# 2005 F

226,628pages on
this wiki

(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
S(i,j,k)

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
$F_0=0;$
For i:=2 to n
$F_i=F_{i-1}+F_{i-2}$
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?

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 n$log_3$n+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_1$$V_2$=empty set and $V_1$$V_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.

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