CSSE 230
Data Structures and Algorithm Analysis

Written Assignment 2 (82 points)

To Be Turned In

These are to be turned in to the WA2 Drop Box on ANGEL (except problem 4, which is to be committed to your SVN repository). You can write solutions out by hand and scan them (there is a networked scanner in F-217), or create a file on your computer directly .   After you have submitted, click on the drop box again to verify that your submission was successful.

Late days may be used or earned for written assignments.

Problem numbers [in square brackets] are the numbers from the 3rd edition of the Weiss book.

1. (2 points) Weiss problem 2.7 [2.6]   (+ with ' ' and " ")
2. (6 points) Weiss problem 3.13 [3.10]  (legal and illegal references)
3. (18 points) Weiss problems 4.23-4.25 [4.21–4.23]. (generic max and min).  Assume that all of the items are of the same type T, and that this type implements the Comparable interface. (You can write these out by hand or type them. You don’t have to actually compile and run them, although you certainly may do so, if it increases your confidence that your answers are correct). If you do them in Eclipse, you should either print the code and scan it,  or copy it and paste it into your document
   To make your life a little bit simpler, I am giving you the headers for some methods.

   public static <T extends Comparable<? super T>> T min(T arg1, T arg2)

   public static <T extends Comparable<? super T>> T max(T arg1, T arg2)

   public static <T extends Comparable<? super T>> T min(T[] args)

   public static <T extends Comparable<? super T>> T[] max2(T[] args)

   Creating the Generic array for the return value of the last part is also tricky;  here is a way to do it:

   T[] result = (T[]) Array.newInstance(args[0].getClass(), 2);

4. (20 points) Weiss problems 4.44 and 4.45 [4.29 and 4.30]. This isn’t exactly a “written problem”, but it comes from the book and requires very little code (if done correctly), so I’m including it in this written assignment.

   Starting code is in your individual SVN repository. (See the first programming assignment for your repository URL.) Use Subclipse to check out the project CountMatches. It includes JUnit tests for all of the parts. I’ve put TODO items in the code indicating where you should add your solution and giving some additional tips for each part of the problem.

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

   Eclipse provides a view that will list all the outstanding TODO and FIXME comments in a project. From the Eclipse Menus choose Window → Show View → Tasks. The new view should appear at the bottom. You can double click on an item in the task list to jump to the corresponding comment in the code. (Eclipse 3.4.0 had a bug where this view wouldn’t update immediately. If you don’t see any TODO items for the CountMatches project, choose Project → Clean... to regenerate the list for CountMatches.)

5. (10 points). Use the formal definition of big-Oh (see Weiss section 5.4) to show that N² + 3N + 8 is O(N²). That is, find appropriate constants N₀ and c, and show that they work.
6. (6 points) Weiss Problem 5.3 [5.3], part a only. (T₁(N) + T₂(N)). Prove your answer, using the N₀ and c idea from the formal definition of big-Oh. [Hint: the given bounds on T₁ and T₂ tell you something about the existence of an N₀ and c for each of those functions: we could call these numbers N₀₁, c₁, N₀₂, and c₂ ]. Use those constants to come up with appropriate constants for the sum of the functions.)
7. (12 points) For each of the following four code fragments, taken from Weiss problem 5.20 [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++)
          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++;
      

8. (8 points) Weiss Problem 5.14 [5.11].   (running time if we go from size 100 to size 500).

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 Exercise 6.5 [6.5]. (You may have to come back to it a few times before you figure out what to do.) Here is a more detailed explanation:

  The goal of this problem is to implement a collection data type that provides three operations and does them efficiently:

  push(obj); // adds obj to the collection.
  
  obj = pop(); // removes and returns the most recently-added object.
  
  obj = findMin(); // returns the smallest object (assume that all
   // of the objects in the collection are Comparable).
  

  A single stack can do the first two operations in constant time, but not the third. But if our implementation uses TWO stacks to represent a collection, it is possible to do each of the three operations in constant time. Is should be obvious that our new data structure’s push method will have to do more work (than the push operation for an ordinary stack would have to do) in order for findMin to also be a constant-time operation. All you need to do is show the code for the three operations. You may assume that there is already a Stack class that has its own push, pop, and top methods. The code for each of the three methods that you must provide is short. We hope that by making things a bit more specific, it will make it easier for you to get started on this problem.

  To further assist you in understanding this problem, here is a framework in which your answers could go: A class declaration with stubs for the three methods you are supposed to write. Each of those methods should be constant time (no loops or recursion)

  public class StackWithMin<E> {
   // TODO: Give these two stacks names indicating what they are used for:
   private Stack<E> stack1, stack2;
  
   public StackWithMin() {
   this.stack1 = new Stack<E>();
   this.stack2 = new Stack<E>();
  }
  
   public void push(E element) { /* TODO: fill in the details */ }
   public E pop() {/* TODO: fill in the details */ }
   public E findMin() {/* TODO: fill in the details */ }
  }
  

• Weiss exercises 6.26(a)(b), 6.27(a)(b), 6.28(a)(b) [6.12(a)(b), 6.13(a)(b), 6.14(a)(b)]. No implementation required; just the algorithm and analysis.