Sep 7, 2009

Jeff Erickson's Algorithms Course Materials

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.

Creative Commons License
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

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

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

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.


No comments:

Post a Comment

Subscribe to: Post Comments (Atom)