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:
<![CDATA[
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:
<![CDATA[
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?
- 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:
<![CDATA[
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.
<![CDATA[
/**
* Return total # bits needed in compressed file not-including 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 re-writing 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 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).
-
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
-
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).
<![CDATA[
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
}
]]>
-
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.
<![CDATA[
/**
* 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)
{
}
]]>
- 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.