CSSE 230
Data Structures and Algorithm Analysis

Written Assignment 4 - 90 points

To Be Turned In

Questions 1-6 and 8 are to be submitted to the drop box on ANGEL and question 7 committed to your repository. Late days may be used for written assignments - if either part (dropbox or repo) is late, you will be charged a late day.

1. (20 points) Weiss Exercise 5.26 [5.20]. In order to make the calculations simpler, you may assume that N = 2^k - 1 for some integer k ≥ 0, and that all elements are equally likely to be the one we are searching for. Note that the problem only deals with successful searches (where the item we are looking for is actually in the array).

   Hint: For each i, count how many of the array elements will be found after binary search examines exactly i array elements. (For example, the middle element is the only one to be found after examining one array element, and there are two elements that can be found after two probes into the array.) Use a summation to help you find the average.

   Potentially useful fact: Depending on how you work this problem, you may find the following useful:

   

2. (15 points) Suppose we execute this pseudocode:

   String  in = "ABCD";
   String out = ""; 
   Stack stack = new empty stack;
   while ( in != "" || stack is not empty)
       randomly choose ONE of the following two operations:
           - remove the first character from in and push it on  stack, or
           - pop stack and add the character that was popped to the end of out.
   

   Note that this process will always result in some permutation of ABCD in the output.   Recall the "railroad diagram" discussion from the Session 10 PowerPoint Slides.

   1. (5 points) Display two permutations of ABCD that are NOT possible final values of out.
   2. (10 points) How many different permutations of ABCD are possible final values for out?

3. (10 points) It is useful to have a unique representation of binary trees that can be written compactly. For simplicity, we assume that each node of the tree will contain one Character. We represent a tree by a pair of strings, which I call chars and children. The chars is a pre-order listing of the contents of the nodes. The children string tells about the children of the corresponding node from chars as follows:

   2	The node has two children.
   0	The node has no children.
   L	The node only has a left child.
   R	The node only has a right child.

   For example:

   chars = "+a*-bcd"; children = "2022000";
   represents the tree in Weiss Figure 18.11 (a)

   chars = "7215349"; children = "220LR00";
   represents the tree in Weiss Figure 19.4 (a).

   1. What are the values of chars and children for the tree below?

      

   2. For a different tree we have:

         chars = "THEQUICKBROWN";
      children = "2R220002R0RL0";
      

      Show the order of the nodes in an in-order traversal of the tree.

4. (10 points)

   THEQUICKLAZYFOX is the pre-order traversal of a tree (one character per node).

   QIUCEHLAZKFYTXO is the in-order traversal of the same tree.

   What is the order of the nodes in the level-order traversal of this tree?

5. (5 points) Consider a PostOrder iterator (see Weiss §18.4) for the binary tree shown on page 715[657] (Figure 19.34). Using the notation of Figure 18.25, show the contents of the stack at the time when 55 is the node whose value is about to be output.

6. (10 points) If tree is a BinaryTree with N nodes, and itr is a PostOrder iterator for that tree, suppose that we run the following code:

   for (itr.first(); itr.isValid(); itr.advance()) {
   	System.out.println(itr.retrieve());
   } 
   

   Is the running time for this code Θ(log N), Θ(N), Θ(N log N) or Θ(N²)?

   Explain your answer.

   Be sure that your explanation accounts for how the postorder iterator’s stack is used during the execution of the code. The code for the PostOrder class can be found in Section 18.4 (spanning three different pages).
   

7. (10 points) Exercise 6.23 [this problem did not appear in the 3rd edition]. Starting code is in the ChangeList project in your repository. Commit to your repository when you have completed it.
   Here is the problem statement from the book: Method changeList replaces each String in the list by both its lower-case and upper-case equivalents. Thus if the original list contains [Hello, NewYork], the modified list will contain [hello, HELLO, newyork, NEWYORK].  Use the ListIterator interface's add and remove methods to write an efficient implementation of this method for linked lists.
   public static void changeList(List<String> theList) .  Note that both ListIterator and LinkedList are defined in the java.util package.
   
8. (10 points) In this problem, you will get practice writing a simple proof that uses mathematical induction. Recall the basics of (ordinary) induction: Let p be a predicate (in this case, a function from int to boolean). Let n₀ be any integer. To show that p(n) is true for all integers n≥n₀, we need to show two things:
   1. p(n₀) is true.
   2. for any k≥n₀, if p(k) is true, so is p(k+1).   To show this part, we write down the assumption that p(h) is true, and use it to show that p(k+1) is true.
   This page has a nicely-explained simple proof by induction. And this page has more examples, with more detailed explanations.  Mimic one of the examples from one of those pages  to show (in your own words) that for all n≥0, 1 + 4 + 9 + ... + n² = n(n+1)(2n+1)/6 . 

   Notes:

   1. Don't just write equations. Also write some words to explain what you are doing.
   2. Some students have been erroneously taught that you do an induction proof of a property that involves an equation in the same style you would use to solve an equation: writing down the equation you want to prove, and then performing the same operation on both sides until you get a true statement. This is at best very bad style, and it can sometimes lead to "proving" something that is not really true. Instead, start with "one side" of the thing you want to prove, and algebraically manipulate it (including using the induction assumption at some point) until you get what you want  on the other side.

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.

• (5 points) Problem 6.37[6.22]. You do not have to do this on a computer, but you may do so if it increases your confidence that your code is correct. You must include your code in your submission document. You will (probably) need to refer to the Javadoc documentation of java.util.Map to complete this problem.

• Weiss exercise 6.2 [6.2]. You can just write the code for part (a) out by hand if you wish, but I recommend getting it working in Eclipse and printing out your code. Here is some code that you can use to test your method if you wish:

  public static void main(String[] args) {
    Collection<Collection<String>> a = new ArrayList<Collection<String>>();
    String[][] arrays = {{"abc", "def", "ghi"}, 
                         {"xyz", "uvw", "abc", "abc"}, 
                         {"a", "ab", "abc", "xyz", "abc"}};
    for (String[] sArray : arrays){
      Collection<String> a1 = new ArrayList<String>();
      for (String s: sArray)
        a1.add(s);
      a.add(a1);
    }
    System.out.println(count(a, "abc"));
  } 
  

• Other good problems to think about: 15.1[15.1], 15.3[15.3], 15.5[15.5], 15.9[15.9], 15.10[15.10], 15.12[15.12], 15.13[15.13], 17.3[17.3], 17.4[17.4], 17.5[17.5], 17.6[17.6] , 17.16[17.16]