Homework 2 Solution

1. Purpose: Practice solving recurrences. For each of the following recurrences, use the Master Theorem to derive asymptotic bounds for T(n), or argue why the Master Theorem does not apply. You don’t have to solve the recurrence if the MT does not apply. If not explicitly stated, please assume that small instances need constant time c. Justify your answers, ie. give the values of a, b, n^log_b(a) f, , for case 3 of the Master Theorem also show that the regularity condition is satisfied. (3 points each)
(a) T(n)=8T(3n/2)+n3.
(b) T(n)=4T(n/2)+n2sqrt(n).
(c) T(n)=7T(n/3)+n11/5.
(d) T(n)=4T(n/2)+100-sqrt(n).
(e) T(n)=½T(n/3)+sqrt(n).

2. Purpose: More practice solving recurrences. Please solve the following recurrences. (3 points each)
(a1 & a2) The two recurrences in lecture 4, page 7. Use T(1)=1.
(b) The recurrence in lecture 6, page 7. Use T(1)=0.
(c) Assume c>1. T(8)=…=T(0)=c, T(n) = 3T(n-2)+2n-1 otherwise. Give the exact solution and the asymptotic big-theta bound for T(n). Justify your answers.

3. Purpose: Often, recursive function calls use up precious stack space and might lead to stack overflow errors. Tail call optimization is one method to avoid this problem by replacing certain recursive calls with an iterative control structure. Learn how this technique can be applied to QUICKSORT. (2 points each) Solve Problem 7-4, a-c on page 188 of our textbook.

4. (5 points) Purpose: Practice algorithm design and the use of data structures. This problem was an interview question! Consider a situation where your data is almost sorted—for example you are receiving time-stamped stock quotes and earlier quotes may arrive after later quotes because of differences in server loads and network traffic routes. Focus only on the time-stamps. Assume that each time-stamp is an integer, all time-stamps are different, and for any two time-stamps, the earlier time-stamp corresponds to a smaller integer than the later time-stamp. The time-stamps arrive in a stream that is too large to be kept in memory completely. The time-stamps in the stream are not in their correct order, but you know that every time-stamp (integer) in the stream is at most hundred positions away from its correctly sorted position. Design an algorithm that outputs the time-stamps in the correct order and uses only a constant amount of storage, i.e., the memory used should be independent of the number of time-stamps processed. Solve the problem using a heap.

5 (4 points for each algorithm). Purpose: Implementing algorithms. Implement insertion sort, merge sort, and heapsort, and count the number of comparisons they perform. Follow the description in our textbook in the following sections: Section 2.1, Page 18 for insertion sort; Section 2.3, Pages 31-34 for merge sort; and Sections 6.2-6.4, Pages 154-160 for heapsort. Pay attention to ties and special case considerations. Please only count comparisons between the input values, not between index variables. i) In insertion sort, only count the number of comparisons between elements in the array A (the second compare on line 5 page 18), not the compares that check if the index variable i is larger than zero; ii) in merge sort, count the number of comparisons on line 13 page 31; iii) in heapsort, count the number of comparisons between the elements of array A (the second compare on line 3 and line 6 on page 154), not the compares between variables l, r, A.heapsize, and largest.
Use the code frameworks Solution.py or Solution.java in the file framework.zip. You don’t need to print or return the results, but please make sure that they are stored in the following two instance variables: sorting_array (stores the sorted input) and comparison_count (stores the number of comparisons performed) in Python 2.7, or sortingArray and comparisonCount in Java. You can create additional methods if required but do not change the name of existing methods and any existing code - points will be cut if you do. You can code this in either Java or Python 2.7 (not Python 3). Another file SortingTest.py/java contains test cases to check your code for various inputs. Submit the file Solution.py/java and not the test file. Your code will be checked on the remote-linux server by us automatically using the provided cases in SortingTest.py/java, plus some (unknown) cases. To avoid loss of marks please make sure that all provided test cases pass on the remote-linux server by using the test file. Instructions for the remote-linux server setup and test given in the document “HW2 Programming Assignment Setup instructions and Tutorials.pdf”.