Can somebody please help me with these problems? These are from the textbook Fou
ID: 671182 • Letter: C
Question
Can somebody please help me with these problems? These are from the textbook Foundations of Algorithms by Richard Neapolitan and Kumarss Naimipour.
37. Use the divide-and-conquer approach to write a recursive algorithm that computes n!. Define the input size and answer the following questions. Does your function have an exponential time complexity? Does this violate the statement of case 1 given in Section 2.8? The statement of case 1 is: 1. An instance of size n is divided into two or more instances each almost of size n.
38. Suppose that, in a divide-andconquer algorithm, we always divide an instance of size n of a problem into n subinstances of size n/3, and the dividing and combining steps take linear time. Write a recurrence equation for the running time T(n), and solve this recurrence equation for T(n). Show your solution in order notation.
Thank you!
Explanation / Answer
Hi,
Below is the solution to your problem:
Divide and conquer:
1.Break problem into smaller problems
2.Solve smaller problems
3.Combine results
Example:
• Factorial of n: – n! = n * (n-1) * (n-2) * … * 2 * 1
• Recursive definition: – n! = n * (n-1)! and 1! = 1
• Computation of factorial of 4: – 4! = 4 * 3! = 4 * 3 * 2! = 4 * 3 * 2 * 1! = 4 * 3 * 2 * 1 = 24
Algorithm:
Finding factorial of n >= 1
• n! = n(n-1)(n-2)…1
• Divide and Conquer Strategy:
• if n = 1: n! = 1 (direct solution),
else: n! = n * (n-1)!
When a function makes use of itself, as in a divide-and-conquer strategy, it is called recursion
• Recursion requires: Base case or direct solution step. (e.g., factorial(1))
• Recursive step(s): • A function calling itself on a smaller problem. E.g., n*factorial(n-1)
• Eventually, all recursive steps must reduce to the base case
Proof by induction:
(1) Solution works for n = 0
(2) If it works for n-1, it works for n
(3) 1. and 2. imply, it works for n = 1
(4) 2. and 3. imply it works for n = 2 and in fact any larger n
Recursive function:
static private int factorial(int n)
{
if (n==1)
{
// check for termination condition
return 1;
} else {
// break problem into smaller problem
int fac = n*factorial(n-1);
return fac;
}
}
Implementation of recursion
• What does the computer do?
– In which order do function calls and multiplications happen?
• Method call for n=4: calls method for n-1=3
• Method call for n=3: calls method for n-1=2
• Method call for n=2: calls method for n-1=1
• Method call for n=1: returns value 1
• Method call for n=2: computes 2*1, returns 2
• Method call for n=3: computes 3*2, returns 6
• Method call for n=4: computes 4*6, returns 24
Complexity analysis:
Hope that answers your question...HAPPY ANSWERING!!!!!!!