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 time, but the worst case cost is higher.
[ TRUE/FALSE ]
Function is O( ).
2) 20pts
A pharmacist has W pills and n empty bottles. Let denote the number of pills that each bottle can hold.
Describe a greedy algorithm, which, given W and , determines the fewest number of bottles needed to store the pills. Prove that your algorithm is correct.
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.
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.
, , 5 , , , 3n, , , 2n+1
5) 20pts
Let G = (V, E) be an (undirected) graph with costs Ce ≥ 0 on the edges e ∈ E. Assume you are given a minimum-cost spanning tree T in G. Now assume that an edge connecting two nodes v, w ∈ V with cost c is deleted from graph G and let G’ be the new graph. Assume that the graph G’ is connected.
a. If the removed edge doesn’t appear in the MST T, will T still be the MST of G’? Please justify your answer.
b. If the removed edge appears in the MST T, give an O(|V|+|E|) algorithm to find a MST for the graph G’.
c. Prove that the output produced by your algorithm in part b is an MST
6) 13pts
Solve the following recurrences by giving tight Θ-notation bounds. You do not need to justify your answers, but any justification that you provide will help when assigning partial credit.
i. T(n)=5T(n/2)+n2logn
ii. T(n)=4T(n/2)+nlogn
iii. T(n)=(6006)1/2*T(n/2)+n√6006
Additional Space