CSSE 230
Data Structures and Algorithm Analysis

Homework 1  - 46 points

To Be Turned In

These are to submitted to the Homework 1 Moodle assignment as a single file in 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 (like MS Word, which exports to pdf). Some apps (like scanbot) also allow you to take a photo with your phone or tablet and save it as a pdf. After you have submitted to the Moodle assignment, click on the submission to verify that it was uploaded successful. Warning: unreadable hand written submissions earn zero credit.

 

Some homeworks will contain problems that are very challenging.  You should read them as soon as they are assigned in case you need a couple of days to ponder one of 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 #1-3, if you don't know what Big-Theta running time is, you will be safe giving Big-Oh. 

  1. (6 points) Choose one of the following answers for each part: Θ(log (N)), Θ(N), Θ(N log (N)), Θ(N2), or Θ(N3). 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?

  2. (10 points) For each of the following four code fragments, similar to Weiss problem 5.20, first write the exact number of times the "sum++" statement executes in terms of n, using the ceiling or floor if needed. (Hint: two of them do.) Then use that to also write the Big-Theta running time.  
    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++) {
         for (int j = 0; j < i; j++) {
            sum++;
         }
      }
    5. for (int i = 1; i < n; i *= 2) {
         sum++;
      }
  3. (4 points) Consider the following algorithm to find the largest number in a given non-empty array, a, of size N. Give the exact, worst-case running time in terms of N, and the corresponding big-Theta value. Note: in this case, we are counting the times we make a comparison less than, greater then, or equals) using at least one array element, so specifically the condition in the if statement. 
    int max = a[0];
for (int k = 1; k < a.length; k++) {
    if (a[k] > max) {
        max = a[k];
    }  
}
  4. (6 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. In this problem and throughout this course, unless I specify otherwise, log n means the logarithm in base 2 of n. Explain how you know that this is the correct integer. (Hint: if solving for N isn't working for you, graphing this in Maple and submitting your graph sounds like a great idea! Make sure you zoom in/out at various levels to see where the graphs cross, even going out to n = 40.)
  5. (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. 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.