# CS计算机代考程序代写 algorithm CS570

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