CMSC 451 Fall 2012 Dave Mount Homework 1 Algorithm Design Basics Handed out Thu Sep 6 Due at the start of class Thu Sep 20 Late homeworks are not accepted but you may drop your lowest homework score References For reference information on asymptotics summations and recurrences see either the text by Cormen Leiserson Rivest and Stein or the text by Kleinberg and Tardos Also see the class handout on Background Information Notation Throughout the semester we will use lg x to denote logarithm of x base 2 log2 x and ln x to denote 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 reader is familiar with the problem Be sure that your pseudo code is sufficiently detailed that your intentions are clear and unambiguous Avoid adding extraneous details and confusing jargon E g It is much clearer to say Insert x at the end of the list rather than list insertAtEnd x You may make use of any standard data structures linked lists binary trees heaps etc without explaining how to implement them If you have any questions check with us In addition to presenting pseudo code explain your general strategy in English This way if you make a coding error the grader can ascertain your real intent and give partial credit It is also a good idea to provide a short example to illustrate your approach Even if you are not explicitly asked you should always provide 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 standard problem there are n men and n women and each man and each woman has an n element preference list that orders all the members of the opposite sex This algorithm ignores woman preferences and simply 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 1 while 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 We will explore the correctness of this algorithm by answering the following questions a Is this algorithm guaranteed to produce a perfect matching that is every man is paired exactly one 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 produced by 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 in this system have exactly the same sets of preferences and in particular they rank the men in decreasing preference order hm1 m2 mn i Each man s list contains all the women but otherwise each man s preferences are arbitrary Under this restriction is the matching produced by this algorithm guaranteed to be stable As before either give a proof or present a counterexample 1 Note Throughout the semester whenever you are asked to present a counterexample you should strive to make your counterexample as short and clear as possible In addition to giving the input for the counterexample briefly explain what the algorithm does when run on this input and why it is wrong Problem 2 Consider the following summation which holds for all n 0 2 n n X X 3 i i i 1 i 1 That 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 0 we 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 Problem 2 Problem 3 For each of the parts below list the functions in increasing asymptotic order In some cases functions may be asymptotically equivalent that is f n is g n In such cases indicate this by writing f n g n When one is asymptotically strictly less than 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 n2 n log n 3n n log n the first function is n2 and the other two are n log n and therefore the answer would be n log n 3n n log n n2 Explanations are not required but may be given to help in assigning partial credit a b c d e 3 2 n lg n nlg 4 2 3 max 50n 2 n n 20 3 n 2 ln n 2lg n 2 n3 50n 2 n 20 2 n 3 lg n2 2 2 lg n min 50n2 n3 n2 20 Problem 4 The purpose of this problem is to design a more efficient algorithm for the previous larger element problem as introduced in class Recall that we are given a sequence of numeric values ha1 a2 an i For each element ai for 1 i n we want to know the index of the rightmost element of the sequence ha1 a2 ai 1 i whose value is strictly larger than ai If no element of this subsequence is larger than ai then by convention the index will be 0 Here is naive the n2 algorithm from class 2 previousLarger 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 steps through the array one element at a time A more efficient approach would be to exploit p values that have already been constructed If you don t see this right away try drawing a picture Using this insight design 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 factored in only after the final cutoffs have been set and can only increase your final grade An in place algorithm is one that is given its input in a chunk of memory e g as an array which it is allowed to modify in the course of the algorithm it stores its output in this same chunk of memory Otherwise it is only allowed to use a constant amount of additional working storage e …
View Full Document
Unlocking...