The course meets 9.30--10.45 am Tuesday and Thursday at 3505 Seamans Center.

Kasturi Varadarajan, 101D MacLean Hall, Phone: 335-0732, email:firstname-lastname@uiowa.edu. Office hours: 11.00--12.00 am Mon, Tue, Wed.

Let us postpone a discussion of what this course is *really* about
to the end of the course. Those who can't wait to see the real motivation can peek at Section 0.6 (page 11) of Jeff Erickson's lecture notes.

It is easier to describe the mechanics of the course. We will practise the precise statement of various computational problems, think about different strategies or algorithms to solve them, reason about their correctness, evaluate these algorithms from the point of view of efficiency (usually running time), and develop a feel for the difficulty of problems and the applicability of various techniques we will learn. It is convenient to organize the course in terms of the following topics:

- Divide-and-Conquer
- Randomized Algorithms
- Dynamic programming
- Greedy Algorithms
- Network Flow
- NP-completeness

We will cover *two* other topics, possibly from the following list:
exact algorithms for hard problems, approximation algorithms, more
of probabilistic algorithms, basic computational geometry algorithms, introduction to linear programming.

Algorithm Design, by Kleinberg and Tardos.

We will assume effectively an exposure to an undergraduate data structures course, so that when we talk about algorithms, you are comfortable at seeing how they might translate into programs. This also means you have seen the mechanics of analyzing the running time of simple algorithms. It helps to have also been exposed to an undergraduate algorithms course, in particular, to topics such as graph exploration (breadth first search, depth first search), and shortest path algorithms. Beyond this, we won't assume familiarity with specific topics, but rather hope for a certain maturity.

The grading will be based on about seven homeworks (40 percent), a midterm (25 percent), and a final (35 percent). One or two of the homeworks will be based on programming.

The policy on late homeworks is that you have a quota of three days for the entire semester that you may use for late submissions. So for example, there will be no penalty if you submit the third homework a day late, the fifth two days late, and the rest of the homeworks on time. Once you use up your quota of three days, any homework submitted late will not be accepted and you will get 0 points for that homework.

When you submit a homework X days late, your quota gets decreased by X irrevocably. You can only be late by an integer number of days -- if you submit 10 hours after the deadline, for example, your quote is depleted by one day.

- First Day Handout.
- The First Homework, due in class on Tuesday, Jan 31.
- The second Homework, due in class on Tuesday, Feb 14.
- The third Homework, due 11:59 pm on Tuesday, Feb 28.
- The fourth Homework, due in class on Thursday, March 29.
- The fifth Homework, due in class on Thursday, April 12.
- The sixth and last homework, due in class on Tuesday, May 1.