Compsci 100, Fall 2009, Recitation 10/30


Name: _____________________  Netid: _________________

Name: _____________________  Netid: _________________
 
Name: _____________________  Netid: _________________

Trees and Recurrences

This is continued from last week's recitation.

  1. Two binary trees s and t are isomorphic if they have the same shape; the values stored in the nodes do not affect whether two trees are isomorphic. In the diagram below, the tree in the middle is not isomorphic to the other trees, but the tree on the right is isomorphic to the tree on the left.

    *

    Write a method isIsomorphic that returns true if its two tree parameters are isomorphic and false otherwise. You must also give the big-Oh running time (in the average case, assuming each tree is roughly balanced) of your method with a justification. To determine the running time you should write a recurrence. Express the running time in terms of the number of nodes in trees s and t combined, i.e., assume there are N nodes together in s and t with half the nodes in each tree. Write a recurrence to justify the runtime complexity.

    Hint: a null trees is not isomorphic to a non-null tree, but two null trees are isomorphic. That's most-to-all of the base case you'll need. If the two trees have isomorphic left subtrees and isomorphic right subtrees, then they must be isomorphic.

    /** * Retrns true if s and t are isomorphic, i.e., have same shape. * @param s is a binary tree (not necessarily a search tree) * @param t is a binary tree * @return true if and only if s and t are isomporphic */ public static boolean isIsomorphic(TreeNode s, TreeNode t) { if (s == null && t == null) return true; // consider the case when one of s and t is null here // consider here the both non-null case, make recursive calls }
  2. Two trees s and t are quasi-isomorphic if s can be transformed into t by swapping left and right children of some of the nodes of s. The values in the nodes are not important in determining quasi-isomorphism, only the shape is important. The trees below are quasi-isomorphic because if the children of the nodes A, B, and G in the tree on the left are swapped, the tree on the right is obtained.

    *

    Write a method isQuasiIsomorphic that returns true if two trees are quasi-isomorphic. You must also give the big-Oh running time (in the average case, assuming each tree is roughly balanced) of your method with a justification. Express the running time in terms of the number of nodes in trees s and t combined as with the previous problem. Write a recurrence to do this. The recurrence isn't one of the standard five recurrences we've seen in notes, for now just write the recurrence rather than solving it.

    The difference in quasi-isomorphism compared to isomorphism is that if the left subtree of one tree is quasi-isomorphic to the right subtree of the other, the trees might be quasi-isomorphic. Of course if the left subtrees are quasi-isomorphic the trees could be quasi-isomorphic as well.

    /** * Returns true if s and t are quasi-isomorphic, i.e., have same shape. * @param s is a binary tree (not necessarily a search tree) * @param t is a binary tree * @return true if and only if s and t are quasi-isomporphic */ public static boolean isQuasiIsomorphic(TreeNode s, TreeNode t) { }

    BadNeighbors

  3. The second part of the recitation is about the BadNeighbors APT

    One idea in solving the bad neighbors APT is to write a helper routine -- one that will use an extra parameter to express a recursive solution. The method solve returns the best sum using elements from donations that occur at locations index or later. As in the APT, adjacent elements can't both contribut to the best sum. But in writing solve we won't worry about the first element being adjacent to the last element. The APT method maxDonations will just return solve(donations,0)

    private int solve(int[] donations, int index) { }
    1. If index is too large the sum returned is zero since no donations are possible. Explain why and write the code to deal with this base case.
    2. As with any recursive routine, the method will make recursive calls and then solve one case: dealing with donations[index]. Sometimes more than one recursive call is needed.

      If the element donations[index] is not used, then a recursive call of solve(donations,index+1) provides the best sum from donations. Explain why this is the case in words, e.g., why index+1 is the right value when donations[index] isn't used.

      int bestWithout = solve(donations,index+1);
    3. If the element donations[index] does contribute/is used in the best sum, then write the expression including the recursive call that sets the value as shown below; write one line: int bestWith = Use words to explain the code you wrote.

    4. Given the answers to the questions above, complete the entire method solve that returns the highest sum using values from index or later, i.e., put the statements together. Note that the method doesn't "worry" about the first element being adjacent to the last. private int solve(int[] donations, int index) { }
    5. Given the solution above, continue the program below which uses solve. Explain why the answers printed should be the same even though the arrays are different. public class BadNeighbors { public int solve(int[] donations, int index){ // not shown } public int maxDonations(int[] donations){ return solve(don,0); } public static void main(String[] args){ BadNeighbors bn = new BadNeighbors(); int[] a = {10,3,2,5,7,8}; int answer = bn.maxDonations(a); System.out.printf("answer = %d\n", answer); } }
    6. The code above will print the value 23, obtained from 10+5+8, because solve doesn't consider the 10 and 8 to be adjacent. To fix this suppose the code below is used: public int maxDonations(int[] donations){ int[] smaller = new int[donations.length-1]; for(int k=0; k < smaller.length; k++){ smaller[k] = donations[k]; } return solve(smaller,0); } This code will print the value 19 as expected. However, a small change to the array in main as shown prints the answer 16. public static void main(String[] args){ BadNeighbors bn = new BadNeighbors(); int[] a = {3,2,5,7,8,10}; int answer = bn.maxDonations(a); System.out.printf("answer = %d\n", answer); } Explain why the answer should be 19, but why 16 is printed. Develop a way of making an additional call to solve in the body of maxDonations to help obtain the right answer to be returned from maxDonations.
  4. The code developed above should be correct when finished, but it will time out on some of the sample test data. Write a recurrence for solve and guestimate its solution. Then discuss how to use memoizing to avoid recomputing the same thing many times and "fix" time-out issue.