CS 473 Homework 0 (due January 26, 2009) Spring 2010CS 473: Undergraduate Algorithms, Spring 2010Homework 0Due Tuesday, January 26, 2009 in class•This homework tests your familiarity with prerequisite material—big-Oh notation, elementaryalgorithms and data structures, recurrences, graphs, and most importantly, induction—to helpyou identify gaps in your background knowledge.You are responsible for filling those gaps.The early chapters of any algorithms textbook should be sufficient review, but you may also wantconsult your favorite discrete mathematics and data structures textbooks. If you need help, pleaseask in office hours and/or on the course newsgroup.•Each student must submit individual solutions for these homework problems. For all futurehomeworks, groups of up to three students may submit (or present) a single group solution foreach problem.•Please carefully read the course policies linked from the course web site. If you have any questions,please ask during lecture or office hours, or post your question to the course newsgroup. Inparticular:–Submit five separately stapled solutions, one for each numbered problem, with your nameand NetID clearly printed on each page. Please do not staple everything together.–You may use any source at your disposal—paper, electronic, or human—but youmustwriteyour solutions in your own words, and you must cite every source that you use.– Unless explicitly stated otherwise, every homework problem requires a proof.–Answering “I don’t know” to any homework or exam problem (except for extra creditproblems) is worth 25% partial credit.–Algorithms or proofs containing phrases like “and so on” or “repeat this process for alln”,instead of an explicit loop, recursion, or induction, will receive 0 points.1CS 473 Homework 0 (due January 26, 2009) Spring 20101. (a) Write the sentence “I understand the course policies."(b) [5 pts]Solve the following recurrences. State tight asymptotic bounds for each function inthe form Θ(f(n)) for some recognizable functionf(n). Assume reasonable but nontrivialbase cases if none are given.Do not submit proofs—just a list of five functions—but youshould do them anyway, just for practice.• A(n) = 3 A(n −1) + 1• B(n) = B(n −5) + 2n −3• C(n) = 4 C(n/2) +pn• D(n) = 3 D(n/3) + n2• E(n) = E(n −1)2− E(n −2)2, where E(0) = 0 and E(1) = 1 [Hint: This is easy!](c) [5 pts]Sort the following functions from asymptotically smallest to asymptotically largest,indicating ties if there are any.Do not submit proofs—just a sorted list of 16 functions—butyou should do them anyway, just for practice.Writef(n) g(n) to indicate thatf(n) =o(g(n)), and writef(n)≡ g(n) to meanf (n) = Θ(g(n)). We use the notation lg n = log2n.n lg npn 5nplg n lgpn 5pnp5n5lg nlg(5n) 5lgpn5plg np5lg nlg(5pn) lgp5nplg(5n)2. [CS 225 Spring 2009]Suppose we build up a binary search tree by inserting elements one at atime from the set{1,2,3, . . . , n}, starting with the empty tree. The structure of the resulting binarysearch tree depends on the order that these elements are inserted; every insertion order leads to adifferent n-node binary search tree.Recall that the depth of a leaf`in a binary search tree is the number of edges between`andthe root, and the depth of a binary tree is the maximum depth of its leaves.(a)What is the maximum possible depth of ann-node binary search tree? Give an exact answer,and prove that it is correct.(b)Exactly how many different insertion orders result in ann-node binary search tree withmaximum possible depth? Prove your answer is correct. [Hint: Set up and solve a recurrence.Don’t forget to prove that recurrence counts what you want it to count.]2CS 473 Homework 0 (due January 26, 2009) Spring 20103. [CS 173 Spring 2009] A binomial tree of order k is defined recursively as follows:• A binomial tree of order 0 is a single node.•For allk >0, a binomial tree of orderkconsists of two binomial trees of orderk −1, withthe root of one tree connected as a new child of the root of the other. (See the figure below.)Prove the following claims:(a) For all non-negative integers k, a binomial tree of order k has exactly 2knodes.(b)For all positive integersk, attaching a leaf to every node in a binomial tree of orderk −1results in a binomial tree of order k.(c) For all non-negative integers k and d, a binomial tree of order k has exactlykdnodes withdepth d.Binomial trees of order 0 through 5.Top row: the recursive definition. Bottom row: the property claimed in part (b).4. [CS 373 Fall 2009] For any language L ∈ Σ∗, letRotate(L) :=¦w ∈ Σ∗w = x y and y x ∈ L for some strings x, y ∈ Σ∗©For example, Rotate({OOK!, OOKOOK}) = {OOK!, OK!O, K!OO, !OOK, OOKOOK, OKOOKO, KOOKOO}.Prove that ifLis a regular language, thenRotate(L) is also a regular language. [Hint:Remember the power of nondeterminism.]5.Herr Professor Doktor Georg von den Dschungel has a 24-node binary tree, in which every node islabeled with a unique letter of the German alphabet, which is just like the English alphabet withfour extra letters:Ä,Ö,Ü, andß. (Don’t confuse these withA,O,U, andB!) Preorder and postordertraversals of the tree visit the nodes in the following order:• Preorder: B K Ü E H L Z I Ö R C ß T S O A Ä D F M N U G• Postorder: H I Ö Z R L E C Ü S O T A ß K D M U G N F Ä B(a) List the nodes in George’s tree in the order visited by an inorder traversal.(b) Draw George’s tree.3CS 473 Homework 0 (due January 26, 2009) Spring 2010?6. [Extra credit]You may be familiar with the story behind the famous Tower of Hanoï puzzle, asrelated by Henri de Parville in 1884:In the great temple at Benares beneath the dome which marks the centre of the world, rests a brass platein which are fixed three diamond needles, each a cubit high and as thick as the body of a bee. On one ofthese needles, at the creation, God placed sixty-four discs of pure gold, the largest disc resting on thebrass plate, and the others getting smaller and smaller up to the top one. This is the Tower of Bramah.Day and night unceasingly the priests transfer the discs from one diamond needle to another accordingto the fixed and immutable laws of Bramah, which require that the priest on duty must not move morethan one disc at a time and that he must place this disc on a needle so that there is no smaller disc belowit. When the sixty-four discs shall have been thus transferred from the