CSSE 230
Data Structures and Algorithm Analysis

Written Assignment 3

To Be Turned In

These are to be turned in as hard copy. You can write solutions out by hand, or write them on your computer and print them.

Papers must not have ragged, spiral-notebook edges. Multiple page solutions must be stapled. Solutions not following these guidelines will be returned ungraded. I regret this rigidity, but it is necessary given the number of students in CSSE 230 this term.

Late days may not be used for written assignments.

1. (9 points) Weiss Problem 5.3, parts b–d. If a statement is always true, explain why using the N₀ and c idea from the formal definition of big-Oh. If a statement can be false, give an example of functions T₁ T₂, 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. You’ll find the solution to part a of this problem posted on ANGEL as part of the WA2 solutions.)
2. (8 points) Weiss Problem 5.12.
3. (12 points) For each of the following four code fragments, taken from Weiss problem 5.15, give a Big-Oh analysis of the running time. By “analysis” I mean that you should give the Big-Oh answer and explain how you arrived at it.

   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=0; j < i; j++)
              sum++;
      

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

   4. for (int i=1; i < n; i = i * 2)
          sum++;
      

4. (15 points) Weiss Exercise 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? Any Schlemiel 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, bonus) Weiss Problem 5.16. This one is more complex than any of the parts of problem 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.

   The following formulas for series sums may be helpful:

   

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.

• Weiss Problem 1.14
• Weiss Problem 2.12. You do not have to do this on your computer, but you are welcome to do so if you wish, and paste the code into your document (or just print it if you did the rest of the problems by hand). You should not use high-level tools like StringTokenizer to do this, but should use the basic String operations (indexOf and substring may be particularly helpful). The following code and output may help clarify what the method is supposed to do:

  public static void main(String[] args) {
      String[] stringList = split("Here is a short sentence.", " ");
      for (String s : stringList)
         System.out.println(s);
      System.out.println("-------");
      stringList = split("abracadabra.", "bc");
      for (String s : stringList)
         System.out.println(s);
  

• Weiss Problem 3.12

• This problem is inspired by Weiss exercise 5.8, but is different. That problem examines the efficiency of computing X^N, where X is a double value and N is an integer. That algorithm is O(N). It turns out we can do a lot better; there is an algorithm that is O(log N). Write and test code that does this.

  Hint: Base your algorithm on the binary representation of N. For example, X¹¹ = X¹*X²*X⁸ (Note that 11 has one-bits representing 1, 2, and 8). So you can write N as a sum of powers of 2. Start with power=X, and keep squaring power to get the original X to those powers of 2. Only multiply X⁽²ⁱ⁾ into the product if the ith bit of the binary representation of N is 1. Your program should ask the user for X and N, and print X^N.

  Another hint: It is probably easier to do this recursively.

  You can just write the code out by hand if you wish, but I recommend getting it working in Eclipse.

• Weiss exercise 6.4.

• Weiss Exercise 6.18. Your program should read strings (one per line) form standard input, and write Strings (one per line) to standard output. The alphabetical part of the sort should ignore case. Hint: Use a two-argument overloaded version of java.util.Collections.sort().

  Sample Run:

  Enter the strings, one per line (CRTL Z to end):
  Come
  and
  sit
  by
  my
  side,
  if
  you
  love
  me
  Do
  not
  hasten
  to
  bid
  me
  adieu
  Just
  remember
  the
  Red
  River
  Valley
  And
  the
  cowboy
  who
  loved
  you
  so
  true
  
  SORTED LIST OF STRINGS:
  by
  Do
  if
  me
  me
  my
  so
  to
  and
  And
  bid
  not
  Red
  sit
  the
  the
  who
  you
  you
  Come
  Just
  love
  true
  adieu
  loved
  River
  side,
  cowboy
  hasten
  Valley
  Remember