COMS 311: Homework 3

COMS 311: Homework 3

Total Points: 100
Submission format. Your submission should be in pdf format. Name your submission file:
<Your-net-id>-311-hw3.pdf. For instance, if your netid is asterix, then your submission file
will be named asterix-311-hw3.pdf.
Rules for Algorithm Design Problems.
1. Unless otherwise mentioned, for all algorithm design problems, part of the grade depends on
runtime. Better runtime will lead to higher grade.
2. Unless otherwise mentioned, for all algorithm design problems, you are required to write some
justification of why your algorithm correctly addresses the given problem.
3. You will write pseudo-code for your algorithm. It should not be some code in a specific
programming language (e.g., Java, C/C++, Python).
4. You can use any operation already covered in class-lectures in your solution without explicitly
writing the algorithm. However, you need to use them appropriately (i.e., indicate the inputs
to and outputs from these algorithms). For instance, you can use heapifyUp with input as
the index of a heap element and you do not need to write the code for heapifyUp.
Problems 1–4 are 25pts each. Extra Credit Problem is 20pt.
1
1. In the indomitable gaulish village, druid Getafix had to make several trips to all village houses
everyday. There are walkways between houses in this village such that Getafix can take several
walkways to any house and also from any house Getafix can take several walkways to come
back to his house. All walkways in this village are directed, i.e., one may not be able to take
the same walkway to go back and forth between two houses. Everyday Getafix has to do the
following:
for every house h
Getafix walks from his house to h
Getafix delivers magic potion to the house members
Getafix walks from h to his own house
Write an algorithm to determine the shortest distance Getafix walks everyday. You can
assume that every walkway is of length L. The input to your algorithm is the village map
with houses and walkways between them. Here is an example scenario:
D
2 1
3
4
DFS(v, prevD)
dist(v) = min(prevD + L,dist(v))
if (!visited(v))
for all n in v.neighbors
DFS(n, dist(v))
Getafix(V, E, D)
total = 0
for all v in V
visited(v) = 0
dist(v) = infinity
DFS(D, 0) // phase 1: distance to
for all v in V
total += dist(v)
Reverse(E)
for all v in V
visited(v) = 0
dist(v) = infinity
DFS(D, 0) // phase 2: distance back
for all v in V
total += dist(v)
return total
2
First, Getaphix finds the shortest path to all houses using DFS and a distance property.
Next we reverse the edges in the graph. Now, DFS actually finds the shortest path back from
all other nodes because the graph is reversed. Summing all these distances should give the
shortest path for Getafix.
2 DFSs take O(V + E), 2 resets take O(V), and 1 reversal takes O(E). Summing these puts
Getaphix in O(V + E).
3
2. Given a directed graph G = (V, E), a vertex is k(< |V |) strong if k vertices can reach the
vertex (excluding itself). Write an algorithm to verify the existence of a |V | −1 strong vertex
in a given graph. The input to your algorithm is a directed graph.
HasStrong(V, E)
SCCs = Tarjan(V, E)
V’ = all individual components in SCCs
E’ = unique edges connecting components in SCCs
leaf = null
for all c in V’
if |(c, u)| == 0 and leaf != null
return false
leaf = c
return true
First we find the SCCs of the input. Condensed graphs consisting of SCCs are DAGs, so
there will at least be one node with 0 neighbors, aka a leaf. If there are multiple leafs, then
these leafs cannot reach other, which gurantees that none of the nodes in the leaf is strong. If
there is a single leaf, then all other nodes in the previous components can reach it, and that
leaf is an scc, so all nodes in that leaf is reachable by all other nodes aka strong.
Tarjan runs in O(V + E), and checking the neighbors of each SCC is O(V). This puts HasStrong in O(V + E)
4
3. Given a connected undirected graph, write an algorithm for verifying the existence of simple
cycle in the graph. A simple cycle is defined as a sequence of vertices v1, . . . , vk, where all
vertices are distinct and ∀i ∈ [1, k − 1],(vi
, vi+1) ∈ E and (vk, v1) ∈ E. The input to your
algorithm is a connected undirected graph.
DFS(v, prev)
visited(v) = 1
cycle = 0
for all n in neighbors(v)
if n != prev and visited(v)
return true
if DFS(n, v) // separate if statements for earlier termination
return true
return false
HasSimpleCycle(V, E)
for each v in V
visited(v) = 0
for each v in V
if !visited(v)
if DFS(v, null)
return true
return false
This is simply a DFS for undirected graph that terminates if it finds a vertex that’s already
been reached. This would indicate a cycle, returning true. If no DFS calls return true, then
there is no cycle.
This gives HasSimpleCycle O(V + E)
5
4. Given a directed graph G = (V, E), we say that it is at least one-way connected if for every
u1, u2 ∈ V , there exists a path from u1 to u2 or a path from u2 to u1. Write an algorithm to
determine whether G is at least one-way connected. The input to your algorithm is a directed
graph.
Here are couple of scenarios. Graph I is at least one-way connected and Graph II is not at
least one-way connected (in Graph II for pair of vertices a and e, there is no path from a to
e and from e to a).
a
b
c
d
e a
b
c
d
e
(I) (II)
AtLeastOneWayConnected(V, E)
SCCs = Tarjan(V, E)
V’ = all individual components in SCCs
E’ = edges connecting components in SCCs
// compute in degrees
for each c in V’
in(c) = 0
for each e (u, c) in E’
c.in++
while (|V’| > 0)
root = null
for each c in V’
if in(c) == 0 && root != null
root = c
else
return false
for all e (u, root) in E’
in(u)--
remove root from V’
return true
First, we get all the strongly connected components of our graph. This gives us a condensed
graph that is guranteed to be a DAG. Now we can determine root nodes in our DAG by
finding which components have an in degree of 0. We then remove that root node, update the
in degree of all nodes it goes to, and repeat. If there’s ever more than one root node, then we
have branches with components where at least one of the branches cannot reach the other.
If there’s branches that can reach eachother, then we’d have a cycle, and that’s not possible
because SCC graphs are DAGs. So, upon detection of multiple root nodes, we return false,
6
else if we are able to clear all nodes, we can return true.
Tarjan takes O(V + E), then we perform initializations in O(V), then calculating in degrees in
O(E). In the worst case for finding each root node, we must make |V |−k comparisons, where k
is the nubmer of nodes removed. So, it could take |V |+(|V |−1)+(|V |−2)+...+1 comparisons
to remove all root nodes giving |V |(|V |+ 1)/2 ∈ O(V
2
). O(V +E) +O(V ) +O(E) +O(V
2
) =
O(V
2 + E).
7
5. Extra Credit Given an undirected graph G = (V, E), we say that it is k-colorable if each
vertex v can be colored with one of the k colors (c(v) is the color of vertex v) such that
∀(u1, u2) ∈ E : c(u1) 6= c(u2). Write an algorithm to verify that a given graph is 2-colorable
and if it is, then determine a coloring scheme (i.e., determine the color for each vertex). The
input to your algorithm is an undirected graph and 2 colors.
ColoringDFS(v, c1, c2)
for all n in neighbors(v)
if visited(n)
if c(n) == c(v)
return false
else
c(n) = (c(v) == c1 ? c2 : c1)
ColoringDFS(n)
return true
TwoColorable(V, E, c1, c2)
for all v in V
visited(v) = 0
c(v) = null
for all v in V
c(v) = c1
if !ColoringDFS(v)
return (false, c(V))
return (true, c(V))
A graph is 2-colorable iff it is bipartite. This is a modification of detecting bipartisonship
with DFS that colors nodes as it goes. Then we can simply return whether or not the graph
is bipartite along with the coloring scheme.
Detecting bipartisonship is O(V + E), giving TwoColorable in O(V + E).
8