CS570
Analysis of Algorithms Spring 2015
Exam I
Name: _____________________ Student ID: _________________
Email Address:_______________
_____Check if DEN Student
Maximum
Received
Problem 1
20
Problem 2
20
Problem 3
14
Problem 4
13
Problem 5
20
Problem 6
13
Total
100
Instructions:
1. This is a 2-hr exam. Closed book and notes
2. If a description to an algorithm or a proof is required please limit your description or
proof to within 150 words, preferably not exceeding the space allotted for that
question.
3. No space other than the pages in the exam booklet will be scanned for grading.
4. If you require an additional page for a question, you can use the extra page provided
within this booklet. However please indicate clearly that you are continuing the solution on the additional page.
20 pts
Mark the following statements as TRUE or FALSE. No need to provide any justification.
[ TRUE/FALSE ]
For some graphs BFS and DFS trees can be the same.
[ TRUE/FALSE ]
The number of cycles in a bipartite graph may be odd.
[ TRUE/FALSE ]
Stable matching algorithm presented in class is based on the greedy technique.
[ TRUE/FALSE ]
To delete the ith node in a binary min heap, you can exchange the last node with the ith node, then check the nodes below the ith node to see if the ith node should move down the heap to “re-heapify” it.
[ TRUE/FALSE ]
Kruskal’s algorithm can fail in the presence of negative cost edges.
[ TRUE/FALSE ]
Consider an instance of the Stable Matching Problem in which there exists a man m and a woman w such that m is ranked first by w, and w is ranked first by m. Then (m, w) must appear in every stable matching.
[ TRUE/FALSE ]
If a connected undirected graph G has the same weights for every edge, then a minimum spanning tree can be found in linear time.
[ TRUE/FALSE ]
Given n numbers, one could construct a binary heap using the n numbers, then using the binary heap produce a sorted list of the numbers in O(n) time.
[ TRUE/FALSE ]
In a Fibonacci heap, the insert operation has an amortized cost of 𝑂(1) time, but the worst case cost is higher.
[ TRUE/FALSE ]
Function 10𝑛102𝑛 + 3𝑛log(𝑛) is O(𝑛102𝑛).
2) 20pts
A pharmacist has W pills and n empty bottles. Let {𝑝1, 𝑝2, … , 𝑝𝑛} denote the number of pills that each bottle can hold.
Describe a greedy algorithm, which, given W and {𝑝1, 𝑝2, … , 𝑝𝑛}, determines the fewest number of bottles needed to store the pills. Prove that your algorithm is correct.
Solution:
Sort the n bottles in non-increasing order of capacity. Pick the 1st bottle, which has largest capacity, and fill it with pills. If there are still pills left, fill the next bottle with pills. Continue filling bottles until there are no more pills. We can sort the bottles in O(n log n) and it takes time O(n) to fill the bottles, so our greedy algorithm has running time O(n log n).
To show correctness, we want to show there is an optimal solution that includes the 1st greedy choice made by our algorithm. Let k be the fewest number of bottles needed to store the pills and let S be some optimal solution. Denote the 1st bottle chosen by our algorithm by p’. If S contains p’, then we have shown our bottle is in some optimal solution. Otherwise, suppose p’ is not contained in S. All bottles in S are smaller in capacity than p’ (since p’ is the largest bottle) and we can remove any of the bottles in S and empty its pills into p’, creating a new set of bottles S’ = S –{p}∪{p’}that also contains k bottles { the same number of bottles as in S’. Thus S’ is an optimal solution that includes p’ and we have shown there is always an optimal solution that includes the 1st greedy choice.
Because we have shown there always exists an optimal solution that contains p’, the problem is reduced to finding an optimal solution to the subproblem of finding k-1 bottles in {𝑝1, 𝑝2, … , 𝑝𝑛}-{p’}to hold W-p’ pills. The subproblem is of the same form as the original problem, so that by induction on k we can show that making the greedy choice at every step produces an optimal solution.
3) 14pts
We are given a graph G = (V; E) with uniform cost edges and two vertices s and t within G. We are told that the length of the shortest path from s to t is more than n/2 (where n is the number of vertices within G). Give a linear time algorithm to
find a vertex v (other than s and t) such that every path from s to t contains v. Justify your solution.
Solution:
Algorithm:
a) Based on the uniform edge cost assumption, we run BFS from s and find the
shortest path from s to t.
b) Since the shortest distance from s to t is more than n/2, other than the s layer and
t’s belonged layer in the BFS tree, there must be at least one layer crossed by the shortest path that has only 1 vertex. Choose this single vertex that forms a layer by itself, and this vertex is a valid one we want.
c) Running BFS and searching takes linear time in total.
Proof (Justification):
The key part of the justification is to prove that, other than the s layer and t’s belonged layer in the BFS tree, there must be a layer crossed by the shortest path that has a single vertex.
Suppose this is not true, i.e., other than the s layer and t’s belonged layer, each layer of the BFS tree crossed by the shortest path has at least two vertices. As we know, the shortest path from s to t has distance more than n/2, i.e., the shortest distance is at least n/2+1, where n/2 means the largest integer smaller than or equal to n/2. Therefore, apart from the s layer and t’s belonged layer, the number of layers in the BFS tree crossed by the shortest path from s to t should be at least n/2, and the total number of vertices in these layers must be at least 2*n/2 ≥ n-1. Adding s and t, the total number of vertices in G turns out to be no less than n+1, which obviously contradicts the fact that n is the number of vertices in G.
Thus, other than the s layer and t’s belonged layer, there must be a layer between s and t that only has a single vertex, denoted as v. Then every possible path from s to v must pass through node v.
4) 13pts
Arrange the following functions in increasing order of asymptotic complexity. If f(n)=Ө(g(n)) then put f=g. Else, if f(n)=O(g(n)), put f < g.
4𝑛2, log2 𝑛, 5𝑛2, log3 𝑛, 𝑛𝑛, 3n, 𝑛𝑙𝑜𝑔(𝑛), 2𝑛, 2n+1
Solution:
log2𝑛