HW6 Solutions Page
Return to
homework page.
9.1 Find a topological ordering in graph 9.11.
(Pi) := pass i through topsort alg
(P1) (P2) (P3) (P4)
Queue Order Queue Order Queue Order Queue Order
s empty g s d h s g h a s g d
(P5) (P6) (P7)
Queue Order Queue Order Queue Order
a s g d h b e s g d h a e s g d h a b
(P8) (P9) (P10)
Queue Order Queue Order Queue Order
i s g d h a b e f s g d h a b e i c s g d h a b e i f
(P11) (P12)
Queue Order Queue Order
t s g d h a b e i f c empty s g d h a b e i f c t
9.11 Find the maximum flow in graph 9.11
We start first with the all zero flow and a residual graph which is
the original graph together with 0 weighted back edges.
We then keep finding the path from s to t with as whose minimally weighted
edge is as large as possible. We then add this weight to the edges along
this path in the flow graph and recompute the residual graph.
(or subtract from a forward edge if edge is a back edge). We repeat this
process until s and t are connected in the residual graph only by paths
which traverse an edge of weight 0.
Pass 1: We add 4 along path s, g, h, i, t in flow graph recompute residual.
Pass 2: We add 3 along path s, d, e, f, t in flow graph recompute residual.
Pass 3: We add 2 along path s, g, a, e, c, t in flow graph recompute residual.
Pass 4: We add 1 along path s, d, a, b, c, t in flow graph recompute residual.
Pass 5: We add 1 along path s, a, b, c, t in flow graph recompute residual.
At this point s in residual only has 0 edges going out of it and the
algorithm stops. You can use the above five lines to draw what the max flow
looks like. The flow is 11.
9.54 Show that the clique problem is polynomially reducible to vertex cover.
Let G=<V,E> and K be an instance of clique. Let G' = <V, E'>
where E' = V x V - E. That is, e in V x V is in E' iff e is not in E.
Suppose G has a clique H of size K. Then none of the vertices in H
will share an edge in G' so by picking the remaining |V|-K
vertices in G' we are guaranteed to have vertex cover in G'.
Similarly, if there is a vertex cover of size |V|-K in G', and we look
at the K vertices not in this cover then they can't share an edge
or we would need a larger vertex cover. Therefore in G these vertices
would be a clique.
Thus, the problem of whether G has a clique of size K is answered
`Yes' iff the problem of whether G' has a vertex cover is answered `Yes'.
The construction of G' from G can easily be done in linear time in
the size of G and K and so this is a polynomial reduction.
10.3 We want to contruct a Huffman code from the following table:
Char Frequency
================
: 100
space 605
newline 100
, 705
0 431
1 242
2 176
3 59
4 185
5 250
6 174
7 199
8 205
9 207
We construct the Huffman tree by first putting each of the
the above into its own tree. Then repeatedly combining the
two smallest trees we've constructed so far:
To begin we make the tree: Step 1:(159)
/ \
(59) (100)
[3] [:]
Step 2: Step 3: Step 4: Step 5:
(259) (350) (384) (413)
/ \ / \ / \ / \
(159) (100) (174) (176) (185) (199) (205) (207)
/ \ newline [6] [2] [4] [7] [8] [9]
(59) (100)
[3] [:]
Step 6: Step 7: Step 8: Step 9:
(492) (609) (797) (923)
/ \ / \ / \ / \
(242) (250) (259) (350) (384) (413) (431) (492)
[1] [5] Step2 Step3 Step4 Step5 0 Step6
Step 10: Step 11: Step 12: Step 13: Step 14:
(1097) (1314) (1720) (2411) (4131)
/ \ / \ / \ / \ / \
(492) (605) (609) (705) (797) (923) (1097) (1314) (1720) (2411)
Step6 space Step7 , Step8 Step9 Step10 Step11 Step12 Step13
Now we extract code by following the branches down the tree to symbols.
Going left means a 0; going right means a 1.
Symbol Code
3 110000
: 110001
newline 11001
6 11010
2 11011
4 0000
7 0001
8 0010
9 0011
1 0110
5 0111
0 010
space 101
, 111
//cs146sec6hw6file1 - a word morphing program
import java.util.*;
import java.io.*;
/**
This class is a Java application for determining if two Strings
are equivalent to each other via single letter substitutions
each of which is a word in a given dictionary. The program is
run from the command line with the line
java cs146sec6hw6file1 sourceword targetword dictionary
It also provides static methods for computing shortest
paths between two vertices in a graph.
*/
public class cs146sec6hw6file1
{
/**
Driver for application. Makes sure all command line args are there
Then reads in the dictionary, sets up graph, and look for short
path. If it exists it prints it out.
@param args - command line arguments
*/
public static void main(String[] args)
{
if(args.length < 3)
{
System.out.println("Need to supply three command line args.\n"+
"java cs146sec6hw6file sourceword targetword dictionary.");
}
if(!readGraph(args[0], args[1], args[2]))
{
System.out.println("No.");
}
unweighted((Vertex)graph.get(targetIndex));
if(((Vertex)graph.get(sourceIndex)).dist < INFINITY)
{
System.out.println("Yes.");
outputPath(sourceIndex);
}
else System.out.println("No.");
}
/**
Creates a graph based on the words in the file diciotnary
The graph is an ArrayList of vertices
where each vertex has a hashset of adjacent vertices.
Two words are adjacent if they are the same length and differ
in at most one position.
@param sourceWord - word we are trying to morph
@param targetWord - what we are trying to change it to
@param dictionary - filename of a dictionary of word to use in morph
@return - whether or not source and target words in dictionary
*/
public static boolean readGraph(String sourceWord, String targetWord,
String dictionary)
{
String line;
sourceIndex = -1;
targetIndex = -1;
int index = 0;
graph = new ArrayList();
try
{
BufferedReader in = new BufferedReader(
new FileReader(dictionary));
while((line = in.readLine()) != null)
{
if(sourceWord.equals(line)) sourceIndex = index;
if(targetWord.equals(line)) targetIndex = index;
Vertex v = new Vertex(line, null, 0);
graph.add(v);
calculateAdjacentTo(v);
index++;
}
}
catch(Exception e)
{
System.err.println("Couldn't read that file.");
e.printStackTrace();
System.exit(1);
}
if(sourceIndex == -1 || targetIndex == -1)
return false;
INFINITY = index;
for(int i = 0; i < index; i++)
((Vertex)graph.get(i)).dist = INFINITY;
return true;
}
/**
This functions updates the dist field of the vertices in graph
according to their distance from s. Also updates their path
variables according.
Preconditions: need dist's to be initially INFINITY and path's null
@param s - source vertex for search
*/
public static void unweighted( Vertex s)
{
ArrayList queue = new ArrayList();
Vertex v, w;
if (s == null ) return;
queue.add(s);
s.dist=0;
while(!queue.isEmpty())
{
v=(Vertex)queue.remove(0);
Iterator adjIterator = v.adjacent.iterator();
while(adjIterator.hasNext())
{
w = (Vertex)adjIterator.next();
if(w.dist == INFINITY)
{
w.dist = v.dist + 1;
w.path = v;
queue.add(w);
}
}
}
}
/**
Prints to standard output the path from index in the graph
to the Vertex targetIndex in graph
@param index - index of node want to compute path from
*/
public static void outputPath(int index)
{
Vertex v = (Vertex)graph.get(index);
while (v != null)
{
System.out.println(v.toString());
v = v.path;
}
}
/**
This inner class represents Vertex in our graph. We can
subclass it and its adjacency method if we would like
to compute shortest paths in different kinds of graphs.
*/
public static class Vertex
{
/**
Contructor stores Vertex data.
@param data - what we storing in the Vertex (usually a String)
@param path - next vertex on path to target.
@param dist - distance to target.
*/
public Vertex(Object data, Vertex path, int dist)
{
this.data = data;
this.path = path;
this.dist = dist;
adjacent = new HashSet();
}
/**
@return - data stored in this vertex converted to a string
*/
public String toString()
{
return data.toString();
}
/**
Used to determine if two vertices are adjacent to each other.
@param w - vertex we are comparing with current one.
@return - true if toString() of this vertex differ from that
of w in at most one place.
*/
public boolean isAdjacent(Vertex w)
{
String myData = data.toString();
String wData = w.data.toString();
if(myData.length() != wData.length()) return false;
int count = 0;
for(int i = 0; i < myData.length(); i++)
{
if(myData.charAt(i) != wData.charAt(i)) count++;
}
if(count > 1) return false;
return true;
}
protected Object data; // data stored in vertex. In our app a String
protected Vertex path; //next vertex in path to target
protected int dist; // distance to target
protected HashSet adjacent; //all vertices adjacent to this vertex
}
/*
Used by readGraph to add v to all the vertices in the graph
which are adjacent to v and to create v's adjacency list.
*/
static void calculateAdjacentTo(Vertex v)
{
Iterator vertices = graph.iterator();
while(vertices.hasNext())
{
Vertex w = (Vertex)vertices.next();
if( w != v && w.isAdjacent(v))
{
if(!v.adjacent.contains(w)) v.adjacent.add(w);
if(!w.adjacent.contains(v)) w.adjacent.add(v);
}
}
}
protected static ArrayList graph; //stores graph of dictionary
protected static int sourceIndex; //index in graph of sourceword
protected static int targetIndex; //index in graph of targetword
protected static int INFINITY; // graph.size()
}