CS计算机代考程序代写 algorithm 1-

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 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) 20 pts

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) 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.

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) 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. 4𝑛2, log2 𝑛, 5𝑛2, log3 𝑛, 𝑛𝑛, 3n, 𝑛𝑙𝑜𝑔(𝑛), 2𝑛, 2n+1 Solution: log2 𝑛 < log3 𝑛 < 2𝑛 = 2𝑛 + 1 = 3𝑛 < 𝑛𝑙𝑜𝑔(𝑛) < 4𝑛2 = 5𝑛2 < 𝑛𝑛 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. Yes, If there is another MST T’ which is better than T for the graph G’ then it will also be better than T for the graph G, which is a contradiction that T is a MST for graph G. b. If the removed edge appears in the MST T, give an O(|V|+|E|) algorithm to find a MST for the graph G’. After an edge is removed from the MST T, let A and B be the two connected components that are formed. From the graph G’, find an edge e’ that connects A and B and has minimum cost among all such edges. Join components A and B with the e’ to give a new tree T’, which will be MST of G’. c. Prove that the output produced by your algorithm in part b is an MST By applying cycle property, if a "better edge" is added to a tree, and the cycle has a more expensive edge than "better edge", then the tree is not MST; otherwise, "better edge" does not exist anywhere, tree is MST. 1. The two sub-trees after disconnection are both MST, using cycle property, no "better edge" within each sub-tree. 2. If a "better edge" is connecting two sub-trees, some edge in sub-tree is more expensive. This means the original tree before the disconnection is not a MST. We have contradiction, so the "better edge" is not connecting two sub-trees. "better edge" does not exist anywhere, the tree from Problem 5(2) is a 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)+n2logn Solution: From master theorem case 1, i.e. for the recurrence relation T(n) = aT( 𝑛 𝑏 ) + f(n), if f(n) = O(𝑛𝑐), where c < 𝑙𝑜𝑔𝑏𝑎 then T(n)=𝜃(𝑛 log𝑏 𝑎) T(n) = Θ(nlog25) ii. T(n)=4T(n/2)+nlogn From master theorem case 1, T(n) = 𝜃(𝑛2) iii. T(n)=(6006)1/2*T(n/2)+n√6006 From master theorem case 3, i.e. if f(n) = Ω(𝑛𝑐), where 𝑐⁡ > ⁡𝑙𝑜𝑔𝑎𝑏, and 𝑎𝑓(
𝑛

𝑏
) ⁡≤ kf(n)

for constant k < 1 then T(n) = 𝜃(𝑓(𝑛)) T(n) = 𝜃(𝑛√6006) Additional Space