CS 373: Combinatorial Algorithms
CS 373 is the standard senior-level algorithms class required of every computer science undergraduate and graduate student at the University of Illinois (unless you take the automata theory class CS 375, but relatively few students do that). This page contains all the teaching materials that my TAs and I have developed during the five times I've taught the course (thrice in reality and twice virtually).
- Lecture notes
- Homeworks and exams
- Administrivia
- Thanks
- What to do if 373 is already full
- An open letter to Internet students
All material on this web page is Copyright © 1999, 2000, 2001, 2002, 2003 Jeff Erickson. Anything on this page may be freely downloaded, printed, copied, or distributed, 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're a lawyer, read the legaleze.
This work is licensed under a Creative Commons License.Feedback of any kind is always welcome, especially bug reports. I would especially appreciate hearing from anyone outside UIUC who finds this stuff useful (or useless)!
Lecture Notes
These notes are listed in the order they were used in Fall 2002, with notes from other semesters and other handouts sprinkled in appropriate places. Different notes were used in different semesters, and I haven't written notes for every lecture. Most of these notes have more that one lecture's worth of material. (I usually take about 15 minutes to cover a single page, or about five pages per 75-minute lecture; your mileage may vary.)Fall 2003 UIUC students: Printed and bound copies of these notes will be available at a local copy shop very soon; stay tuned for details. Buying a bound copy is probably more convenient than downloading and printing everything yourself!
- All the lecture notes in one huge file (197 pages) [ps.gz]
- Title page and preface [ps.gz]
- Background
- Randomized algorithms
- Amortized analysis
- Graph algorithms
- Seminumerical algorithms
- String matching
- Computational Geometry
- Lower bounds
I do not actually assign reading or homework problems from CLRS. In fact, I have a standing rule that if a topic isn't covered in the posted lecture notes, it won't be on the homeworks or exams, even if I talk about it in class and it's covered in CLRS. Nevertheless, CLRS is an excellent reference for all things algorithmic. Students are strongly encouraged to consult CLRS if they find something in the lecture notes confusing or unclear.
One of the best books ever written about recursion. And toilets.
In past semesters, I also recommended Ian Parberry's book Problems on Algorithms (Prentice-Hall, 1995), especially for students who need to strengthen their background knowledge. This book is now out of print (and even when it wasn't, we could only get crappy Xeroxed copies from the publisher), but it can be downloaded from Ian's web site as karmaware.
|> Algorithms are ok, but it has too much of an academic feel to me |> to be fun. yes, but hey! you need algorithms to make decent programs. it's like two builders saying "yer, using bricks and mortar is just too academic. Me? I like wood and nails", but with wood and nails you build... what? cubby houses. houses in trees. dog kennels. the guy with the bricks and mortar builds other things.
Today, I sometimes interview recent grads for software design jobs. One standard problem I pose is "Write a routine, in any programming language of your choice (I've probably seen it), that sorts an array of things according to some ordering scheme. I don't care about efficiency, but I expect the following: (a) that it is correct, (b) that you can explain the complexity of the algorithm in "O(n)" notation." Of course I expect a bubble sort of integers. One smartass did a Shell sort and got it right. But over 90% of the candidates fail this basic test. That's sad.
The scary part is that peer reviewers think this is being "too hard" on a candidate.
-- Rene Hollan, slashdot.org, 17 Oct 2001.