1-
CS570
Analysis of Algorithms
Fall 2014
Exam I
Name: _____________________
Student ID: _________________
Wednesday Evening Section
Maximum Received
Problem 1 20
Problem 2 16
Problem 3 16
Problem 4 16
Problem 5 16
Problem 6 16
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.
1) 20 pts
Mark the following statements as TRUE or FALSE. No need to provide any
justification.
[ TRUE/FALSE ]
Let be a complete binary tree with nodes. Finding a path from the root of to a
given vertex using breadth-first search takes .
[ TRUE/FALSE ]
Dijkstra’s algorithm works correctly on a directed acyclic graph even when there are
negative-weight edges.
[ TRUE/FALSE ]
If the edge is not part of any MST of , then it must be the maximum weight edge
on some cycle in .
[ TRUE/FALSE ]
If and then .
[ TRUE/FALSE ]
The following array is a max heap: [10; 3; 5; 1; 4; 2].
[ TRUE/FALSE ]
There are at least 2 distinct solutions to the stable matching problem: one that is
preferred by men and one that is preferred by women.
[ TRUE/FALSE ]
In a binary max-heap with n elements, the time complexity of finding the second
largest element is O(1).
[ TRUE/FALSE ]
Given a binary max-heap with n elements, the time complexity of finding the smallest
element is O(lg n).
[ TRUE/FALSE ]
Kruskal’s algorithm can fail in the presence of negative cost edges.
[ 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.
2) 16 pts
The diameter of a graph is the maximum of the shortest paths’ lengths between all pairs
of nodes in graph . Design an algorithm which computes the diameter of a connected,
undirected, unweighted graph in time, and explain why it has that runtime.
3) 16 pts
Consider a stable marriage problem where the set of men is given by M = {m1, m2, …,
mN} and the set of women is W = {w1, w2, …, wN}. Consider their preference lists to
have the following properties:
prefers over
prefers over
Prove that a unique stable matching exists for this problem.
Note: symbol means “for all”.
4) 16 pts
Ivan is a businessman and he has several large containers of fruits to ship. As he has
only one ship he can transport only one container at a time and also it takes certain
fixed amount of time per trip. As there are several varieties of fruits in the containers,
the cost and depreciation factor associated with each container is different. He has n
containers, a1, a2, … , an. Initial value of each container is v1, v2, … , vn and
depreciation factor of each container is d1, d2, … , dn. So, if container ai happens to be
the j
th
shipment, its value will be vi (di j). Can you help Ivan maximize profit
(value) by providing an efficient algorithm to ship the containers? Provide proof of
correctness and state the complexity of your algorithm.
5) 16 pts
Consider an undirected graph G = (V, E) with distinct nonnegative edge weights we ≥
0. Suppose that you have computed a minimum spanning tree of G. Now suppose
each edge weight is increased by 1: the new weights are w’e = we + 1. Does the
minimum spanning tree change? Give an example where it changes or prove it cannot
change.
6) 16 pts
Mark all the correct statements in the following:
a. Consider these two statements about a connected undirected graph with vertices and
edges:
I.
II.
(a) I and II are both false.
(b) Only I is true.
(c) Only II is true.
(d) I and II are both true.
b. Suppose the shortest path from node to node goes through node and that the cost
of the subpath from to is . Consider these two statements:
I. Every shortest path from i to j must go through k.
II. Every shortest path from i to k has cost .
(a) I and II are both true.
(b) Only I is true.
(c) Only II is true.
(d) I and II are both false.
c. Consider the execution times of two algorithms I and II:
I.
II.
(a) Only I is polynomial.
(b) Only II is polynomial.
(c) I and II are both polynomial.
(d) Neither I nor II is polynomial.
d. Suppose . Consider these statements:
I.
II.
(a) Only I is true.
(b) Only II is true.
(c) I and II are both true.
(d) I and II are both false.
Additional Space