Compsci 100, Spring 2009, April 10 Recitation

name: __________________________   login: _____________

name: __________________________   login: _____________

name: __________________________   login: _____________

Huff Stuff

  1. Suppose you've created a Huffman tree whose root is stored in TreeNode myRoot. You want to store all the Huffman codings for each value stored in the leaves of this tree, so you write this private method: private void createCodings(TreeNode root, String path) { }
    1. You call this initially with createCodings(myRoot,""). Explain in words what the purpose and relationship of parameter path is in relation to parameter root.
      
      
      
      
      
      
      
      
      
    2. Here are the instance variables from the definition of TreeNode: public int myValue; public int myWeight; public TreeNode myLeft; public TreeNode myRight; Given these, what are the two recursive calls for non-leaf nodes in createCodings?
      
      
      
      
      
      
      
    3. The base case for createCodings is a leaf node. When the base case is identified, the coding/path to the leaf is stored in a map. Write the code that identifies a leaf and stores the path appropriately in instance variable: a Map myCodes
      
      
      
      
      
      
      
      
      
      
  2. Suppose you have these instance variables in a SimpleHuffProcess implementation: int[] myFreqs; // count of # occurrences of every 8/ALPH_SIZE bit chunk Map<Integer,String> myCodes; // as described in previous question Write the method totalCodedBits that returns the number of bits that will be used in the compressed file for the data stored in the instance variables above. Except for the header information this is the total number of bits used to store the compressed file. You compute this from frequencies of each 8-bit chunk and the length in bits of each code for the chunk. Assume that 8-bit chunks that don't appear in the data, i.e., which have frequencies of zero, are not represented in the map myCodes. /** * Return total # bits needed in compressed file not-including header info. * @return ... */ private int totalCodedBits() { }
  3. If the PSEUDO_EOF chunk is not represented in myFreqs how would you modify the code above to account for its length in re-writing totalCodedBits?
    
    
    
    
    
    
    
    
    
    


Graph Stuff

The graph below is used in several questions.

*

  1. Draw diagrams for both the adjacency list and adjacency matrix representations of the graph with directed edges as shown above. For the adjacency matrix use either T/F or 0/1 to indicate an edge.
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
  2. Write out a possible vertex ordering for both depth-first and breadth-first traversals of the graph with directed edges as shown above starting at vertex 0 (there's more than one correct answer for each).
    
    
    
    
    
    
    
    
    
  3. In the adjacency-list representation of a directed graph (with E edges and V vertices), what is the big-Oh complexity of how long does it take to compute the out-degree of every vertex (combined time)? How long does it take to compute the in-degree of every vertex (combined time)? Give your answers using notation like O(VE) or O(V) in terms of both V and E. Briefly justify your answers.
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    Graph Connectivity

  4. A connected graph is one in which every pair of its vertices is connected by some path. In class we talked about using DFS or BFS to determine if a graph is connected. The method below is the standard DFS we discussed in class, use it with a modified name and return type (now boolean) by adding lines(s) so that the method correctly determines if a graph is connected (the instance variable myGraph is shown too).

    Map<String, List<String>> myGraph = new HashMap<String,List<String>>(); public boolean isConnected(String vertex){ Set<String> visited = new TreeSet<String>(); Stack<String> st = new Stack<String>(); st.push(vertex); visited.add(vertex); while (st.size() > 0){ String s = st.pop(); for(String neighbor : myGraph.get(s)){ if (!visited.contains(neighbor)){ visited.add(neighbor); st.push(neighbor); } } } return }
  5. To determine if a graph has a cycle starting from a specific vertex V, a breadth- or depth-first search is performed. If V is visited during the search, the graph has a cycle starting from V, otherwise it does not.

    Write a modified DFS to determine if a graph has a cyle starting from the parameter to the method.

    /** * Returns true if graph has a cycle starting from start, returns * false otherwise. * @param start is beginning of search for cycle */ Map<String, List<String>> myGraph = new HashMap<String,List<String>>(); public boolean hasCycle (String start) { }
  6. Discuss a solution to the Circuits APT in terms of a high-level description of using DFS to keep track of the weight of the path being followed in the DFS. Since the graph is acyclic you don't need a visited set.

    Draw a graph that shows you must visit a node more than once, e.g., where the first path followed through a node isn't as long as a subsequent path.