Algorithms Assignment

Insertion Sort as Recursive Procedure

1. Insertion sort can be expressed as a recursive procedure as follows. In order to sort A[1 .. n], we recursively sort A[1 .. n -1] and then insert A[n] into the sorted array A[1 .. n - 1]. 
1a) (10 points) Write pseudocode for this algorithm, Insertion sort, as a RECURSIVE procedure.

1b) (4 points) Write a recurrence for the worst case running time of this recursive version of insertion sort.

1c) (3 points) Solve the recurrence equation.

1d) (3 points) Is your Insertion sort stable? Why or why not?

 

2. (20 points) Each of n keys in an array may have one of the values red, white or blue. Give a linear time algorithm for rearranging the keys so that all the reds come before all the whites and all the whites come before all the blues. The only operations permitted on the keys are
- Examination of a key to find out what color it is.
- A swap (interchange of positions) of two keys specified by their indices.

 

3. (20 points) The operation HEAP-DELETE(A, i) deletes the item in node i from heap A. Give an implementation of HEAP-DELETE that runs in O(lg n) time for an n-element max-heap. Explain in detail why it is O(lg n).

 

4.  (20 points) Given a set of n numbers, we wish to find the i largest numbers in sorted order using an ith largest order-statistic algorithm that returns an array of the i largest numbers in sorted order, lowest to highest.Find a theta bound on the worst case running time in terms of n and i and show it with your analysis. (No pseudocode needed)

 

5. (20 points) Given a sequence of n numbers a1, a2, a3, . . . , an (some of them might be negative) stored in an array, we want to find two indicies i <= j such that the sum of the numbers from ai to aj is maximum, among all possible i-j pairs and 1 <= i <= j <= n.  Derive the content we learn from dynamic programming and show the substructure. Write pseudocode of  an O(n) algorithm.