CSSE 230
Data Structures and Algorithm Analysis

Written Assignment 3  -  85 points

To Be Turned In

These are to be turned in to a drop box on ANGEL.

[Numbers in brackets] are problem numbers from the third edition of the Weiss textbook.

The following formulas for series sums may be helpful:

  1. (15 points) Weiss Problem 5.3[5.3], parts b–d. For each of these statements: if the statement is always true, explain why using the N0 and c idea from the formal definition of big-Oh. If the statement can be false, give an example of functions T1 T2, and F for which it is false. (Hints: For algorithm analysis we assume that all the functions have non-negative values; an algorithm can’t execute in negative time. As a guideline on how to prove any of the statements that may be true, you’ll find a solution to part a of this problem posted on ANGEL as part of the WA2 solutions) .  Note that the use of big-O instead of big-theta here is intentional; some of the answers would be different if big-theta was used instead.
  2. (8 points) Weiss Problem 5.15 [5.12].
  3. (12 points) For each of the following four code fragments, similar to Weiss problem 5.20 [5.15], give a Big-Oh analysis of the running time. By “analysis” we mean that you should give the Big-Oh answer and explain how you arrived at it. The usual way of arriving at it is to get an exact formula for the number of times the "sum++" statement executes, then ignore the low-order terms.
    1. for (int i=0; i < n; i++)
    for (int j=0; j < n * n; j++)
        sum++;

    2. for (int i=0; i < n; i++)
    for (int j=i; j < n; j++)
        sum++;

    3. for (int i=0; i < n; i++)
    for (int j=0; j < i * n; j++)
        for (int k=0; k < n; k++)
            sum++;

    4. for (int i=n; i >= 1; i = i / 2)
    sum++;

  4. (15 points) Weiss Exercise 5.30 [5.23]. Note that your method is supposed to efficiently search the sorted (increasing) array a of integers, looking for an integer i for which a[i] == i and return true if and only if there is such an i.

    You may assume that the array has no duplicate entries, and therefore is strictly increasing. I.e. a[j-1] < a[j] for all j with 0 < j < a.length. You may not assume that all of the integers in the array are non-negative, because then the problem would be boring.

    Show your algorithm and the results of your analysis. Obviously you should try to come up with an efficient algorithm; some of the credit for this problem will be based on your algorithm's efficiency. (Think about it carefully—is O(N) "efficient" for this task? Anyone can write a loop from 0 to a.length.)

  5. (20 points) This is the recursive programming problem, Trees, that we started in class.

    Here are some sample trees:

    This problem is based on one from Object-Oriented Programming in Python, by Goldwasser and Letscher. As they describe it:

    “The general approach is to define a tree … that has a trunk and then two or more branches, which are actually [themselves] trees… By defining a tree with a reference point at the bottom of the trunk, it is easy to rotate a subtree and attach it where desired. Variations can be achieved (as shown in the figure above), by altering the number of branches attached to the trunk or the angle between those branches. In our left two figures, all branches are attached to the top of the trunk. In the right two, the branch points are distributed vertically. The third and fourth figures are identical, except that leaves have been added as a base case, using a small green circle at the end of each branch.”

    Starting code is in your individual SVN repository. Use Subclipse to check out the project Trees. Since this program is graphical, we will primarily evaluate the correctness of your solution based on the display of your program. I’ve put TODO items in the code indicating where you should add your solution and giving some additional direction for each part of the problem. The TODO items are numbered. You should probably try to do them in order.

    When you finish the TODO items, just commit your solution back to your repository. You don’t need to turn in this part on paper.

  6. (15 points) Weiss Problem 5.21 [5.16]. You only need to do the analysis, not an implementation. This one is more complex than any of the parts of problem 5.20 [5.15]. As with our analysis of the cubic algorithm for MCSS in class, you should first derive a (closed-form, no-summation notation) formula for the exact number of times that the sum++ statement executes. Be sure to explain what you are doing, not just write equations. Use your derived formula to state a big-Oh estimate; you can use the usual shortcut of dropping lower-order terms and constant factors only at this last stage.

    You do not have to implement and run the code.

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, but you are not required to turn them in.