1. (16%) True or False. You need justify your answer.

(a) By the master theorem, the solution to the recurrence T(n)=3T(n/3)+logn is T(n)=Θ(nlogn)
(b) For hashing an item into a hash table in which collisions are resolved by chaining, the worst-case time is proportional to the load factor of the table.
(c) Depth-first search of a graph is asymptotically faster than breadth-first search.
(d) For any directed acylclic graph, there is only one topological ordering of the vertices.
(e) If some of the edge weights in a graph are negative, the shortest path from s to t can be obtained using Dijkstra's algorithm by first adding a large constant C to each edge weight, where C is chosen laree enough that every resulting edge weight will be nonnegative.
(f) If all of edge capacities in a graph are integer multiples of 5 then the maximum flow value is a multiple of 5.
(g) If each operation on a data structure runs in O(1) amortized time, then n consecutive operations run in O(n) time in the worst case.
(h) A graph algorithm with Θ(ElogV) running time is asymptotically better than an algorithm with a Θ(ElogE) running time for a connected, undirected graph G(V;E).

Ans: (a) false, it should be θ(n) (b) true (c) false, both are O(V+E) (d) false, there are many topological ordering (e) false, the path which has more edges will add more C (f) true (g) false, you can’t make sure when to amortize (h) false, if graph is connected, E=O(n^2) s.t. logE=O(log V)

2. (8%) Assume n≥0. How many times is procedure S called in this program?

for k:=1 to n do
for i:=1 to k-1 do
for j:=0 to k-1 do
if i!=j then
Try to simplify your answer.

Ans: \sum_{k=1}^n (k-1)k-(k-1)=\sum_{k=1}^n (k-1)^2=\sum_{k=1}^{n-1} k^2=\frac {(n-1)n(2n-1)}{6}

3. (16%) Fibonacci numbers are defined by the recurrence F_0=0, F_1=1, F_{n+1}=F_n+F_{n-1},n≥1. This problem concerns the exact calculation of F_n when n is very large. It is known that there is a constant c such that the exact binary representation of F_n fits in cn+O(1) bytes.

(a) (6%) Suppose you are using an algorithm for addition that takes max(m,n) units of time to add an m-byte number to an n-byte number. How many units of time does it take to compute the value of F_n for large n, using the program
For i:=2 to n
and the assumed algorithm for multiple-precision addition? Give an asymptotic answer that is correct to within O(n).
(b) (8%) Let L_n=F_{n-1}+F_{n+1}. It is known that F_{2n}=F_nL_n and L_{2n}=L_n^2-2(-1)^n. Therefore it is possible to compute F_{2^m} and L_{2^m} in O(m) multiplicative steps instead of order 2^m additive steps. Assume that you can multiply an m-byte number by an n-byte number in mn units of time, and that you can add or subtract 2 from a large number in constant time. Determine the asymptotic time needed to compute F_{2^m} by this "accelerated" method, correct to within O(2^m).
(c) (2%) When n=2^m is large, which of these two methods is faster, given that the constant is approximately 0.08678?

Ans: No answer

4. (10%) Suppose K is a totally ordered universe, and suppose you had a function middle (k_1, k_2, k_3) which, when given any three keys k_1, k_2, k_3 belongs to K, produces the value 1, 2, or 3 depending on whether k_1, k_2, k_3 is the middle value of the keys. Also assume that K has minimum element 0. We are interested in the complexity of sorting n different keys (all>0), using the function middle as the only comparison primitive. Prove a worst-case lower bound of nlog_3n+lower order terms (which needn't be given) for the number of calls of middle in order to sort nkeys.

Ans: Decision tree model, when middle is called, there will be three cases, so the decision tree height is log3 n! = Ω(n log3 n)

5. (10%) Suppose we have a sequence of O(n) Union's and Find's, in which all the Union's occur before the Find's. Assume that we use both the weighting heuristic and the path compression heuristic. Prove that this sequence can be processed in O(n) time.

Ans: Cormen 21.4

6. (18%) An undirected graph G=(V,E) is called bipartite if V can be partitioned into two disjount sets, V_1 and V_2 (i.e., V_1V_2=empty set and V_1V_2=V) such that every edge in E has one end in V_1 and the other in V_2.

(a) (9%) Show that graph is bipartite iff it has no cycle of odd length.
(b) (9%) Give an O(E) time algorithm to determine if a given graph G is bipartite.

Ans: (a) If there is one odd length cycle, then the start and end vertex will be in the same set. (b) DFS, the root is in V1, then all the adjacent vertexes are in V2, check this consistence.

7. (12%) Suppose you are given a set S={a_1, a_2, ..., a_n} of tasks, where task a_i requires p_i units of processing time to complete, once it has started. You have one computer on which to run these tasks, and the computer can run only one task at a time. A schedule assigns which tasks run during what times on the computer. For any schedule, let c_1 denote the completion time of task i, that is, the time at which task i completes processing. Your goal is to find a schedule that minimizes the average completion time, that is, minimizing \frac{1}{n}\sum_{i=1}^{n}c_i.

(a) (2%) Suppose there are two tasks with p_1=3 and p_2=5. Consider (1) the schedule in which task 1 runs first, followed by task 2 and (2) the schedule in which task 2 runs first, followed by task 1. In each case, state the values of c_1 and c_2 and compute the average completion time.
(b) (5%) Give an algorithm that schedules the tasks so as to minimize the average completion time. Each task must run non-preemptively, that is, once task i is started, it must run continuously for p_i units of time. Prove that your algorithm minimizes the average completion time, and state the running time of your algorithm.

Suppose now that the tasks are not all available at once. That is, each task has a release time r_1 before which it is not available to be processed. Suppose also that we allow preemption, so that a task can be suspended and restarted at a later time. For example, a task i with processing time p_i=6 may start running at time 1 and be preempted at time 4. It can then resume at time 10 but be preempted at time 11 and finally resume at time 13 and complete at time 15. Task i has run for a total of 6 time units, but its running time has been divided into three pieces.

(c) (5%) Give an algorithm that schedules the tasks so as to minimize the average completion time in this new scenario. Prove that your algorithm minimizes the average completion time, and state the running time of your algorithm.

Ans: No answer

8. (10%) Given a set Q of n points in the plane, we define the convex layers of Q inductively. The first layer is CH(Q), where CH(Q) denotes the convex hull of Q. For i>1, let Q_i be the set obtained from Q by removing the vertices in convex layer 1, 2, ..., i-1. Then the ith convex layer layer is CH(Q_i) if Q_i≠Φ. An illustration is in the following. Design an O(n^2) algorithm to compute all of the convex layers of a given set Q. Justify the time complexity?

Ans: Jarvis march, output n point, every point will use at most n operation, so the complexity is n^2.

Ad blocker interference detected!

Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.