1)  20 pts

Mark the following statements as TRUE or FALSE. No need to provide any justification.

[TRUE/FALSE]

Given a binary max-heap with n elements, the time complexity of finding the smallest element is O(log n).

[TRUE/FALSE]

A greedy algorithm considers the entire search space when making each step.

[TRUE/FALSE]

Suppose that for a graph G = (V, E) the average edge weight is w. Then a minimum spanning tree of G will have weight at most (V - 1) w.

[TRUE/FALSE]

Consider two positively weighted graphs G1 = (V, E, w1) and G2 = (V, E, w2) with the same vertices V and same edges E such that for any edge e ϵ E we have w2(e) =        (w1(e)2 . For any two vertices u ϵ V and v ϵ V any shortest path between u and v in G2 is also a shortest path in G1 .

[TRUE/FALSE]

If all edges in a connected undirected graph have unit cost, then you can find the MST using BFS.

[TRUE/FALSE]

Breadth first search is an example of a divide-and-conquer algorithm.

[TRUE/FALSE]

For any cycle in a graph, the cheapest edge in the cycle is in a minimum spanning tree.

[TRUE/FALSE]

0/1 knapsack problem can be solved using dynamic programming in polynomial time.

[TRUE/FALSE]

DFS finds the longest paths from start vertex s to each vertex v in the graph.

[TRUE/FALSE]

The shortest path in a weighted DAG can be found in linear time.

2)   14 pts

Arrange the following functions in increasing order of growth rate with g(n) following f(n) in your list if and only iff (n) = O(g(n)):

2(log n) ,         (log n)log n,         n (log n)3 ,          √log n             22n ,         n1.001,         n!

3)   12 pts.

Suppose that we have an undirected graph G = (V, E). Prove the following statements.

a)   If G is a simple connected graph, then E ≤   .   (3 pts)

b)  If G is a simple graph with V > 3 and E  >   , then G is a connected graph. (9 pts)

4)   12 pts.

Businessman Daniel has n containers c1, c2, …, cn  of several varieties of fruits to ship. Each container has different cost and depreciation expense. Initial value of each container is v1, v2, …, vn  and depreciation expense is given by d1, d2, …, dn . Daniel has only one ship, so he can transport only one container at a time. Therefore, if container ci happens to be in the j-th shipment, its value will depreciate to vi /(j ∗ di ). Can you help Daniel to ship all containers and maximize total value of containers after depreciation? Provide proof of correctness and state the complexity of your algorithm.

5)   10 pts.

For each of the following recurrences, give an expression in the Theta notation for the runtime  T(n)  if the  recurrence  can  be  solved  with  the  Master  Theorem.  Otherwise, indicate that the Master Theorem does not apply.

1.   T(n) = 16T () + n

T(n) =

2.   T(n) = 3T () + √n

T(n) =

3.   T(n) = T () + n (2 − cos n)

T(n) =

4.   T(n) = 2T () + n log2n

T(n) =

5.   T(n) = 8T () − n2  + n2 log n

T(n) =

6)   15 pts

Kuang is planning to go skiing in Big Bear Mountain. The resort has n trails amd m resting bases. As a professional skier, he tries to find the minimum time he needs to get from the peak of the mountain to different resting bases. Due to the safety issue, Kuang must follow the following restrictions:

•   He starts skiing from the peak.

•   There are many ski trails connecting different resting bases, as well as the peak, however there is at most one trail connecting two of them.

•   For  each  ski  trail  in  the  mountain,  Kuang  knows  the  time  he  needs  to  get downhill.

•   Kuang cannot ski uphill.

a)  Design a linear time algorithm to find the minimum time to get from the peak to all the other resting bases. (10 pts)

b)  Show the time complexity of the algorithm. (5 pts)

7)   17 pts

There are several ways to formalize the notion of distance between strings. One common formalization is called edit distance, that focuses on transforming one string into the other by a series of edit operations. The permitted operations are Delete, Insert and Replace of a character in the first string.  We also permit Match, denoting that two characters match each other. Here is one possible alignment of DYNAMIC and STATIC

R  R  D  M  R  M  M

-------------------------

d

s

y

t

n   a  m

a   t

i

i

c

c

The  edit  distance  between  two  strings  is  defined  as  the  minimum  number  of edit operations. A transformation in terms of D, I, M, R of one string to another is called an edit transcript. The edit distance problem is to compute the edit distance between two given strings along with an optimal edit transcript.

Design a dynamic programming algorithm that calculates the edit distance between string X of length n and another string Y of length m.

a)  Define (in plain English) subproblems to be solved. (3 pts)

b)  Write the recurrence relation for subproblems. (5 pts)