CSSE 230
Data Structures and Algorithm Analysis

Written Assignment 1  - 53 points

To Be Turned In (at the end of this documents are some problems to consider but not turn in)

These are to submitted to the HW1 Drop Box on ANGEL by 8:00 AM on the due date. You can write your solutions out by hand and scan them (there is a networked scanner in F-217, and several scanners in the library's Digital Resource Center), or create a file on your computer directly (submit as 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.

Some written assignments will contain problems that are very challenging.  You should read them as soon as they are assigned. Then if you need a couple of days to ponder one of them, you will have them.

 

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 N2 operations. For small values of N, algorithm B is faster; for large values of N, algorithm A is faster. Determine the smallest possible integer N0 such that for all N > N0 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 should 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.