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 ]
then . 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.
If and
[ TRUE/FALSE ]
2) 16pts
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) 16pts
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) 16pts
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 jth 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) 16pts
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) 16pts
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 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.
. Consider these statements:
Additional Space