1-
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 i
th
node in a binary min heap, you can exchange the last node with the i
th
node, then check the nodes below the i
th
node to see if the i
th
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) 20 pts
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) 14 pts
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) 13 pts
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) 20 pts 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) 13 pts 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)+n 2 logn ii. T(n)=4T(n/2)+nlogn iii. T(n)=(6006) 1/2 *T(n/2)+n √6006 Additional Space