Fall 2007: Algorithms, 22C:031:001


The course meets 2.30--3.45 pm Tuesday and Thursday at 112 MacBride Hall


We will study various computational problems using the lens of algorithmic analysis. While the lens itself is motivated by issues of efficiency in terms of running time or space, we will see that the lens leads to some very interesting solutions and general algorithmic techniques. We will also see that computational problems that look very similar to the naked eye appear very different when viewed through the lens.

For our textbook, we will use "Algorithm Design" by Jon Kleinberg and Eva Tardos. We will focus on the following portions corresponding to the text:

This is just the preliminary plan and it will certainly undergo modifications. We will also not stick to the order suggested above.


The main prerequisite is 22C:21 (Data Structures), see for instance this previous offering. In particular, we will assume that we have implemented or are capable of readily implementing the basic graph traversal and shortest path algorithms as well as the usual sorting algorithms. This experience will allow us to discuss algorithms at the level of pseudo-code while assuming facility at being able to translate pseudo-code to actual programs.


The grading will be based on seven homeworks (6 points each), two midterms (15 points each) and a final (28 points). Two of the seven homeworks will require progarmming. The midterms will be held in class on Tuesday, October 2 and Tuesday, November 6.

Final Exam

The final exam will be held at 12.00 pm, Wednesday, December 19 in our regular classroom. The exam will be for two hours. It will be based on the chapters on dynamic programming (Chapter 6) and NP and Computational Intractability (Chapter 8).

Teaching Assistant

Vani Murarka. Office hours: Monday and Friday 2.00--3.00 pm. Office location: B20J, MacLean Hall. Email: firstname-lastname@uiowa.edu

Instructor Office Hours

10.30--11.30 am, Monday, Tuesday, and Wednesday.

Course Handouts