(NEW) The solution is here.
1) (10 points) Exercise 5.1, Weiss, page 194
2) (10 points) Show how heapsort processes the input: 5, 9, 2, 1, 8, 11, 10, 7
3) (18 points, 1 point for each) Consider the following algorithms, as discussed in the lectures:
(a) insertion sort
(b) selection sort
(c) bubble sort (the most optimized version discussed in class)
(d) heap sort
(e) merge sort
(f) quick sort with the pivot = the middle element
For each of these algorithms indicate the asymptotic running time in each of the following cases:
(i) The input is 1, 2, 3, ..., n
(ii) The input is n, 1, 2, ..., n-1
(iii) The input is 2, 3, ..., n, 1
You need to provide eighteen Big-O answers.
4) (15 points) Sorting Phone Numbers The input to this problem consists of a list of 7-digit phone numbers written as simple integers (e.g. 5551212 represents the phone number 555-1212). No number appears in the input more than once but there is no other limit on the size of the input. Write precise (preferable Java-like) pseudocode for a method that prints out the phone numbers (as integers) in the list in ascending order. Your solution must not use more than 2MB of memory. You should explain why this is true of your solution. (Note: No cheating! It cannot use any external storage or hard disks or tapes or punched cards or the network or an infnite tape etc. Assume that as input you will get an Iterator<Integer>).