hw0.pdfhw1.pdfhw2.pdfhw3.pdfhw4.pdfhw5.pdfhw6.pdfmt1.pdfmt2.pdffinal.pdfCS 473G: Combinatorial Algorithms, Fall 2005Homework 0Due Thursday, September 1, 2005, at the beginning of class (12:30pm CDT)Name:Net ID: Alias:I understand the Homework Instructions and FAQ.• Neatly print your full name, your NetID, and an alias of your choice in the boxes above.Grades will be lis ted on the course web site by alias. Please w rite the sam e alias on everyhomework and exam! For privacy reasons, your alias should not resemble your name orNetID. By providing an alias, you agree to let us list your grades; if you do not provide analias, your grades will not be listed. Never give us your Social Security number!• Read the “Homework Instructions and FAQ” on the course web page, and then check the boxabove. This page describes what we exp ect in your homework solutions—start each numberedproblem on a new sheet of paper, write your name and NetID on every page, don’t turn insource code, analyze and prove everything, use good English and good logic, and so on—aswell as policies on grading standards, regrading, and plagiarism. See especially the coursepolicies regarding the magic phrases “I don’t know” and “and so on”. If you haveany questions, post them to the course newsgroup or ask during lecture.• Don’t forget to submit this cover shee t with the rest of your homework solutions.• This homework tests your familiarity with prerequisite material—big-Oh notation, elemen-tary algorithms and data structures, recurrences, discrete probability, and most importantly,induction—to help you identify gaps in your knowledge. You are responsible for fillingthose gaps on your own. Chapters 1–10 of CLRS should be sufficient review, but you mayalso want consult your discrete mathematics and data structures textbooks.• Every homework will have five required problems. Most homeworks will also include oneextra-credit problem and several practice (no-credit) problems. Each numbered problem isworth 10 points.# 1 2 3 4 5 6∗TotalScoreGraderCS 473G Homework 0 (due September 1, 2005) Fall 20051. Solve the following recurrences. State tight asymptotic bounds for each function in the formΘ(f(n)) for some recognizable function f(n). You do not need to turn in proofs (in fact, pleasedon’t turn in proofs), but you should do them anyway, just for practice. Assume reasonablebut nontrivial base cases. If your solution requires specific base cases, state them!(a) A(n) = 2A(n/4) +√n(b) B(n) = maxn/3<k<2n/3B(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) = 2Gd(n + 3)/4e − 5n/√lg n + 6 lg lg n+ 78√n − 9 − lg10n/ lg lg n + 11lg∗n− 12?(h) H(n) = 4H(n/2) − 4H(n/4) + 1 [Hint: Careful!](i) I(n) = I(n/2) + I(n/4) + I(n/8) + I(n/12) + I(n/24) + nF(j) J(n) = 2√n · J(√n) + n[Hint: First solve the secondary recurrence j(n) = 1 + j(√n).]2. Penn and Teller agree to play the following game. Penn shuffles a standard deck1of playingcards so that every permutation is equally likely. Then Teller draws c ards from the deck, oneat a time without replacement, until he draws the three of clubs (3♣), at which point theremaining undrawn cards instantly burst into flames and the game is over.The first time Teller draws a card from the deck, he gives it to Penn. From then on, untilthe game ends, whenever Teller draws a c ard whose value is smaller than the previous cardhe gave to Penn, he gives the new card to Penn. To make the rules unambiguous, they agreeon the numerical values A = 1, J = 11, Q = 12, and K = 13.(a) What is the expec ted numbe r of cards that Teller draws?(b) What is the expecte d maximum value among the cards Teller gives to Penn?(c) What is the expe cted minimum value among the cards Teller gives to Penn?(d) What is the expecte d number of cards that Teller gives to Penn?Full credit will be given only for exact answers (with correct proofs, of course).1In a standard deck of 52 cards, each card has a suit in the set {♠, ♥, ♣, ♦} and a value in the set{A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K}, and every possible suit-value pair appears in the deck exactly once. Penn andTeller normally use exploding razor-sharp ninja throwing cards for this trick.1CS 473G Homework 0 (due September 1, 2005) Fall 20053. A rolling die maze is a puzzle involving a standard six-sided die2and a grid of squares. Youshould imagine the grid lying on top of a table; the die always rests on and exactly coversone square. In a single ste p, you can roll the die 90 degrees around one of its bottom edges,moving it to an adjacent square one step north, south, east, or west.Rolling a die.Some squares in the grid may be blocked ; the die can never rest on a blocked square. Othersquares may be labeled with a number; whenever the die rests on a labeled square, the numberof pips on the top face of the die must equal the label. Squares that are neither labeled normarked are free. You may not roll the die off the edges of the grid. A rolling die maze issolvable if it is possible to place a die on the lower left square and roll it to the upper rightsquare under these constraints.For example, here are two rolling die mazes. Black squares are blocked. The maze on the leftcan be solved by placing the die on the lower left square with 1 pip on the top face, and thenrolling it north, then north, then east, then east. The maze on the right is not solvable.Two rolling die mazes. Only the maze on the left is solvable.(a) Suppose the input is a two-dimensional array L[1 .. n][1 .. n], where each entry L[i][j]stores the label of the square in the ith row and jth column, where 0 means the squareis free and −1 means the square is blocked. Describe and analyze a polynomial-timealgorithm to determine whether the given rolling die maze is solvable.?(b) Now suppose the maze is specified implicitly by a list of labeled and blocked squares.Specifically, suppose the input consists of an integer M, specifying the height and widthof the maze, and an array S[1 .. n], where each entry S[i] is a triple (x, y, L) indicatingthat square (x, y) has label L. As in the explicit encoding, label −1 indicates that thesquare is blocked; free squares are not listed in S at all. Describe and analyze an effic ientalgorithm to determine whether the given rolling die maze is solvable. For