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).

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.

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

Homeworks and Exams

Solutions were posted to the course web site after each homework and exam was submitted, but for rather obvious reasons, you can't get them here. I will gladly email solutions to interested instructors. Subjects covered in each homework and exam vary from semester to semester depending on the lecture schedule.

Eventually, I'll post homeworks and exams from Fall 2001 and Spring 2002, when the class was taught by Sariel Har-Peled. Stay tuned!

Administrivia

Prerequisites:
Students are assumed to have working knowledge of the material taught in CS 225 and CS 273. This is not the same as merely having passed! In particular, I assume that all students have a gut-level understanding of induction and recursion. Undergraduates who have not taken both 225 and 273 need my permission to enroll.

Coursework:
Grades are based on 6 homeworks (30%) (dropping the lowest), two in-class midterms (20% each), and a final exam (30%). Undergraduates and graduate students are graded on separate curves. Graduate students have some additional homework and exam problems; undergrads can solve the graduate homework problems for extra credit. There is no distinction between 3/4-unit and 1-unit graduate students.

Required Textbook:
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 2nd edition. MIT Press / McGraw-Hill, 2001.

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.

Recommended Textbooks:
Theodore S. Geisel [Dr. Seuss]. The Cat in the Hat Comes Back. Random House, 1958.

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.

Thanks

The preface to the lecture notes gives a long list of people who helped (either directly or indirectly) with the development of these course materials. I want to especially thank my teaching assistants, without whom teaching a course of 200+ students would be impossible. In particular, the TAs wrote most of the homework problems and solutions. 
|> 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.

- John Bastian, comp.games.development.programming.misc, September 13, 1999

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.
Jeff Erickson ([email protected]) 07 Jul 2003