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

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

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

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.

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

   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.

   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.

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.

   ---