Homework 2: Due 9/23, 2005

1. Write a recursive function that takes a positive integer n and produces as output all subsets of the set {1, 2, 3, ..., n}. For example, if n = 3, then the output would be

   empty set
   1
   1 2
   1 3
   2 
   2 3
   3
   1 2 3
   

   The order in which the subsets are generated does not matter.

   To write this recursive function use the following idea of expressing the problem with input n in terms of a smaller problem with input n-1. To generate all subsets of {1, 2, ..., n}, first generate all subsets of {1, 2, 3, ..., n-1}. Then generate all subsets of {1, 2, 3, ..., n-1} a second time, but this time appending the number n to each subset generated.
   

   What to submit: A printout of just the function genSubsets.

2. In this problem you are asked to perform experiments to compare the performance of bubbleSort, mergeSort, and quickSort. To perform the experiments, generate for each value of n, 10 integer arrays of size n, run all three sorting algorithms on each of the 10 arrays, time each run, and report the mean running time (taken over the 10 runs) for each algorithm, for each value of n. Do this for the following values of n: 1000, 2000, 3000, ..., 10,000 and make a plot of running times, one each for bubbleSort, mergeSort, and quickSort. Write about 10 sentences summarizing your observations, based on these plots. Consider the following questions:
   • Which implementation is fastest?
   • How does the running time seem to grow, as a function of n, for each implementation? Does the growth of the running time match your expectation?
   • Of mergeSort and quickSort, which is faster?

   Some more details. You should fill the integer arrays with randomly generated integers. To randomly generate an integer you can use the class Random defined in java.util. To learn more about this class see this page at java.sun.com. To time your functions use the function System.currentTimeMillis(). Here is an example of the bubble sort algorithm being timed. To ensure that all of you are timing the same code, I would like you to start with our textbook's implementations of three algorithms. You can download them from here: bubbleSort, mergeSort, and quickSort.
   

   What to submit: (i) One program that contains your entire experiment. It should include the functions for the three sorting algorithms, it should include code for generating the arrays, and it should include code that calls and appropriately times the sorting functions. (ii) three plots, one for each sorting algorithm, and (iii) a brief write-up (about 10 sentences, at most) containing your observations.

3. This program shows how to define a 2-dimensional structure using Vectors. Complete the program as per instructions given in the comments in the program.
   

   What to submit: A printout of the updated program.

4. Here is a version of the partition function that is different from the one given in the textbook and the one I presented in class. Suppose that the array data contains the sequence

   		11 3 4 9 34 6 9 18 2 7 8 1.
   

   Show how data is rearranged after the execution of partition. Also, indicate what the value returned by the function is.

   In 2-3 sentences, describe the algorithm that partition is using to achieve its task.

   	public static int partition(int[] data, int left, int right)
   	{
   		int i, j;
   		
   		i = left;
   		for(j = left; j <= right; j++)
   		{
   			if(data[j] < data[i])
   			{
   				swap(data, i, j);
   				i++;
   				swap(data, i, j);	
   			}
   		}		
   
   		return i;
   
   	}
   

   
   

   What to submit: The array data after partition completes, the value it returns, and a 2-3 sentence description of the algorithm it uses.