Problem Set 10. Posted 4/7

Notes: Of the three problems given below, one will be solved by the TAs in next week's discussion section, you will have to solve one in class, and the remaining problem is due in the lecture on Friday, 4/14.

1. The recursive solution to the Towers of Hanoi problem (discussed in class) is given here. Translate the recursive function TowersOfHanoi that you see here into an iterative function, by explicitly using a stack to simulate the recursion. Start with Lafore's implementation of the Stack class and modify it to so that each item in the stack is an activation record. Recall that an activation record for our simulation of fibonacci consisted of two fields: n and count. For this problem, some additional fields are needed, but the overall idea and code are similar to what we used in our simulation of fibonacci.

2. This problem asks you to illustrate how depth first traversal works on the graph given below. Assume that a depth first traversal is started on the above graph with source A. Further assume that in the adjacency list representation of the graph, each adjacency list contains vertices in alphabetical order. List vertices in the order in which they are visited by the depth first traversal. Show the depth first tree that is constructed.

3. This problem asks you to perform experiments to get a better sense of the running time of the quick sort function. The quick sort code discussed in class is posted here. Derive two versions of the quick sort from this code. In the first version, the partition function simply picks the first element of the given array as the pivot. In the second version, the partition function randomly picks an element of the given array as the pivot. We will call this version, randomized quick sort. You are required to run quick sort and randomized quick sort of input arrays generated as follows.

   For each value of n generate an array of size n called randomList, with integers in the range 1 through n, chosen randomly. It is okay for this array to contain duplicates. Run quick sort and randomized quick sort on randomList and record the running times of these functions. Then take the sorted version of randomList, reverse it, and create another array of elements, called reverseList. Run quick sort and randomized quick sort on reverseList and record the running times of these functions. Repeat this 10 times (for the same value of n) and compute average running times. You should have 4 average running times: (i) quick sort on randomList, (ii) randomized quick sort on randomList, (iii) quick sort on reverseList, and (iv) randomized quick sort on reverseList.

   Finally, repeat this for values of n equal to 10000, 11000, 12000, ..., 19000. Produce 4 plots, each with n on the x-axis and average running time on the y-axis. Comment on your plots, indicating whether they correspond to theoretical predictions. (1) Use partition with no trick. Generate (a) random input and (b) input sorted in reverse order. Run quick sort, time, and explain results. (2) Use partition with randomization. Generate (a) random input and (b) input sorted in reverse order. Run quick sort, time, and explain results.

   ---