CMPSC 20
2003:April:02

CMPSC 20 Exercise-Set #1

Due Wednesday, April 9 at lecture



    You can do all of these exercises in teams of (at most) two. But rem. each of you needs to learn the material e.g. so you'll know it for tests.


    Acknowledgement: Some of these exercises are derived from "A Practical Introduction to Data Structures and Algorithm Analysis" by Clifford A. Shaffer.


  1. [20 points]   One type of `checksum' is the 32-bit integer that is the sum of the Unicode characters in a file. (Overflow of the range of numbers representable in 32 bits is allowed; but actually overflow is unlikely if all the characters are ASCII.) This information can be used as follows: The checksum is calculated for the original material. When the material is copied or transmitted across a network, the checksum is calculated for the copy, and having the same checksum as the original one gives some assurance that the material was not corrupted in transit.
    Write a program to compute this checksum of a file that is specified as a command-line argument to your Java application-program.
    For this exercise, submit a printout of your Java code, and load the .class-file obtained from compiling your program into your Enterprise account. (But you can put it actually outside your www folder in your account, since this program isn't an applet.) Rem. specify "binary" mode if you use ftp .
    20% of the points here are reserved for having good style, i.e. Good Programming Practices. But beyond that, you won't gain any more credit for doing any other extra work for this exercise, since it's not a project-exercise.


  2. [20 points]   Do our textbook's Programming Projects 2.1-3 .
    2.1
    To the HighArray class in the highArray.java program (Listing 2.3), add a method called getMax() that returns the value of the highest key in the array, or -1 if the array is empty. Add some code in main() to exercise this method. You can assume all the keys are positive numbers.
    2.2
    Modify the method in Programming Project 2.1 so that the item with the highest key is not only returned by the method, but also removed from the array. Call the method removeMax().
    2.3
    The removeMax() method in Programming Project 2.2 suggests a way to sort the contents of an array by key value. Implement a sorting scheme that does not require modifying the HighArray class, but only the code in main(). You'll need a second array, which will end up inversely sorted. (This scheme is a rather crude variant of the selection sort in Chapter 3, "Simple Sorting.")
    Submit a printout and load your .class-file into your Enterprise account as above.


  3. [20 points]   Do our textbook's Programming Project 2.4 .
    2.4
    Modify the orderedArray.java program (Listing 2.4) so that the insert() and delete() routines, as well as find(), use a binary search, as suggested in the text.
    Submit a printout and load your .class-file into your Enterprise account as above.


  4. [36 points]   Here are some functions of n:
    4n2     log3n     3n     20n     2     log2n     n2/3     n!


  5. [6 points]  
    1. Suppose that a particular algorithm has time-complexity T1(n) = 3×2n, and that executing an implementation of it on a particular machine takes t1 seconds for n inputs. Now suppose that we are presented with a new machine that is 64 times as fast as the old machine. How many inputs can we process on the new machine in t1 seconds?
    2. Suppose that another algorithm has time-complexity T2(n) = n2, and that executing an implementation of it on a particular machine takes t2 seconds for n inputs. Now suppose that we are presented with a new machine that is 64 times as fast as the old machine. How many inputs can we process on the new machine in t2seconds with this algorithm?
    3. A third algorithm has time-complexity T3(n) = 8n. Executing an implementation of it on a particular machine takes t3 seconds for n inputs. Given a new machine that is 64 times as fast, how many inputs can we process in t3 seconds with this third algorithm?


  6. [8 points]   Hardware vendor XYZ Corp. claims that their latest computer will run 100 times faster than that of their competitor, Prunes, Inc. If the Prunes, Inc. computer can execute a program on input of size n in one hour, what size input can XYZ's computer execute in one hour for each algorithm with the following growth-rate equations?
    n     n2     n3     2n


  7. [12 points]   In terms of the value of n, determine O() for the following code-fragments in the average case. Assume that all variables are of type int .
    1. a = b + c;
      d = a + e;
      
    2. sum = 0;
      for ( i = 0; i < 3; i++ )
          for ( j = 0; j < n; j++ )
      	sum++;
      
    3. sum = 0;
      for ( i = 0; i < n*n; i++ )
          sum++;
      
    4. Assume array A contains n values.
      for ( i = 0; i < n; i++ ) {
          for ( j = 0; j < n; j++ )
      	A[i] = (int) (n * Math.random());
      		// Math.random() takes constant time
          sort(A);	// sort() takes  n * log(n)  time
          }
      
    5. Assume array A contains a random permutation of the values from 0 to n - 1 .
      sum = 0;
      for ( i = 0; i < n; i++ )
          for ( j = 0; A[j] != i; j++ )
      	sum++;
      
    6. sum = 0;
      if ( EVEN(n) )
          for ( i = 0; i < n; i++ )
      	sum++
      else
          sum = sum + n;
      


  8. [3 points] Without worrying about the worst-case running-time at first, say what you think is the shortest possible running-time for the following code-fragment, as a function of the initial value of n:
    count = 0;
    while ( n > 1 ) {
        if ( ODD(n) )
    	n = 3*n + 1;
        else
    	n = n/2;
        count++;
        }
    
    Then, briefly discuss what you think the real O() worst-case running-time of this code may be.


  9. [1 point]   You will get this 1 point if you do all the steps of submission correctly: including your name(s) and U-Mail/Enterprise account-names at the top front of your submission, properly loading any .class files for this assignment -- and not posting on the Web any .java files.