1-
CS570
Analysis of Algorithms
Fall 2013
Exam I
Name: _____________________
Student ID: _________________
____Tuesday/Thursday Session ____Wednesday Session ____DEN
Maximum Received
Problem 1 20
Problem 2 15
Problem 3 15
Problem 4 20
Problem 5 15
Problem 6 15
Total 100
2 hr exam
Close book and notes
If a description to an algorithm is required please limit your description to within 150
words, anything beyond 150 words will not be considered.
Xinyu
打字机
Xinyu
打字机
Xinyu
打字机
1) 20 pts
Mark the following statements as TRUE or FALSE. No need to provide any
justification.
[ TRUE/FALSE ]
A directed graph G is strongly connected if and only if G with its edge directions
reversed is strongly connected.
True, by definition of strongly connectedness.
[ TRUE/FALSE ]
If a weighted undirected graph has two MSTs, then its vertex set can be partitioned
into two, such that the minimum weight edge crossing the partition is not unique.
True, Let T1 and T2 be two distinct MSTs. Let e1 be an edge that is in T1 but not in T2.
Removing e1 from T1 partitions the vertex set into two connected components. There is a
unique edge (call it e2) that is in T2 that crosses this partition. By optimality of T1 and T2,
both e1 and e2 should be of the same weight and further should be of the minimum weight
among all edges crossing this partition.
[ TRUE/FALSE ]
If the vertex set of a weighted undirected graph can be partitioned into two, such that
the minimum weight edge crossing the partition is not unique, then the graph has at
least two MSTs.
False. Consider the graph with edge set {(a,b),(b,c),(c,d)} where all edge weights are
identical. ({a,d},{b,c}) is a partition that does not have a unique minimum weight edge
crossing it, however the graph (being a tree) has a unique MST.
[ TRUE/FALSE ]
The number of binomial trees in a binomial heap with n elements is at most O(log n).
True. See the lecture notes.
[ TRUE/FALSE ]
A bipartite graph cannot contain a cycle of length 3 or greater.
False. Consider the graph which is also a cycle with 4 vertices. It is bipartite contradicting the
assertion in question.
[ TRUE/FALSE ]
Since Fibonacci heaps guarantee amortized cost and not worst case cost, the run time
complexity of Dijkstra’s algorithm using Fibonacci heaps may be worse than that of a
binary heap implementation.
False. For Fibonacci heaps with n entries, the amortized running time of delete min is O(log
n) and the amortized running time for decrease key is O(1). Thus for every sequence of
extract mins/decrease keys with (A extract mins and B decrease keys in total), the worst
case running time is bounded by O(B+A log n).
When applied to the implement the priority queue in Dijkstra, A is O(B), that is the number of
vertices visited is asymptotically bounded by the number of edges relaxed. A binary heap
implementation would take at least Theta(B log n) time since decreasy key takes Theta(log
n) time. Thus, the Fibonacci heap implementation is faster even in the worst case.
[ TRUE/FALSE ]
Implementations of Dijkstra’s and Kruskal’s algorithms are identical except for the relaxation
steps.
False. It is Dijkstra’s and Prim’s that bear a resemblance not Dijkstra’s and Kruskal’s. For
instance, at a generic stage in Kruskal’s we could have multiple disconnected components (a
forest) while Dijkstra’s always grows a tree.
[ TRUE/FALSE ]
The divide step in the divide and conquer algorithm always takes less time than the
combine step, therefore, the complexity of a divide and conquer algorithm is never
dependent on the divide step.
False. Divide step could be slower than the combine step.
[ TRUE/FALSE ]
Suppose that in an instance of the original Stable Marriage problem with n couples,
there is a man M who is first on every woman’s list and a woman W who is first on
every man’s list. If the Gale-Shapley algorithm is run on this instance, then M and W
will be paired with each other.
True. If (M,W) are not matched with each other, then since (M,W) prefer each other to
everyone else, they can swap making the matching unstable.
[ TRUE/FALSE ]
For a search starting at node s in graph G, the DFS Tree is never as the same as the
BFS tree.
False. For instance, G being a tree is a counterexample.
2) 15 pts
Suppose you are choosing between the following three algorithms:
I) Algorithm A solves problems by dividing them in constant time into five
subproblems of half the size, recursively solving each subproblem, and then
combining the solutions in linear time.
II) Algorithm B solves problems of size n by dividing in constant time and
recursively solving two subproblems of size n-1 and then combining the solutions in
constant time.
III) Algorithm C solves problems of size n by dividing them in constant time into
nine subproblems of size n/3, recursively solving each subproblem, and then
combining the solutions in O(n2 ) time.
What are the running times of each of these algorithms (in big-O notation), and which
would you choose?
I. O(nlog25)
II. O(2n)
III. O(n2log(n)) – the minimum time complexity
3) 15 pts
Suppose a CS curriculum consists of n courses, all of them mandatory. The prerequisite
graph G has a node for each course, and an edge from course v to course w if and only if
v is a prerequisite for w. Find an algorithm that works directly with this graph
representation, and computes the minimum number of semesters necessary to complete
the curriculum (assume that a student can take any number of courses in one semester).
The running time of your algorithm should be linear.
First do a BFS/DFS to make sure that the graph is a directed acyclic graph (DAG) (otherwise, the
coursework cannot be completed in finitely many semesters since there would be a cycle of
prerequisite dependencies).
The problem then reduces to finding the length of the longest path in the DAG which can be
solved as follows.
Do a topological sort, let the resulting set of vertices be {v1,v2,v3,…,vn} in O(|V|+|E|) time. Recall
from HW 4, prob 5 that the above topological sorting implies that for all j>i, there is no directed
path from vj to vi.
Set all the edge lengths to equal 1.
Then iteratively (similar to Dijkstra’s modification in HW 4, prob 5) compute the length of the
longest path to v1, then the length of the longest path to v2, and so on until vn as explained
below.
Let L(v) denote the length of the longest path ending at v. We will iteratively compute L(v).
Start with v1. Since v1 has no incoming edges, the length of the longest path to v1 is L(v1)= 0.
The length of the longest path to v2 is L(v2) = 1 if the edge (v1,v2) is present and 0 otherwise.
More generally, If vi does not have an incoming edge, then set L(vi)=0. If vi has an incoming
edge, then L(vi) = max ( L(vk) + 1) where the maximum is taken over all vk such that (vk,vi) is
present in the graph. (Remark: The ordering implies that the only k values that we need to
consider are k