CS 373: Combinatorial Algorithms - Huihoo
CS 373: Combinatorial AlgorithmsUniversity of Illinois, Urbana-ChampaignInstructor: Jeff EricksonTeaching Assistants: Spring 1999: Mitch Harris and Shripad Thite Summer 1999 (IMCS): Mitch Harris Summer 2000 (IMCS): Mitch Harris Fall 2000: Chris Neihengen, Ekta Manaktala, and Nick Hurlburt Spring 2001: Brian Ensink, Chris Neihengen, and Nick Hurlburt Summer 2001 (I2CS): Asha Seetharam and Dan Bullok Fall 2002: Erin Wolf, Gio Kao, Kevin Small, Michael Bond, Rishi Talreja, Rob McCann, and Yasutaka Furakawac Copyright 1999, 2000, 2001, 2002, 2003 Jeff Erickson.This work may be freely copied and distributed.It may not be sold for more than the actual cost of reproduction.This work is distributed under a Creative Commons license; see For the most recent edition, see http://www.uiuc.edu/ jeffe/teaching/373/.
For junior faculty, it may be a choice between a book and tenure.— George A. Bekey, “The Assistant Professor’s Guide to the Galaxy” (1993)I’m writing a book. I’ve got the page numbers done.— Stephen WrightAbout These NotesThis course packet includes lecture notes, homework questions, and exam questions from thecourse ‘CS 373: Combinatorial Algorithms’, which I taught at the University of Illinois in Spring1999, Fall 2000, Spring 2001, and Fall 2002. Lecture notes and videotapes lectures were also usedduring Summer 1999, Summer 2000, Summer 2001, and Fall 2002 as part of the UIUC computerscience department’s Illinois Internet Computer Science (I2CS) program.The recurrences handout is based on samizdat, probably written by Ari Trachtenberg, basedon a paper by George Lueker, from an earlier semester taught by Ed Reingold. I wrote mostof the lecture notes in Spring 1999; I revised them and added a few new notes in each followingsemester. Except for the infamous Homework Zero, which is entirely my doing, homework andexam problems and their solutions were written mostly by the teaching assistants: Asha Seetharam,Brian Ensink, Chris Neihengen, Dan Bullok, Ekta Manaktala, Erin Wolf, Gio Kao, Kevin Small,Michael Bond, Mitch Harris, Nick Hurlburt, Rishi Talreja, Rob McCann, Shripad Thite, and YasuFurakawa. Lecture notes were posted to the course web site a few days (on average) after eachlecture. Homeworks, exams, and solutions were also distributed over the web. I have deliberatelyexcluded solutions from this course packet.The lecture notes, homeworks, and exams draw heavily on the following sources, all of which Ican recommend as good references. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974. (This was the textbook for the algorithms classesI took as an undergrad at Rice and as a masters student at UC Irvine.) Sara Baase and Allen Van Gelder. Computer Algorithms: Introduction to Design and Analysis. Addison-Wesley, 2000. Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, 1997. (This is the requiredtextbook in my computational geometry course.) Thomas Cormen, Charles Leiserson, Ron Rivest, and Cliff Stein. Introduction to Algorithms,second edition. MIT Press/McGraw-Hill, 2000. (This is the required textbook for CS 373,although I never actually use it in class. Students use it as a educated second opinion. I usedthe first edition of this book as a teaching assistant at Berkeley.) Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to theTheory of NP-Completeness. W. H. Freeman, 1979. Michael T. Goodrich and Roberto Tamassia. Algorithm Design: Foundations, Analysis, andInternet Examples. John Wiley & Sons, 2002. Dan Gusfield. Algorithms on Strings, Trees, and Sequences: Computer Science and MolecularBiology. Cambridge University Press, 1997. Udi Manber. Introduction to Algorithms: A Creative Approach. Addison-Wesley, 1989.(I used this textbook as a teaching assistant at Berkeley.)
Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge UniversityPress, 1995. Ian Parberry. Problems on Algorithms. Prentice-Hall, 1995. (This was a recommendedtextbook for early versions of CS 373, primarily for students who needed to strengthen theirprerequisite knowledge. This book is out of print, but can be downloaded as karmaware fromhttp://hercule.csci.unt.edu/ ian/books/poa.html .) Robert Sedgewick. Algorithms. Addison-Wesley, 1988. (This book and its sequels have byfar the best algorithm illustrations anywhere.) Robert Endre Tarjan. Data Structures and Network Algorithms. SIAM, 1983. Class notes from my own algorithms classes at Berkeley, especially those taught by Dick Karpand Raimund Seidel. Various journal and conference papers (cited in the notes). Google.Naturally, everything here owes a great debt to the people who taught me this algorithm stuffin the first place: Abhiram Ranade, Bob Bixby, David Eppstein, Dan Hirshberg, Dick Karp, EdReingold, George Lueker, Manuel Blum, Mike Luby, Michael Perlman, and Raimund Seidel. I’vealso been helped immensely by many discussions with colleagues at UIUC—Ed Reingold, EdgarRaoms, Herbert Edelsbrunner, Jason Zych, Lenny Pitt, Mahesh Viswanathan, Shang-Hua Teng,Steve LaValle, and especially Sariel Har-Peled—as well as voluminous feedback from the studentsand teaching assistants. I stole the overall course structure (and the idea to write up my ownlecture notes) from Herbert Edelsbrunner.We did the best we could, but I’m sure there are still plenty of mistakes, errors, bugs, gaffes,omissions, snafus, kludges, typos, mathos, grammaros, thinkos, brain farts, nonsense, garbage,cruft, junk, and outright lies, all of which are entirely Steve Skiena’s fault. I revise and updatethese notes every time I teach the course, so please let me know if you find a bug. (Steve is unlikelyto care.)When I’m teaching CS 373, I award extra credit points to the first student to post an explanation and correction of any error in the lecture notes to the course newsgroup (uiuc.class.cs373).Obviously, the number of extra credit points depends on the severity of the error and the qualityof the correction. If I’m not teaching the course, encourage your instructor to set up a similarextra-credit scheme, and forward the bug reports to Steve me!Of course, any other feedback is also welcome!Enjoy!— JeffIt is traditional for the author to magnanimously accept the blame for whatever deficienciesremain. I don’t. Any errors, deficiencies, or problems in this book are somebody else’s fault,but I would appreciate knowing about them so as to determine who is to blame.— Steven S. Skiena, The Algorithm Design Manual, Springer-Verlag, 1997, page x.
CS 3731Notes on Solving Recurrence RelationsFun with Fibonacci numbersConsider the reproductive cycle of bees. Each male bee has a mother but no father; each femalebee has both a mother and a father. If we examine the generations we see the following family tree: We easily see that the number of ancestors in each generation is the sum of the two numbersbefore it. For example, our male bee has three great-grandparents, two grandparents, and oneparent, and 3 2 1. The number of ancestors a bee has in generation n is defined by theFibonacci sequence; we can also see this by applying the rule of sum.As a second example, consider light entering two adjacent planes of glass:At any meeting surface (between the two panes of glass, or between the glass and air), the lightmay either reflect or continue straight through (refract). For example, here is the light bouncingseven times before it leaves the glass.In general, how many different paths can the light take if we are told that it bounces n times beforeleaving the glass?The answer to the question (in case you haven’t guessed) rests with the Fibonacci sequence.We can apply the rule of sum to the event E constituting all paths through the glass in n bounces.We generate two separate sub-events, E 1 and E2 , illustrated in the following picture.1
CS 373Notes on Solving Recurrence RelationsSub-event E1 : Let E1 be the event that the first bounce is not at the boundary betweenthe two panes. In this case, the light must first bounce off the bottom pane, or else we aredealing with the case of having zero bounces (there is only one way to have zero bounces).However, the number of remaining paths after bouncing off the bottom pane is the same asthe number of paths entering through the bottom pane and bouncing n 1 bounces more.Entering through the bottom pane is the same as entering through the top pane (but flippedover), so E1 is the number of paths of light bouncing n 1 times.Sub-event E2 : Let E2 be the event that the first bounce is on the boundary between thetwo panes. In this case, we consider the two options for the light after the first bounce: itcan either leave the glass (in which case we are dealing with the case of having one bounce,and there is only one way for the light to bounce once) or it can bounce yet again on the topof the upper pane, in which case it is equivalent to the light entering from the top with n 2bounces to take along its path.By the rule of sum, we thus get the following recurrence relation for F n , the number of pathsin which the light can travel with exactly n bounces. There is exactly one way for the light totravel with no bounces—straight through—and exactly two ways for the light to travel with onlyone bounce—off the bottom and off the middle. For any n 1, there are F n 1 paths where thelight bounces off the bottom of the glass, and F n 2 paths where the light bounces off the middleand then off the top.F0 1F1 2Fn Fn 1 Fn 2Stump a professorWhat is the recurrence relation for three panes of glass? This question once stumped an anonymousprofessor1 in a science discipline, but now you should be able to solve it with a bit of effort. Aren’tyou proud of your knowledge?1Not me! —Jeff2
CS 3732Notes on Solving Recurrence RelationsSequences, sequence operators, and annihilatorsWe have shown that several different problems can be expressed in terms of Fibonacci sequences,but we don’t yet know how to explicitly compute the nth Fibonacci number, or even (and moreimportantly) roughly how big it is. We can easily write a program to compute the n th Fibonaccinumber, but that doesn’t help us much here. What we really want is a closed form solution for theFibonacci recurrence—an explicit algebraic formula without conditionals, loops, or recursion.In order to solve recurrences like the Fibonacci recurrence, we first need to understand operationson infinite sequences of numbers. Although these sequences are formally defined as functions ofthe form A : IN IR, we will write them either as A ha 0 , a1 , a2 , a3 , a4 , . . .i when we want toemphasize the entire sequence2 , or as A hai i when we want to emphasize a generic element. Forexample, the Fibonacci sequence is h0, 1, 1, 2, 3, 5, 8, 13, 21, . . .i.We can naturally define several sequence operators:We can add or subtract any two sequences:hai i hbi i ha0 , a1 , a2 , . . .i hb0 , b1 , b2 , . . .i ha0 b0 , a1 b1 , a2 b2 , . . .i hai bi ihai i hbi i ha0 , a1 , a2 , . . .i hb0 , b1 , b2 , . . .i ha0 b0 , a1 b1 , a2 b2 , . . .i hai bi iWe can multiply any sequence by a constant:c · hai i c · ha0 , a1 , a2 , . . .i hc · a0 , c · a1 , c · a2 , . . .i hc · ai iWe can shift any sequence to the left by removing its initial element:Ehai i Eha0 , a1 , a2 , a3 , . . .i ha1 , a2 , a3 , a4 , . . .i hai 1 iExample: We can understand these operators better by looking at some specific examples, usingthe sequence T of powers of two.T h20 , 21 , 22 , 23 , . . .i h2i iET h21 , 22 , 23 , 24 , . . .i h2i 1 i2T h2 · 20 , 2 · 21 , 2 · 22 , 2 · 23 , . . .i h21 , 22 , 23 , 24 , . . .i h2i 1 i2T ET h21 21 , 22 22 , 23 23 , 24 24 , . . .i h0, 0, 0, 0, . . .i h0i2.1Properties of operatorsIt turns out that the distributive property holds for these operators, so we can rewrite ET 2T as(E 2)T . Since (E 2)T h0, 0, 0, 0, . . .i, we say that the operator (E 2) annihilates T , and wecall (E 2) an annihilator of T . Obviously, we can trivially annihilate any sequence by multiplyingit by zero, so as a technical matter, we do not consider multiplication by 0 to be an annihilator.What happens when we apply the operator (E 3) to our sequence T ?(E 3)T ET 3T h2i 1 i 3h2i i h2i 1 3 · 2i i h 2i i TThe operator (E 3) did very little to our sequence T ; it just flipped the sign of each number inthe sequence. In fact, we will soon see that only (E 2) will annihilate T , and all other simple2It really doesn’t matter whether we start a sequence with a0 or a1 or a5 or even a 17 . Zero is often a convenientstarting point for many recursively defined sequences, so we’ll usually start there.3
CS 373Notes on Solving Recurrence Relationsoperators will affect T in very minor ways. Thus, if we know how to annihilate the sequence, weknow what the sequence must look like.In general, (E c) annihilates any geometric sequence A ha 0 , a0 c, a0 c2 , a0 c3 , . . .i ha0 ci i:(E c)ha0 ci i Eha0 ci i cha0 ci i ha0 ci 1 i hc · a0 ci i ha0 ci 1 a0 ci 1 i h0iTo see that this is the only operator of this form that annihilates A, let’s see the effect of operator(E d) for some d 6 c:(E d)ha0 ci i Eha0 ci i dha0 ci i ha0 ci 1 da0 ci i h(c d)a0 ci i (c d)ha0 ci iSo we have a more rigorous confirmation that an annihilator annihilates exactly one type of sequence, but multiplies other similar sequences by a constant.We can use this fact about annihilators of geometric sequences to solve certain recurrences. Forexample, consider the sequence R hr 0 , r1 , r2 , . . .i defined recursively as follows:r0 3ri 1 5riWe can easily prove that the operator (E 5) annihilates R:(E 5)hri i Ehri i 5hri i hri 1 i h5ri i hri 1 5ri i h0iSince (E 5) is an annihilator for R, we must have the closed form solution r i r0 5i 3 · 5i . Wecan easily verify this by induction, as follows:r0 3 · 5 0 3[definition]Xri 5ri 1[definition] 5 · (3 · 5i 5 ·32.2i 1)[induction hypothesis][algebra]XMultiple operatorsAn operator is a function that transforms one sequence into another. Like any other function, we canapply operators one after another to the same sequence. For example, we can multiply a sequencehai i by a constant d and then by a constant c, resulting in the sequence c(dha i i) hc·d·ai i (cd)hai i.Alternatively, we may multiply the sequence by a constant c and then shift it to the left to getE(chai i) Ehc · ai i hc · ai 1 i. This is exactly the same as applying the operators in thereverse order: c(Ehai i) chai 1 i hc · ai 1 i. We can also shift the sequence twice to the left:E(Ehai i) Ehai 1 i hai 2 i. We will write this in shorthand as E 2 hai i. More generally, theoperator Ek shifts a sequence k steps to the left: E k hai i hai k i.We now have the tools to solve a whole host of recurrence problems. For example, whatannihilates C h2i 3i i? Well, we know that (E 2) annihilates h2 i i while leaving h3i i essentiallyunscathed. Similarly, (E 3) annihilates h3 i i while leaving h2i i essentially unscathed. Thus, if weapply both operators one after the other, we see that (E 2)(E 3) annihilates our sequence C.In general, for any integers a 6 b, the operator (E a)(E b) annihilates any sequence of theform hc1 ai c2 bi i but nothing else. We will often ‘multiply out’ the operators into the shorthandnotation E2 (a b)E ab. It is left as an exhilarating exercise to the student to verify that this4
CS 373Notes on Solving Recurrence Relationsshorthand actually makes sense—the operators (E a)(E b) and E 2 (a b)E ab have thesame effect on every sequence.We now know finally enough to solve the recurrence for Fibonacci numbers. Specifically, noticethat the recurrence Fi Fi 1 Fi 2 is annihilated by E2 E 1:(E2 E 1)hFi i E2 hFi i EhFi i hFi i hFi 2 i hFi 1 i hFi i hFi 2 Fi 1 Fi i h0iFactoring E2 E 1 using the quadratic formula, we obtainE2 E 1 (E φ)(E φ̂) where φ (1 5)/2 1.618034 is the golden ratio and φ̂ (1 5)/2 1 φ 1/φ. Thus,the operator (E φ)(E φ̂) annihilates the Fibonacci sequence, so F i must have the formFi cφi ĉφ̂ifor some constants c and ĉ. We call this the generic solution to the recurrence, since it doesn’tdepend at all on the base cases. To compute the constants c and ĉ, we use the base cases F 0 0and F1 1 to obtain a pair of linear equations:F0 0 c ĉF1 1 cφ ĉφ̂ Solving this system of equations gives us c 1/(2φ 1) 1/ 5 and ĉ 1/ 5.We now have a closed-form expression for the ith Fibonacci number: !i !i1φi φ̂i11 51 5 Fi 22555With all the square roots in this formula, it’s quite amazing that Fibonacci numbers are integers.However, if we do all the math correctly, all the square roots cancel out when i is an integer. (Infact, this is pretty easy to prove using the binomial theorem.)2.3Degenerate casesWe can’t quite solve every recurrence yet. In our above formulation of (E a)(E b), we assumedthat a 6 b. What about the operator (E a)(E a) (E a) 2 ? It turns out that this operatorannihilates sequences such as hiai i:(E a)hiai i h(i 1)ai 1 (a)iai i h(i 1)ai 1 iai 1 i hai 1 i(E a)2 hiai i (E a)hai 1 i h0iMore generally, the operator (E a) k annihilates any sequence hp(i) · ai i, where p(i) is anypolynomial in i of degree k 1. As an example, (E 1) 3 annihilates the sequence hi2 · 1i i hi2 i h1, 4, 9, 16, 25, . . .i, since p(i) i2 is a polynomial of degree n 1 2.As a review, try to explain the following statements:5
CS 373Notes on Solving Recurrence Relations(E 1) annihilates any constant sequence hαi.(E 1)2 annihilates any arithmetic sequence hα βii.(E 1)3 annihilates any quadratic sequence hα βi γi 2 i.(E 3)(E 2)(E 1) annihilates any sequence hα β2 i γ3i i.(E 3)2 (E 2)(E 1) annihilates any sequence hα β2 i γ3i δi3i i.2.4SummaryIn summary, we have learned several operators that act on sequences, as well as a few ways ofcombining operators.OperatorAdditionSubtractionScalar multiplicationShiftComposition of operatorsk-fold shiftDefinitionhai i hbi i hai bi ihai i hbi i hai bi ichai i hcai iEhai i hai 1 i(X Y)hai i Xhai i Yhai i(X Y)hai i Xhai i Yhai iXYhai i X(Yhai i) Y(Xhai i)Ek hai i hai k iNotice that we have not defined a multiplication operator for two sequences. This is usuallyaccomplished by convolution: * iXaj bi j .hai i hbi i j 0Fortunately, convolution is unnecessary for solving the recurrences we will see in this course.We have also learned some things about annihilators, which can be summarized as follows:Sequence Annihilatorhαi E 1αai E aαai βbi (E a)(E b)iiα0 a0 α1 a1 · · · αn ain (E a0 )(E a1 ) · · · (E an )hαi βi (E 1)2(αi β)ai (E a)2(αi β)ai γbi (E a)2 (E b)(α0 α1 i · · · αn 1 in 1 )ai (E a)nIf X annihilates hai i, then X also annihilates chai i for any constant c.If X annihilates hai i and Y annihilates hbi i, then XY annihilates hai i hbi i.33.1Solving Linear RecurrencesHomogeneous RecurrencesThe general expressions in the annihilator box above are really the most important things toremember about annihilators because they help you to solve any recurrence for which you canwrite down an annihilator. The general method is:6
CS 373Notes on Solving Recurrence Relations1.2.3.4.5.Write down the annihilator for the recurrenceFactor the annihilatorDetermine the sequence annihilated by each factorAdd these sequences together to form the generic solutionSolve for constants of the solution
Alfred V. Aho, John E. Hopcroft, and Je rey D. Ullman. The Design and Analysis of Com-puter Algorithms. Addison-Wesley, 1974. (This was the textbook for the algorithms classes I took as an undergrad at Rice and as a masters student at UC Irvine.) Sara Baase and Allen Van Gelder. Computer Algorithms
strong Combinatorial Chemistry /strong in Drug Research strong Combinatorial chemistry /strong and rational drug design Structure-based and computer-assisted design and virtual screening (LUDI, FlexX et al.) of protein ligands supplement strong combinatorial chemistry /strong . strong Combinatorial /strong design of drugs The necessary tools are already available but scoring functions have to be improved.
In this course we study algorithms for combinatorial optimization problems. Those are . and so it is unlikely that we can design exact e cient algorithms for them. For such problems, we will study algorithms that are worst-case e cient, but that output . make us give a second look at the theory of linear programming duality. Online Algorithms.File Size: 832KB
In this paper we give the fist polynomial-time combinatorial algorithms1 for the generalized circulation problem.The importance of designing such algorithms for this problem is twofold. Combinatorial methods may lead to algorithms that are more efficient, both in theory and in practice, than al
1 Introduction to Combinatorial Algebraic Topology Basic Topology Graphs to Simplicial Complexes Posets to Simplicial Complexes 2 Permutation Patterns Introduction and Motivation Applying Combinatorial Algebraic Topology Kozlov, Dimitry. Combinatorial algebraic topology. Vol. 21. Springer Science & Business Media, 2008.
topology and di erential geometry to the study of combinatorial spaces. Per-haps surprisingly, many of the standard ingredients of di erential topology and di erential geometry have combinatorial analogues. The combinatorial theories This work was partially supported by the National Science Foundation and the National Se-curity Agency. 177
Integrating natural product synthesis and combinatorial chemistry*,† A.Ganesan Department of Chemistry, University of Southampton, Southampton SO17 1BJ, United Kingdom Abstract: The fields of natural product total synthesis and combinatorial chemistry have major differences as well as much in common. Unique to combinatorial chemistry is the need
62) A carpenter cuts a piece 1 1 2 feet long from a cedar plank that is 18 feet long. How long is the remaining piece? A) 16 feet B) 16 1 2 feet C) 17 1 2 feet D) 17 feet Perform the indicated operation. Simplify your answers. 63) Find the average of 4 5, 5 6, and 1 7. A) 373 70 B) 373 420 C) 373 210 D) 373 630 64) 4 9 2 4 9-1 14 A) 224 47 B .
Siklus Akuntansi Jasa BAGIAN PROYEK PENGEMBANGAN KURIKULUM DIREKTORAT PENDIDIKAN MENENGAH KEJURUAN DIREKTORAT JENDERAL PENDIDIKAN DASAR DAN MENENGAH DEPARTEMEN PENDIDIKAN NASIONAL 2003 Kode Modul: AK.26.D.2,3. BAGIAN PROYEK PENGEMBANGAN KURIKULUM DIREKTORAT PENDIDIKAN MENENGAH KEJURUAN DIREKTORAT JENDERAL PENDIDIKAN DASAR DAN MENENGAH DEPARTEMEN PENDIDIKAN NASIONAL 2003 Kode Modul: AK.26.D.2,3 .
