Given three SORTED (in ascending order) arrays A[1..n], B[1..n], and C[1..n], each containing n numbers, give an O(log n)-time algorithm
computer science
Description
Exercise 5.9. Given
three SORTED (in ascending order) arrays A[1..n], B[1..n], and C[1..n], each
containing n numbers, give an O(log n)-time algorithm (again, counting the
number of comparisons) to find the nth smallest number of all 3n elements in
arrays A, B, and C.
We are given an array A containing n numbers, and an integer
k that divides n. We want to find k numbers x1,x2, ...,xk of A such that xi is
the ( n k i)-th smallest element of A. Develop a divide and conquer algorithm
that finds the xi ’s that runs in time O(n lg k). Prove its correctness and
running time.
Exercise 5.19. Recall that the Fibonacci numbers are defined
by the following recurrence: F0 = 0, F1 = 1 and Fn = Fn−1 + Fn−2 for n > 2.
1. Using the above recurrence, give a simple algorithm to compute Fn, given n.
The complexity of the algorithm in terms of the number of arithmetic operations
should be O(n 2 ). Show that the algorithm indeed has this complexity. Recall
that an arithmetic operation is the cost of adding or multiplying two single
digit numbers. (Hint: How many digits are there in Fn? Use the fact that Fn is
Θ(( 1+√ 5 2 ) n ). 2. Our goal is to use the following matrix identity to
compute the nth Fibonacci number more efficiently. F1 F2 ! = 0 1 1 1! · F0 F1 !
(5.1) (a) Show that Fn Fn+1! = 0 1 1 1!n · F0 F1 ! (5.2) (b) Show that O(log n)
matrix multiplications are enough to compute Fn. (c) Using the fast algorithm
for multiplying two integers (Karatsuba’s algorithm) show that Fn can be
computing in O(n log2 3 log n) arithmetic operations. (d) Can you improve your
analysis of (c) and show a cost of O(n log2 3 ) arithmetic operations ?
