CSSE 230
Data Structures and Algorithm Analysis

Written Assignment 1  - 53 points

To Be Turned In

These are to be turned in to the HW1 Drop Box on ANGEL. You can write solutions out by hand and scan them (there is a networked scanner in F-217), or create a file on your computer directly (MSWord or PDF, please .   After you have submitted, click on the drop box again to verify that your submission was successful.

"Written assignment" is sometimes a slight misnomer, because occasionally these assignments will include very small programming exercises.

The numbers in [square brackets] are problem numbers from the third edition of Weiss, for those who have that version.

Late days may be used or earned for written assignments.

1. (5 points) Weiss exercise 2.13 [2.11].
2. (6 points) Weiss exercise 5.10 [5.7] (a and b only). Give big-Oh running time and a brief description of your derivation.
3. (3 points) Weiss exercise 5.11 [5.8]. Give big-Oh running time and a brief description of your derivation.
4. (8 points) Weiss exercise 5.22 [5.17].
5. (5 points) When the input size is N, algorithm A uses 5 N log N operations, while algorithm B uses N² operations. For small values of N, algorithm B is faster; for large values of N, algorithm A is faster. Determine the smallest possible integer N₀ such that for all N > N₀ algorithm A is faster than algorithm B. Explain how you know that this is the correct integer.
6. (6 points) Draw what the window looks like when the following code is run (a) (2) when the program is first launched, (b) (3)after the user clicks the first button,  the middle button, and the last button.  You shoud figure this out by reading the code, not by running it. (c) (1) What common data structure is created and used in this code?
   
7. (20 points) For each function in the following table, determine the largest size n of a problem that can be solved in time t, assuming that the problem takes f(n) microseconds, where f(n) is the function in the left column.  Throughout this course, unless I specify otherwise, log n means the logarithm in base 2 of n.    If the answer is small, round it to the nearest integer and give the exact answer.  If it is a million or larger, you can use scientific notation, with a couple of decimal places of precision.  Hint: Maple is your friend!.
   

For Your Consideration

These problems are for you to think about and convince yourself that you could do them. It would be good practice to actually do them in the next couple of weeks, but you are not required to turn them in.

• Weiss exercise 2.7 [2.6]. In addition to telling what each prints, explain why it prints what it prints.
• Weiss exercise 2.11 [2.9].
• Weiss exercise 3.14 [3.11]. Read the first sentence as " ... a single private constructor and no other constructors."
• Weiss exercise 4.6 [4.6]. Be sure that you consider all seven parts (some are on the next page).
• List the number of each of the statements in the main( ) method of the following program that would have to be commented out in order to make this code compile and run. For each statement that you list, explain why it is illegal.

  public class HW1StaticMethods { 
     public int pi;
     public static int psi = 5;
     
     public static int triple(int i) {
        return 3*i;
     }
     
     public int quadruple(int i) {
        return 4*pi;
     }
     
     public HW1StaticMethods(int i){
        this.pi = i;
     }
     
     public static void main(String[] args){
        
        HW1StaticMethods hw1 = new HW1StaticMethods(12);
        /*1*/ System.out.println(pi);
        /*2*/ System.out.println(psi);
        /*3*/ System.out.println(quadruple(6));
        /*4*/ System.out.println(triple(7));
        /*5*/ System.out.println(hw1.pi);
        /*6*/ System.out.println(hw1.psi);
        /*7*/ System.out.println(hw1.quadruple(6));
        /*8*/ System.out.println(hw1.triple(7));
        
     }