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.

   Solution: Here are three programs that time bubbleSort and improvedBubbleSort: TimingBubbleSort1.java, TimingBubbleSort2.java, and TimingBubbleSort3.java. The first runs the two versions on bubble sort on almost sorted arrays, the second runs these on almost unsorted arrays, and the third runs these on almost sorted arrays obtained using a different kind of small perturbation. For timing plots and comments on these plots, see comments.pdf.

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");
      

      Solution: The body of the outer loop execues n times. The body of the inner loop executes log_2 n times, independent of what the loop control variable i, of the outer loop is. Therefore, the running time of the code fragment is O(n log_2 n).

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

      Solution: The body of the outer loop execues log_3 n times. The body of the inner loop executes log_2 n times, independent of what the loop control variable i, of the outer loop is. Therefore, the running time of the code fragment is O(log^2 n). Note that it is ok to skip writing the base of the logarithm, inside the Big Oh notation.

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

   Solution: The body of the outer loop execues log_3 n times. The body of the inner loop executes 10 times, independent of what the loop control variable i, of the outer loop is. Therefore, the running time of the code fragment is O(log n).

   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.
   Soluion: Here is the solution.

   ---