Consider this recursive function: 1* Write the recurrence formula for the TIME C
ID: 3605974 • Letter: C
Question
Consider this recursive function:
1* Write the recurrence formula for the TIME COMPLEXITY of this function, including the base cases for N>=0. (You do NOT need to solve it.) (Note that it should NOT be the formula for what the function computes, but for how long it takes.)
2* Draw the tree that shows the function calls performed in order to compute foo(5) (the root will be foo(5) and it will have a child for each recursive call.) Also show what each call returns by using an arrow pointing back from the child to the parent.
3* Write the memoized version of this function in a file called memoization.c.
4* Re-implement this function with memoization (i.e. use a solution array to look-up and store results of recursive calls). The function signature can be whatever you want.
5* Write a wrapper function that calls the memoized foo function. The signature should be: int foo_wrapper(int N) .
6* The main function should call and print the result for foo_wrapper(15) and then for foo_wrapper(10) and after that it should repeatedly read N from the user and call foo_wrapper(N) and print the result until the user enters -1 for N.
Explanation / Answer
a) B(n) be the number of length n bit sequences that have no three consecutives 0s(i.e., do not contain the substring “000”)
Any bit string that has no 000 must have a 1 in atleast one of the 1st three positions. The n we will break up all bit strings by avoiding 000 by when the first 1 occurs. i.e., each bit string of length n avoiding 000 falls into exactly any one of these cases:
Therefore, the recurrence is
B(n)=B(n-1)+ B(n-2)+ B(n-3), with B(0)=1, B(1)=2, B(2)=4
Or
B(n)=B(n-1)+ B(n-2)+ B(n-3), with B(1)=2, B(2)=4, B(3)=7
b) Let S(n)={1,2,3,…,n}. We say that a subset A of S(n) is good if A does not contain any two consecutive integers.
For any k, let a(k) be the number of good subsets of S(k).
There are two types of good subsets of S(n).
Type 1 good subsets of S(n) contain the element n,
Type 2 good subsets of S(n) do not contain n.
We first get an expression for the number of Type 1 good subsets of S(n) , where n2.Such a subset cannot contain n-1. So any Type 1 good subset of S(n) is obtainable by adding n to a good subset of S(n-2) . Also, if we add n to a good subset of S(n-2) , we always obtain a Type 1 good subset of S(n) So there are exactly as many good Type 1 subsets of S(n) as there are good subsets of S(n-2) . By definition there are a(n-2) good subsets of S(n-2) .
A good subset of S(n) is either of Type 1 or of Type 2. So the number of good subsets of S(n) is a(n-2)+a(n-1)
We have therefore shown that a(n) = a(n-2)+a(n-1)
c)
In this firstly see that if n is not a multiple of 3, then there will be no way to tile the rectangle. And if n is a multiple of 3, then there are two ways to tile the 1st three coloumns:
The rest of the tilling is a tilling of a 2x(n-3) rectangle of which there are T(n-3).
Therefore the recurrence is
T(n )= {2T(n-3), with T(0)=1 if n=0(mod 3) or 0 else
We could use the base case T(3)=2
So, the following recurrence can be aslo equivalent to T(n)= 2T(n-3), with T(0)=1, T(1)=0,T(2)=0
Or
T(n)= 2T(n-3), with T(1)=0, T(2)=0,T(3)=2
d)A ternary string is a sequence of digits, where each digit is either 0,1,or 2.
Here according to the problem in example, we cannot have 2 anywhere after a 0, and the dot represents a binary string, i.e. a string of length(n-1) with the property that we cannot use 2 anywhere after the use of 0.
For the base case we have to note that any ternary string of length 1 satisfies the required property. Hence the recurrence is
T(1)=3
T(n)=2T(n-1)+2^(n-1)