22C:21: Computer Science II: Data Structures

Homework 1: 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.

    Solution: Here is the solution.

  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:

    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.

    Solution:

    import java.util.*;
    
    class hello
    {
            public static void main(String[] args)
            {
                    // Defines x as a reference/pointer to a Vector object
                    // The definition also specifies that each element
                    // of the Vector is itself a Vector of Integer objects
                    // So you should think of x as a 2-dimensional object
                    Vector> x;
    
                    // Allocates space for x by calling a constructor in
                    // the Vector class that takes a single argument that
                    // specifies the initial capacity of the Vector.
                    // Now x contains 3 items, each item currently points
                    // to nothing
                    x = new Vector>(3);
    
    
                    // Now each item in x is a reference/pointer to a Vector
                    // of size 4. So now x can be thought of as a matrix
                    // with 3 rows and 4 columns
                    for(int i = 0; i < 3; i++)
                            x.add(new Vector(4));
    
    
                    // Add code here that reads 12 integers input by a user.
                    // Assume that the user inputs the 4 numbers in row 1
                    // followed by the 4 numbers in row 2, followed by the
                    // 4 numbers in row 3
                    Scanner input = new Scanner(System.in);
                    System.out.println("Enter 12 integers");
    
                    for(int i = 0; i < 3; i++)
                            for(int j = 0; j < 4; j++)
                                    (x.get(i)).add(input.nextInt());
    
                    // Add code here to output the 12 numbers in the matrix.
                    // The output is required to contain the 3 numbers in column
                    // 1, followed by the 3 numbers in column 2, etc.
    
                    for(int j = 0; j < 4; j++)
                    {
                            for(int i = 0; i < 3; i++)
                            {
                                    System.out.print(x.get(i).get(j));
                                    System.out.print(" ");
                            }
    
                            System.out.println();
                    }
            }
    }
    

  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.
            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;
    
            }
    

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

    Solution: Shown below is thte arrangement of the elements in the array data, at the beginning of each execution of the for-loop. The values of i and j are also shown. The value returned by the function is left+9.

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

    The first element in data is chosen as the pivot and this element is always at the right end of the first block constructed by partion. In the above example, 11 is chosen as the pivot. The subarray data[left..i] is the first block, the subarray data[i+1..j] is the second block, and the subarray data[j+1..right] is the unprocessed block. In each iteration of the for-loop the next unprocessed element is processed and is either added to the first block or to the second block, depending on how it compares to the pivot element.