CMSC 435 Algorithm Analysis & Design
Answers to Homework #
4
ReportCycle(s)
If s.color is white
Iterator itr = s.neighbors();
set s.color to grey
append s to path
while (itr.hasNext( ))
ReportCycle(itr.next( ))
Else if s.color is grey
append s to path
Report path with cycle
return
Report path without cycles
Given a directed graph G = (V, E)
Construct a graph G' = (V, E') where for each edge (u,v) contained in E, include (v, u) in E'
Color all vertices in G' white
Find a vertex s in G' with no incoming edges
If DetermineDAG(s) is true report topologicalOrder
DetermineDAG(s)
If s.color is white
Iterator itr = s.neighbors();
set s.color to grey
append s to cyclePath
while (itr.hasNext( ))
DetermineDAG(itr.next( ))
Else if s.color is grey
append s to cyclePath
Report path with cycle
return false
Append s to topologicalOrder
return true
Prove by induction that the number of nodes in a binary tree with two children is
exactly one less than the number of leaves.
Base case: Consider the root node with 0, 1, or 2 leaves. If the root has no children
then it is a leaf and the tree has 1 leaf and no nodes with 2 children. If the root has
a single leaf, then again the tree has 1 leaf and no nodes with 2 children. If the root
has two children that are leaves, then the tree has 1 node with 2 children and two leaves.
Inductive Hypotesis: P(n): In a binary tree with n nodes (vertices), the number of nodes
with two children is exactly one less than the number of leaves.
Assume P(n) is true, then construct a binary tree containing n+1 nodes by adding a new leaf
to either (1) a parent with only 1 child, or (2) a parent that is a leaf. In case 1, The number
of leaves and nodes with two children both increase by 1. In the second case the number of
leaves and parents with two children both remain the same.
Let DFS and BFS produce the same tree T, and assume that (u, v) is an edge in G that
is not in T. Since T is a depth-first tree, one of the two ends must be an ancestor of the other.
and since T is also a BFS-tree, the distance of each node from some node w in T must be at
most 1. Since the distance from w to u and w to v differs by at most 1, then one of the two,
say u, must be a direct parent of v in T. This means that (u,v) is an edge of T, contradicting
our original assumption.
The claim is true. Let G be a graph with the given properties, and assume by way of
contradiction that it is not connected. Let S be the nodes in its smallest connected component.
Since there are at least two connected components, we have that |S| £ n/2. Now consider
a node u Î S. Its neighbors all lie in S, so its degree can be at most |S| - 1 £ n/2 -1 £ n/2.
This contradicts the assumption that every node has degree at least n/2.
If all paths have equal weight, we can use BFS to find shortest paths from a single source to
other vertices. Adapt BFS and add numbering to each vertex object denoting the number
of incoming shortest paths. For each vertex in G, create a Vertex object with number 0.
NumShortestSWPaths(s)
Set number of Vertex object s to 1
Create a Queue of Vertex references
Add s to Queue
Set destination found flag to false
While destination w is not found
While Q is not empty
Vertex v = Q.dequeue()
Get an iterator, itr, to iterate over the neighbors of v
While itr hasNext
Vertex object u = itr.next()
Add the number of v to the number of u
If u is the destination w
Set destination found to true
Else if destination flag not set to true
Add u to Q
EndWhile
EndWhile
EndWhile
Report number (of paths) of w
Create an Adjacency List for graph G as follows. The Adjacency list is an array, labeled
by the number of the computer and each element contains two fields: The time at which the
computer became infected (all initially 0), and a reference to a linked-list of edges where
each edge contains the identity of the target vertex, and the time at which this vertex (computer)
was first contacted. The adjacency list can be formed in time O(m) the number of edges
(same as the number of triples in the original data). Once the adjacency list is formed, the
algorithm proceeds as follows: Select an initial vertex Ca that is infected at time ta. Perform
a breadth-first search from this source as follows below.
BFS(Ca)
Create a queue, Q
Add Ca to the queue, Q
While Q is not empty
Ck = next vertex removed from Q
For each edge on the adjacency list of Ck
If the time that the target vertex is contacted >= time the
source vertex is infected
If target is uninfected or this time < time of
previous infection
Set time of infections for Ck to this time
Add Ck to Q
EndFor
EndWhile
EndWhile
The time field in the Adjacency list will indicate which computers are infected and when