Compsci 100, Fall 2008, Recitation Nov 7

name: __________________________   login: _____________

name: __________________________   login: _____________

name: __________________________   login: _____________
  1. Consider the code below that returns true if and only if some pair of elements in the array values sums to target.

    public boolean sums2target(int[] values, int target){ for(int k=0; k < values.length; k++){ for(int j=k+1; j < values.length; j++){ if (values[k] + values[j] == target) return true; } } return false; }

    For example, if the array contains (8,4,1,6) then sums2target(array,10) returns true since 4+6 = 10, but sums2target(array,8) returns false since no pair of numbers sums to 8.

    1. What is the complexity of sums2target? Justify your answer.
    2. Explain how to solve the problem, i.e., writing different code so that the method you code runs in O(n log n) time while using O(1) extra storage (you can change the order of the int values in the array).
    3. A student claims the code below is better than either solution above. Provide a reason for the student being correct and a reason for the student being wrong.

      public boolean sums2target(int[] values, int target){ HashSet<Integer> set = new HashSet<Integer>(); for(int i : values) set.add(i); for(int i : values) if (set.contains(target-i)) return true; return false; }
  2. A heap is stored in an array as we discussed in class so that children of the node with index k are stored at indexes 2*k and 2*k+1 (if there are children).

    In the diagram below the heap has 9 elements, so only values with indexes 1-9 (inclusive) are considered part of the heap. heap

    Write the method lessThanCount that returns the number of values in heap that are less than parameter key. You may want to write an auxiliary method to help -- your auxiliary method should have a parameter indicating the root of the (sub)heap being checked, initially this will be 1. Your code should run in time O(k) where k is the number of values less than key. For example, for the heap above lessThanCount(heap,9,13) should return 3 since three of the nine values in the heap are less than 13.

    /** * @param size is number of valid values in heap * @return number of values in heap less than key */ public int lessThanCount(int[] heap, int size, int key){ }
  3. Consider the HuffmanDecoding APT. Part of a solution is shown below: public String decode2(String archive, String[] dictionary){ String ret=""; while (archive.length() > 0){ for(int k=0; k < dictionary.length; k++){ String s = dictionary[k]; if (archive.startsWith(s)){ ret += (char)('A'+k); // code missing here } } } return ret; }
    1. Describe what the missing line of code must do to ensure that the outer-while loop eventually terminates. What line of code will do this?
    2. If A is the number of characters in archive and D is the size of the dictionary, what is the big-Oh running time of the code above?
      An alternate solution to the APT is given the incomplete code below. public class TreeNode{ String info; TreeNode left; TreeNode right; TreeNode(String s){ info = s; } } public String decode(String archive, String[] dictionary){ TreeNode root = new TreeNode("dummy"); for(int k=0; k < dictionary.length; k++){ // code here to add dictionary[k] to Huffman-tree 'root' } String ret = ""; TreeNode current = root; for(char ch : archive.toCharArray()) { if (ch == '0') current = current.left; else current = current.right; if (current.left == null && current.right == null){ ret += current.info; current = root; } } return ret; }
    3. In terms if A and D what is the big-Oh running time of the code above? Ignore the lengths of strings in the dictionary, they're effectively constant.
  4. Old Test Questions For Practice