1. Which of the following programs from the textbook are stable: selection, insertion, or bubblesort.
2. Suppose you are given a list of N points in the plane. Point i is described by two 16-bit integer coordinates x[i] and y[i]. Describe an O(Nlog N) time algorithm for printing out a list of all points that appear two or more times in the list.
3 Show how the file 1 0 0 1 1 1 0 0 0 0 0 1 0 1 0 0 is partitioned using Program 7.2. Then show how the same file is partitioned if we replace the condition (i >= j) by (i > j). Give the contents of the file and the values of i and j after partitioning is complete, in both cases.
4. Solve the following recurrence for all positive integers N which are powers of 2: T(1) = 0, T(N) = T(N/2) + 1 if N >= 2. Prove your answer by mathematical induction.
5. The largest element in a heap must appear in position 1, and the second largest element must be in position 2 or position 3. Give the list of all positions in a heap of size 15, where the k-th largest element can appear for k = 3, 4, 5. Assume all elements are distinct.
6. Give the sequence of heaps produced when the operations P R I O * R * * I * T * Y * * * Q U E * * * U * E are performed on an initially empty heap. (A letter means "insert" and an * means "delete maximum".)
7. Prove that quicksorting a list of N items always requires a number of comparisons that is at least c Nlog N, for some constant c>0.
8. How many operations does Program 7.1 in book (quicksort) take if the input is an array of N copies of the letter A.
9. Suppose you have to merge k sorted lists of N numbers each. Design a fast algorithm for doing that using ideas covered in in class. How fast is it as a function of N and k? Use the big-oh notation and justify your answer.
10. Given N points on a circle centered at the origin, design and analyze an algorithm for determining whether, among the N points, exactly two of them are antipodal (ie, the line they determine passes through the origin).