Computer Science Homework Help

3. Prove by induction that Fi =
φ
i−φˆi
√
5
where φ =
1+√
5
2
and φˆ =
1−
√
5
2
(Note: Fibonacci numbers
(F0 = 0, F1 = 1, F2 = 1, F3 = 2, . . .) satisfy the relation Fi = Fi−1 + Fi−2). (20 pt)

4. Solve the follwoing recurrences using the master method. (20pt)

(a) T(n) = 4T(n/3) + nlgn

(b) T(n) = 4T(n/2) + n
2√
n.

(c) T(n) = 2T(n/4) + √
n.

(d) T(n) = 7T(n/2) + n
2
.

5. Recall the following partition algorithm from quicksort:

Partition (A , p , r )
x = A [ r ]
i = p – 1
for j = p to r – 1 {
if ( A [ j ] <= x ) {
i = i + 1
swap A [ i ] and A [ j ]
}
}
swap A [ i +1] and A [ r ]
return i + 1

(a) Explain the running time of the algorithm if the initial call is Partition(A, 1, n) (In other words,
the input array is A[1, . . . , n] with size n). (10 pt)

(b) Assume that all elements of the input array A has the same value, e.g., A = [1, 1, . . . , 1] with size
n. What value does the partition algorithm return? (10 pt)

6. Describe an O(nlgn)-time algorithm to solve the following problem. (20pt)

Input: a set S of integers with |S| = n, and an integer k

• Decide: if there exists two elements in S whose sum is exactly k.