Homework 1. Posted 1/19

1. For each of the following code fragments, calculate the number of lines of output produced, when the code fragment is executed. Show your calculations and express your answer as a function of n. For the first two code fragments, assume that n is a multiple of 10 and for the last code fragment, assume that n is a power of 2.

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

      Solution: Fix the value of i at 0. For this value of i, the output statement executes once for each value of j = 0, 10, 20, ..., n - 10. Couting the number of possible values of j, we see that there are n/10 values. So when i = 0, the output statement is executed n/10 times. Similarly, when i = 10, the output statement is executed n/10 times and so on. Just like j, the loop-control variable i also takes on n/10 values. Therefore the output statement gets executed n^2/100 times.

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

      Solution: When i is equal to 0, the output statement is executed 0 times. For any value of i between 1 and 10 (inclusive of both values), the output statement executes once. For any value of i between 11 and 20 (inclusive of both values), the output statement executes twice and so on. Summing this up over all possible values of i we get that the total number of times the output statement is executed is:

      	0 + 1 * 10 + 2 * 10 + 3 * 10 +....
      

      To figure out where this summation stops, note that the last batch of 10 values that i takes are:

      	(n-20) + 1,  (n-20) + 2, ..., (n-20) + 10
      

      For each value of i in this batch, the output statement executes n/10 - 1 times. So the total number of executions of the output statement is:

      	0 + 1 * 10 + 2 * 10 + 3 * 10 +....+ (n/10 - 1) * 10.
      

      Taking 10 common and using the formula for the summation of the first n natural numbers, we obtain that the above summation equals:

      	5(n/10 - 1) (n/10) = n(n-10)/20.
      

   3. 	i = 1;
      	while(i < n)
      	{
      		System.out.println("Hello");
      		i = 2*i;
      	}
      

      Solution: The output statement is executed once for each value of i = 1, 2, 4, 8, ..., 2^k, where 2^k < n, but 2^(k+1) >= n. This is a total of (k+1) times. But, what is k? Solving the inequality, n <= 2^(k+1) < 2n, we get that log_2 (n) <= (k+1) < 1 + log_2 (n). Therefore, the number of times the output statement is executed is the integer between log_2 (n) (inclusive) and log_2 (n) + 1.

2. Bubble Sort is a simple sorting algorithm for which code is given below. In the code, list is an array of size n and the function call swap(list, j, j+1) exchanges the items that are in slots j and j+1 in list.

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

   1. Show the execution of bubble sort on the following sequence of numbers:

      		3 1 8 2 4 5
      

      In particular, show the array after each swap.

      Solution:

      		3 1 8 2 4 5
      		3 1 2 8 4 5
      		1 3 2 8 4 5
      		1 3 2 4 8 5
      		1 2 3 4 8 5
      		1 2 3 4 5 8
      

   2. Calculate the number of comparisons made by the algorithm, as a function of n.

      Solution: For i=0, the variable j takes on n-1 values and therefore for i = 0, n-1 comparisons are made. For i=1, the variable j takes on n-2 values. For i=2, the variable j takes on n-3 values and so on. The last value that i takes is n-1 and for this value of i, the variable j takes on 0 values. Therefore, the total number of comparisons is

      		(n-1) + (n-2) + (n-3) + .... + 3 + 2 + 1 = n(n-1)/2.
      

   3. Notice that the bubble sort algorithm makes the same number of comparisons, independent of the arrangement of items in the array. In other words, bubble sort makes as many comparisons when the input array is already completely sorted, as it does when the input array has many out of order elements. Modify the code so that it detects when the array is sorted and stops immediately.

      Solution:

      	int i = 0;
      	boolean done = false;
      	while(!done)
      	{
      		done =  true;
      		for(int j = n-2; j >= i; j--)
      			if(list[j] > list[j+1])
      			{
      				done = false;
      				swap(list, j, j+1);
      			}
      		i++;
      	}
      

   4. How many comparisons does the improved bubble sort algorithm make when given as input an array of size n that is already in order.

      Solution: The improved bubble sort algorithm makes n - 1 comparisons.

3. In class we discussed an abstract data type (ADT) that supports the following three operations:
   • INSERT(record): inserts the given record into the collection of records.

   • DELETE(key): deletes a record identified by key; does nothing if there is no such record.

   • SEARCH(key): returns a record identified by key; returns null if there is no such record.

   We also discussed two different implementations of this ADT. Implement the above ADT as a java class using an ordered array. Make sure that the search operation is implemented using binary search. Assume that each record consists of three fields. A string field to store a name, a long field to store a social security number, and a double field to store the person's pay. The social security field should be used as a key to delete from the collection and search the collection. Therefore collection of records should be maintained in increasing order of social security number.

   Solution: Here is the code that is the solution to this problem.

   ---