CMSC 451:Fall 2012 Dave MountHomework 1: Algorithm Design BasicsHanded out Thu, Sep 6. Due at the start of class Thu, Sep 20. Late homeworks are not accepted, but youmay drop your lowest homework score.References: For reference information on asymptotics, summations, and recu r r e nc es , see either the text,by Cormen, Leiserson, Rivest, and Stein or the text by Kleinberg and Tardos. Also see the class handout onBackground Information.Notation: Throughout the semester, we will use lg x to denote logarithm of x base 2 (log2x) and ln x todenote the natural logarithm of x. We will use log x when the base does not matter.A Note about Writing Algorithms: When presenting algorithms, more detail is not necessarily better.Remember that your algorithm will be read by a human, not a compiler. You may assume that the readeris familiar with the p r obl em. Be sure that your pseudo-code is sufficiently detailed that your intenti ons areclear and unambiguous. Avoid adding extrane ous details and confusing jargon. (E.g., It is much cleare r tosay “Insert x at the end of the list” rather th an list.insertAtEnd(x).) You may make u s e of any standarddata structures (linked lists, binary trees, heaps, etc.) without explaining how to implement them. If youhave any questions, check with us.In addition to p r es e nting pseudo-code, explain your general strategy in English. (This way, if you makea co din g error, the grader can ascertain your real intent and give partial credit.) It is also a good idea toprovide a short example to illustrate your approach. Even if you are not explicitly asked, you should alwaysprovide a justification of correctness of your algorithm and analysis of its running time.Problem 1. Consider the following simpler algorithm for the stable marriage problem. As in the standar dproblem, there are n men and n women, and each man and each woman has an n-element preferencelist that orders all the members of the opposite sex. Th is algorithm ignores woman preferences, andsimply pairs each man with the first available woman on his list.for (i = 1 to n) {let (w[1], ..., w[n]) be the women of m[i]’s preference list (from high to low)j = 1while (j <= n and m[i] is not yet engaged) {if (w[j] is not yet engaged) {match m[i] with w[j] (and both are now engaged)}else j = j + 1}}(Note that in this algorithm, once a woman accepts a man’s proposal, she will never break it off.) Wewill explore the correctness of this algorithm by answering the following ques ti ons .(a) Is this algorithm guaranteed to pr oduce a perfect matching (that is, every man is paired exactlyone woman and vice versa)? If so, give a proof, and if not, give a counterexample.(b) If your answer to (a) was “no”, skip the rest of the problem. Otherwise, is the matching prod uc edby this algorithm guaranteed to be stable? If so, give a proof, and if not, present a counterexample.(c) If your answer to (b) was “yes”, skip this part. Otherwise, suppose that all the women inthis system have ex actl y the same sets of preferences, and in particular, they rank the menin (decreasing preference) order hm1, m2, . . . , mni. (Each man’s list contains all the women,but otherwise each man’s preferences are arbitrary.) Under this restriction, is the matchingproduced by this algorithm guaranteed to be stable? As before, either give a proof or pres ent acounterexample.1(Note: Throughout the semester, when ever you are asked to present a counterexample, you shouldstrive to make your counterexample as short and clear as possible. In addition to giving the inputfor the counterexample, briefly explain what the algorithm does when run on this input and why it iswrong.)Problem 2. Consider the following summation, which holds for all n ≥ 0,nXi=1i3= nXi=1i!2That is (13+ 23+ · · · + n3) = (1 + 2 + · · · + n)2.(a) Prove this identity holds for all n ≥ 0, by induction on n. (Recall that by convention, for n = 0we have an empty sum, whose value is defined to be the additive identity, that is, zero.)(b) The following figure provides an informal “pictorial proof” of this identity. Explain why.Figure 1: Proble m 2.Problem 3. For each of the parts below, list the func tion s in increasing asymptotic order. In some casesfunctions may be asymptotically equivalent (that is f(n) is Θ(g(n))). In such cases indicate this bywriting f(n) ≈ g(n). Wh en one is asymptotically strictly less t han the other (that is, f (n) is O(g(n))but f(n) is not Θ(g(n))), express this as f (n) ≺ g(n). For example, given the set:n2n log n 3n + n log n,the first function is Θ(n2) and the other two are Θ(n log n), and therefore the answer would ben log n ≈ 3n + n log n ≺ n2.Explanations are not required, but may be given to help in assigning partial credit.(a) (3/2)n3(n/2)2(n/3)(b) lg n ln n lg(n2)(c) nlg 42lg n2(2 lg n)(d) max(50n2, n3) 50n2+ n3min(50n2, n3)(e)n2/20 n2/20n2/20Problem 4. The purpose of this problem is to design a more efficient algorithm for the previous largerelement problem, as introduced in class. Recall that we are given a sequence of numeric values,ha1, a2, . . . , ani. For each element ai, for 1 ≤ i ≤ n, we want t o know the index of t he rightmostelement of the sequence ha1, a2, . . . , ai−1i whose value is strictly larger than ai. If no element of thissubsequence is larger than aithen, by convention, the index will be 0. Here is naive th e Θ(n2) algorithmfrom class.2previousLarger(a[1..n]) {for (i = 1 to n)j = i-1;while (j > 0 and a[j] <= a[i]) j--;p[i] = j;}return p}There is one obvious source of inefficiency in this algorithm, namely the statement j--, which stepsthrough the array one element at a time. A more efficient approach would be to exploit p-values thathave already been constructed. (If you don’t see this right away, try drawing a picture.) Using thisinsight, desi gn a more efficient algorithm. For full credit, your algorithm should run in Θ(n) time.Prove that your algorithm is correct and derive its running time.Challenge Problem. Challenge problems count for extra credit points. These additional points are fac-tored in only after the final cutoffs have been set, and can only increase your final grade.An in-place algorithm is one th at is given its input in a chunk of memory (e.g., as an array) whichit is allowed to modify in the course of the algorithm, it stores its output in this same chunk ofmemory. Otherwise, it is only allowed to use a constant amount of additional working
View Full Document
Unlocking...