Compsci 100, Spring 2009, April 10 Recitation
name: __________________________ login: _____________
name: __________________________ login: _____________
name: __________________________ login: _____________
Huff Stuff
 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) {
}
 You call this initially with
createCodings(myRoot,"")
. Explain in words what the
purpose and relationship of parameter
path
is in relation to parameter root
.
 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 nonleaf nodes
in createCodings
?
 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
 Suppose you have these instance variables in a
SimpleHuffProcess
implementation:
int[] myFreqs; // count of # occurrences of every 8/ALPH_SIZE bit chunk
Map 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 8bit chunk and the length in bits of each code
for the chunk. Assume that 8bit 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 notincluding header info.
* @return ...
*/
private int totalCodedBits() {
}
 If the
PSEUDO_EOF
chunk is not represented
in myFreqs
how would you modify the code above to account
for
its length in rewriting totalCodedBits
?
Graph Stuff
The graph below is used in several questions.

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.

Write out a possible vertex ordering for both depthfirst and
breadthfirst traversals of the graph with directed edges as shown above
starting at vertex 0 (there's more than one correct answer for each).

In the adjacencylist representation of a directed graph (with
E edges and V vertices),
what is the bigOh complexity
of how long does it take to
compute the outdegree of every vertex (combined time)? How long does it take to
compute the indegree 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

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> myGraph =
new HashMap>();
public boolean isConnected(String vertex){
Set visited = new TreeSet();
Stack st = new Stack();
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
}

To determine if a graph has a cycle starting from a specific
vertex V, a breadth or depthfirst 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> myGraph =
new HashMap>();
public boolean hasCycle (String start)
{
}
 Discuss a solution to the
Circuits APT
in terms of a highlevel 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.