Description

Furthermore, please note that the graders will grade 3 out of the 6 questions randomly. Therefore, if the grader decides to check questions 1, 2 and 4, and you haven’t answered question 4, you’ll lose points for question 4. Hence, please answer all the questions. 1. The Fibonacci series can be computed as follows,
F(n) = F(n − 1) + F(n − 2) (1)
In class, we showed how this can be done in O(log n) computation time. Now suppose that the definition is changed in the following way,
F0(n) = F0(n − 1) + F0(n − 2) + F0(n − 3) + F0(n − 4) (2)
Can F0(n) be computed in O(log n)? If yes, please show how it can be done. If no, show a counterexample where this fails. Please provide your rationale for both. Assume that F0(0) = 0,F0(1) = 1,F0(2) = 1,F0(3) = 1. [25 Points].
2. Consider the following problem. You’re given an array A consisting of n integers A[1],A[2],…,A[n]. You’d like to output a two-dimensional n × n array B in which B[i,j](for i < j) contains the sum of array entries A[i] through A[j], i.e., the sum A[i] + A[i + 1] + … + A[j]. (The value of array entry B[i,j] is left unspecified whenever i ≥ j, so it doesn’t matter what is output for these values.)
A simple algorithm to solve this problem illustrated in Algorithm 1:
Data: Input A and n
Result: Return B
1 for i = 1, 2, …, n do
2 for j = i + 1, i + 2, …, n – 1 do
3Add up array entries A[i] through A[j]
4Store the result in B[i,j]
5 end
6 end
7 Return B;
Algorithm 1: Algorithm for Q2
• For some function f that you should choose, give a bound of the form O(f(n)) on the running time of this algorithm on an input of size n (i.e., a bound on the number of operations performed by the algorithm). [8 Points].
• For this same function f, show that the running time of the algorithm on an input of size n is also Ω(f(n)). (This shows an asymptotically tight bound of Θ(f(n)) on the running time.) [8 Points].
• Although the algorithm you analyzed in parts (a) and (b) is most natural way to solve problem-after all, it just iterates through the relevant entries of the array B, filling in a value for each – it contains some highly unnecessary sources of inefficiency. Give a different algorithm to solve this problem, with an asymptotically better running time. In other words, you should design an algorithm with running time O(g(n)), where limn→∞g(n)/f(n) = 0. [9 Points].
3. Design an algorithm to compute the 2nd smallest number in an unordered (unsorted) sequence of numbers {a1,a2,…,an} in n + dlog2(n)e− 2 comparisons in the worst case. If you think such an algorithm can be designed, then show how it can be done. If your answer is no, then explain why it cannot be done. [25 points]
4. Let n = 2p, V = (v1,…,vn),W = (w1,…,wn). Then we can compute the vector product V W by the formula: P1≤i≤p(v2i−1 + w2i) × (v2i + w2i−1) −P1≤i≤p v2i−1× v2i −P1≤i≤p w2i−1× w2i
which requires 3n/2 multiplications. Show how to use this formula for the multiplication of two n × n matrices giving a method which requires n3/2 + n2 multiplications rather than the usual n3 multiplications. [25 points]
5. Find the solution to the following recurrence relation: T(n) = 16T(n/4) + n2, for n a power of 4 (or, n = 4k) and n > 1. Show all your work. [25 points]
6. Find the solution to the following recurrence relation:
T(1) = 1
T(n) = 3nT(n/2), for n a power of 2 (or, n = 2k) and n > 1. Show all your work. [25 points]