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.

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

(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.

```
for (int i = 0; i < n; i++) {
   sum++;
}
```

for (int i = 0; i < n; i += 2) {
   sum++;
}

for (int i = 0; i < n; i++) {
   for (int j = 0; j < n; j++) {
      sum++;
   }
}

for (int i = 0; i < n; i++) {
   sum++;
}
for (int j = 0; j < n; j++) {
   sum++;
}

for (int i = 1; i < n; i *= 2) {
   sum++;
}

(4 points) Consider the following algorithm to find the largest number in a given non-empty array, a, of size N. Give the exact running time in terms of N, the big-Theta running time. 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];
    }  
}
```
(6 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. (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.)
(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.

CSSE 230 Data Structures and Algorithm Analysis

Homework 1 - 46 points

To Be Turned In

CSSE 230
Data Structures and Algorithm Analysis