CS 473 (ug): Combinatorial Algorithms, Fall 2005Homework 0This homework is not to be turned in, but you should do it to check yourunderstanding of the pre-requisite material.This homework tests your familiarity with prerequisite material—big-Oh notation, elementaryalgorithms and data structures, recurrences, discrete probability, and induction—to help you iden-tify gaps in your knowledge. You are responsible for filling those gaps on your own. Forreview, you can check chapters 2 and 3 of the 473 textbook, your discrete mathematics and datastructures textbooks, or the first few chapters of CLRS.CS 473 (ug) Homework 0 (not to be submitted) Fall 20051. Solve the following recurrences. State tight asymptotic bounds for each function in the formΘ(f(n)) for some recognizable function f (n). Assume reasonable but nontrivial base cases.(a) A(n) = 2A(n/4) +√n(b) B(n) = maxn/3<k<2n/3B(k) + B(n − k) + n(c) C(n) = 3C(n/3) + n/ lg n(d) D(n) = 3D(n − 1) − 3D(n − 2) + D(n − 3)(e) E(n) =E(n − 1)3E(n − 2)[Hint: This is easy!](f) F (n) = F (n − 2) + 2/n(g) G(n) = G(log n) + log n(h) H(n) = H(n/2) + 1(i) I(n) = I(n/2) + I(n/4) + I(n/8) + I(n/12) + I(n/24) + n(j) J(n) = 2J(√n) + n22. Sort the following functions from asymptotically smallest to asymptotically largest, indicatingties if any.Pni=1i nlg lg n3nn1/n(lg n)lg2nlg(n!)Pni=1i2− (i − 1)22lg(2n)Pni=11ilg∗22nWhere lg∗n is the iterated logarithm (to the base 2) of n. For more information about iter-ated logarithms, seethe Wikipedia article on iterated logarithms.3. A tournament is a directed graph, such that every pair of vertices has one edge between them.(That is, for any vertices u, v there is either an edge from u to v or an edge from v to u.) AHamiltonian Path in a graph is a path that visits every vertex exactly once. Show that everytournament has a Hamiltonian Path. The figure below shows a 5-vertex tournament, withthe edges corresponding to one Hamiltonian Path highlighted.)1CS 473 (ug) Homework 0 (not to be submitted) Fall 20054. Consider this algorithm to sort an array A of n distinct numbers:Pick two indices i, j uniformly at random from {1,2,..., n}If A[min(i,j)] > A[max(i, j)]swap the elements in positions i and jRepeatThe algorithm automagically stops once the array is sorted.(a) Prove that after O (n2) swaps, the algorithm must halt.(b) Show that if the array is unsorted, the algorithm will perform a swap in a single iterationwith probability at least2n2.(c) Hence, find an upper bound on the exp ec ted number of iterations to perform a swap.(d) Prove that the expected running time of the algorithm is O(n4).(e) Make a simple modification to the algorithm that eliminates the need for the automagicalstop without increasing the overall running time. (That is, the modified algorithm shouldstill have running time
View Full Document