Homework 2. Posted 1/26

1. This problem asks you to run an experiment to measure and compare the running time of the two versions of bubble sort, mentioned in Homework 1, Problem 2. Version A is given below.

   	public static void bubbleSort(int[] list)
   	{
   		int n = list.length;
   		for(i = 0; i < n-1; i++)
   			for(j = n-2; j >= i; j--)
   				if(list[j] > list[j+1])
   					swap(list, j, j+1);
   	}
   

   Version B is the modified version of Version A that stops sorting as soon as it detects that the array is sorted.

   To perform the experiments, you should generate two types of arrays.

   • The "almost sorted" array is generated by starting with an int array of size n containing the sequence 0, 1, 2, ..., n-1 and perturbing it slightly. To perturb the array, pick at random 10 pairs of indices (in the range 0 through n-1) and for each pair of indices (i, j), swap the elements in slots i and j.
   • The "almost unsorted" array is generated in the same way that the "almost sorted" array is generated, except that you start with the sequence n-1, n-2, ..., 3, 2, 1, 0 and perturb it slightly.
   To compute the running time of a version of bubble sort on an array of size n, generate 10 arrays of size n, compute the running time on each array, and take the average of the 10 running times. You do this to get more accurate running times.

   You are required to perform 4 sets of timing experiments, by running: (a) Version A of bubble sort on "almost sorted" input, (b) Version A of bubble sort on "almost unsorted" input, (c) Version B of bubble sort on "almost sorted" input, and (d) Version B of bubble sort on "almost unsorted" input. For each experiment, obtain the running time on arrays of size 1000, 2000, 3000, ..., 10000. You will therefore get 10 running times from each experiment. Plot these running times using your favorite plotting software (Excel, Mathematica, etc.) and connect these points with a smooth curve. You should have 4 plots. Write 3-4 sentences explaining what you see and whether your observations confirm your calculations from Homework 1.

   Some more details. To slightly perturb the contents of an array, you are asked to randomly generate pairs of indices. 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.

2. Calculate the running time of the following code fragments.

   1. 	
      	for(i = 0; i < n; i++)
      		for(j = 1; j <= n; j = 2*j)
      			System.out.println("Hello");
      

   2. 	
      	for(i = 1; i <= n; i = 3*i)
      		for(j = 1; j <= n; j = 2*j)
      			System.out.println("Hello");
      

   3. 	
      	for(i = 1; i <= n; i = 3*i)
      		for(j = i; j < i+10; j = j+1)
      			System.out.println("Hello");
      

   In addition to your answer, show your calculations also. However, your calculations need not be as detailed as for Homework 1, Problem 1.

3. Here is the solution to Homework 1, Problem 3. Modify the RecordDB class given here in two ways.
   1. Add a constructor that takes a positive integer, say n, and allocates an array of size n for the records.
   2. Make the array of records dynamic in the sense that when a new record is to be inserted into a full array, the array is automatically resized to make space for the new record. Always resize the array to about twice its original size.

   ---