CSSE 230
Data Structures and Algorithm Analysis

Homework 1  - 63 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 Homework 1 Drop Box on Moodle as a single file in either MSWord or pdf format. 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. Some apps also allow you to take a photo with your phone or tablet and save it as a pdf. After you have submitted, click on the drop box again to verify that your submission was successful.

 

These homeworks used to be called "written assignments", but that was a slight misnomer, because occasionally these assignments include small programming exercises.

Some homeworks 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 homeworks.

In problems #2,3, and 4, if you don't know what Big-Theta running time is, you will be safe giving Big-Oh. 

  1. (5 points) Weiss exercise 2.13 [2.11]. Hint: If one calls resize(ar) from main(), ar is unchanged. Why? Drawing a box-and-pointer diagram may help you.
  2. (6 pts) What is the Big-Theta running time of:
    1. ...an unsuccessful sequential search of an unordered array that contains N elements?
    2. ...an unsuccessful binary search of an ordered array that contains N elements?
    3. ...a merge sort of an array that contains N elements?
    Choose one of the following answers for each part: O(log (N)), O(N), O(N log (N)), O(N^2), or O(N^3).
  3. (10 pts) For each of the following four code fragments, similar to Weiss problem 5.20, first give the exact number of times the "sum++" statement executes in terms of n. Then use that to give a Big-Theta running time (by ignoring the low-order terms). 
    1. for (int i = 0; i < n; i++) 
          sum++;
          
    2. for (int i = 0; i < n; i += 2) 
          sum++;
          
    3. for (int i = 0; i < n; i++) 
         for (int j = 0; j < n; j++) 
           sum++;
           
    4. for (int i = 0; i < n; i++) 
         sum++;
      for (int j = 0; j < n; j++) 
         sum++;
         
    5. for (int i = 1; i < n; i *= 2) 
         sum++;
  4. (3 points) Weiss exercise 5.11 [5.8]. Give big-Theta running time and a brief description of your derivation.
  5. (8 points) Weiss exercise 5.22 [5.17].
  6. (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.
  7. (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 completes this sequence of clicks: the first button,  then the middle button, and then 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?
    Code
  8. (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, give the exact answer. (Note if you would get a non-integer result, your answer must be the floor of it - make sure you understand why.)  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! If it overflows Maple (like line 1 might), you may give an expression instead. 

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.