[linuxkernelnewbies] Jeff Erickson's Algorithms Course Materials

[peter teoh]

Thank you Jeff Erickson for the free materials!!!! http://compgeom.cs.uiuc.edu/~jeffe//teaching/algorithms/ Algorithms Course Materials by Jeff Erickson August 2009 revision This page contains all my lecture notes for the algorithms classes required for all computer science undergraduate and graduate students at the University of Illinois, Urbana-Champaign. I have taught incarnations of this course eight times: Spring 1999, Fall 2000, Spring 2001, Fall 2002, Spring 2004, Fall 2005, Fall 2006, Spring 2007, Fall 2008, and Spring 2009. These notes are numbered roughly in the order I used them in my undergraduate class, with (lettered) notes containing sprinkled in reasonable places. More advanced material is indicated by the symbol ※. More information about these notes is available after the notes themselves. A large collection of old homeworks and exams follows the lecture notes. Most of these homework and exam problems also appear at the ends of the appropriate lecture notes. Except for various Homework Zeros, which are solely my fault, most of the homework problems were written by my teaching assistants: Aditya Ramani, Alina Ene, Amir Nayyeri, Asha Seetharam, Ben Moseley, Brian Ensink, Chris Neihengen, Dan Bullok, Dan Cranston, Johnathon Fischer, Ekta Manaktala, Erin Wolf Chambers, Igor Gammer, Gio Kao, Kevin Milans, Kevin Small, Lan Chen, Michael Bond, Mitch Harris, Nick Hurlburt, Nitish Korula, Reza Zamani-Nasab, Rishi Talreja, Rob McCann, Shripad Thite, and Yasu Furakawa. Please do not ask me for solutions. If you're a student, you will (usually) learn more from trying to solve a problem and failing than by reading the answer. If you really need help, ask your instructor, your TAs, and/or your fellow students. If you're an instructor, you really shouldn't assign problems that you can't solve yourself! (Because I don't always follow my own advice, some of the problems are buggy, especially in older homeworks and exams. I've tried to keep the buggy problems out of the lecture notes themselves.) More recent version of these notes, along with current homework and exams, may be available at the official sites for the undergraduate and/or graduate algorithms classes at UIUC. Feedback of any kind is always welcome, especially bug reports. I would particularly appreciate hearing from anyone outside UIUC who finds these notes useful (or useless)! Copyright. Except as indicated otherwise, all material linked from this web page is Copyright © 1999–2009 Jeff Erickson. Anyone may freely download, print, copy, and/or distribute anything on this page, either electronically or on paper. However, nothing on this page may be sold in any form for more than the actual cost of printing and/or reproduction. For example, you are welcome to make local copies on your own web server, but you are not allowed to require an access fee (such as tuition) to view your local copy; that's the same as selling it. If you distribute these notes, please give me proper credit and please include a pointer to this web page (http://www.cs.uiuc.edu/~jeffe/teaching/algorithms). If you're a lawyer, read the legalese. This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License. You know, I could write a book. And this book would be thick enough to stun an ox. — Laurie Anderson, "Let X=X", Big Science (1982) Everything Everything in one file (765 pages) Cover material (6 pages) All lecture notes in one file (379 pages) All homework, head-banging, and exam problems in one file (386 pages) If we are ready to tolerate everything as understood, there is nothing left to explain; while if we sourly refuse to take anything, even tentatively, as clear, no explanation can be given. What intrigues us as a problem, and what will satisfy us as a solution, will depend upon the line we draw between what is already clear and what needs to be clarified. — Nelson Goodman, Fact, Fiction & Forecast (1955) Lecture Notes 0. Introduction, history, and course goals Recursion 1. Simplify and delegate A. Fast Fourier transforms ※ 2. Backtracking B. Fast exponential-time algorithms ※ 3. Dynamic programming C. Advanced dynamic programming tricks ※ 4. Greedy algorithms D. Matroids ※ Randomization 5. Nuts and bolts (randomized quicksort) 6. Treaps and skip lists E. Tail inequalities ※ 7. Uniform and universal hashing F. Randomized minimum cut Amortized analysis 8. Aggregation, taxation, potential 9. Scapegoat trees and splay trees 10. Maintaining disjoint sets ("union-find") — includes O(α(n)) amortized analysis ※ String algorithms G. Brute force, fingerprinting H. Knuth-Morris-Pratt Basic graph algorithms 11. Representations, traversal 12. Minimum spanning trees 13. Single-source shortest paths 14. All-pairs shortest paths Flows and cuts 15. Maximum flows and minimum cuts 16. Maximum flow algorithms 17. Applications of maximum flow 18. Extensions of maximum flow ※ Linear programming I. Definitions and duality ※ J. The simplex algorithm ※ Lower bounds 19. Decision trees, leaf counting 20. Adversary arguments ("n-card monte") 21. NP-hardness K. Approximation algorithms Appendix Solving recurrences Retired: These notes contain material that I have not covered in several years, and that I do not expect to cover in the future. L. Fibonacci heaps M. Number-theoretic algorithms N. Convex hulls O. Sweepline algorithms P. Polygon triangulation Q. Lower bound reductions The problem is that we attempt to solve the simplest questions cleverly, thereby rendering them unusually complex. One should seek the simple solution. — Anton Pavlovich Chekhov (c. 1890) Homeworks, Exams, and Head-Banging Sessions Johnny's algorithms homework (Fall 2000 HW 1) Spring 1999: everything Homework: hw0, hw1, hw2, hw3, hw4, hw5 Exams: midterm 1, midterm 2, final Fall 2000: everything Homework: hw0, hw1, hw2, hw3, hw4, hw5, hw6 Exams: midterm 1, midterm 2, final Spring 2001: everything Homework: hw0, hw1, hw2, hw3, hw4, hw5, hw6 Exams: midterm 1, midterm 2, final Fall 2002: everything Homework: hw0, hw1, hw2, hw3, hw4, hw5, hw6 Exams: midterm 1, midterm 2, final Spring 2004: everything Homework: hw0, hw1, hw2, hw3, hw4, hw5, hw6 Exams: midterm 1, conflict midterm 1, midterm 2, final, conflict final Fall 2005: everything Homework: hw0, hw1, hw2, hw3, hw4, hw5, hw6 Exams: midterm 1, midterm 2, final Fall 2006: everything Homework: hw0, hw1, hw2, hw3, hw4, hw5, hw6, hw7, hw8 Head-banging: hbs0, hbs1, hbs2, hbs3, hbs4, hbs5, hbs6, hbs7, hbs8, hbs9, hbs10, hbs11, hbs12, hbs13 Exams: midterm 1, midterm 2, final Spring 2007: everything Homework: hw0, hw1, hw2, hw3, hw4, hw5, Exams: midterm 1, midterm 2, final Fall 2008: everything Homework: hw0, hw1, hw2, hw3, hw4, hw5, hw6 Exams: midterm 1, midterm 2, final Spring 2009: everything Homework: hw0, hw1, hw2, hw3, hw3½, hw4, hw5, hw6, hw6½, hw6¾, hw7, hw8, hw9, hw10 Head-banging: hbs0, hbs1, hbs2, hbs3, hbs3½, hbs4, hbs5, hbs6, hbs6½, hbs6¾, hbs7, hbs8, hbs9, hbs10, hbs11 Exams: midterm 1, midterm 2, final More Information Caveat Lector. Some of these lecture notes have been used less often than others and are therefore (sometimes considerably) less complete/polished. Almost all of these notes contain more than one lecture's worth of material. In a typical 75-minute lecture, I tend to cover 4-5 pages of material—a bit more if I'm lecturing to grad students than to undergraduates. Your mileage may vary! (Arguably, that means that as I continue to add material, the label "lecture notes" becomes less and less accurate.) Alternate sources. My UIUC colleague Sariel Har-Peled maintains his own collection of algorithms lecture notes, which heavily overlap mine, although our presentation styles and specific topical choices are different, sometimes radically so. Choice is good! For people who really prefer dead trees, I recommend the textbooks by Dasgupta, Papadimitriou, and Vazirani; by Kleinberg and Tardos; and (especially for stunning oxen) by Cormen, Leiserson, Rivest, and Stein. An increasing amount of basic algorithmic material can be found at the Source of All Lies. Many more references are listed in the cover material for the lecture notes. Drawing tools. Most of the figures were drawn with OmniGraffle, but a few very old figures were drawn with xfig, and a few particularly complex figures were drawn with either Freehand or Illustrator. The map on the first page of the maxflow/mincut notes was copied from Lex Schrijver's excellent survey "On the history of combinatorial optimization (till 1960)"; the original map is from a US Government work in the public domain. Am I writing a textbook? No. All textbooks suck. (Partly that's because of the unethical rapacious profitable business practices of (most) textbook publishers—these notes will always be freely available. But also, I've never seen a textbook on any topic that I'd be willing to teach from for more than a few weeks; that's why I wrote these notes in the first place.) In particular, if these notes ever became a textbook, they would immediately suck. (Determining whether they already suck is an illuminating exercise for the reader.) Besides, have you ever talked to someone who's actually written a textbook? Do you realize how much work is involved?! No way, man. Not for me.