Design and Analysis of Algorithms
Fall 2020
Assignment 1
Question 1.(10 pt) Below is the pseudo code for a divide and conquer algorithm that finds the minimum value in an array. Suppose that the input array, A, is of size n, analyze the computational cost of this algorithm in the form of T(n) and prove your conclusion.
Question 2.(10 pt) Given the following program
int function (int n){
if (n<=2)
return 1;
return function(n-1)+function(n-2);
}
Prove this program runs in O(2 n) time.
Question 3.(10 pt) Consider two complex numbers, a + bi and c + di, where . How to compute their product with only 3 numerical multiplications? (Note that there is no requirement on the number of additions or subtractions.)
Question 4. (15 pt) In the linear-time divide-and-conquer algorithm taught in class for the selection problem, recall that we divided the input elements into groups of 5. Analyze the running time of this algorithm, assuming that the input elements are divided into groups of 3. Does your algorithm run in linear time?
[Use a similar proof as given in the lecture slides "Divide & Conquer: Linear Time Selection", page 8.]
Question 5. (20 pt) In the linear-time divide-and-conquer algorithm taught in class for the selection problem, recall that we divided the input elements into groups of 5. Analyze the running time of this algorithm, assuming that the input elements are divided into groups of 8. Does your algorithm run in linear time?
[Use a similar proof as given in the lecture slides "Divide & Conquer: Linear Time Selection", page 8.]
Question 6. (20 pt) Given an increasingly sorted array A[1…n] of n distinct integers. Design an O(log n) algorithm which find the index i such that A[i]=i.
Question 7. (20 pt) Let A be an array of positive integers. Design a divide-and-conquer algorithm for computing the maximum value of A[j]-A[i] with j≥i. Analyze the time complexity of your algorithm.