# Fall 2008: Design and Analysis of Algorithms, 22C:231:001

## Coordinates

The course meets 3.55--5.10 pm Tuesday and Thursday at
105, MacLean Hall

## Content

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:

- Divide and Conquer (Chapter 5)
- Randomized Algorithms (Chapter 13)
- Dynamic Programming (Chapter 6)
- Network Flow (Chapter 7)
- NP and Computational Intractability (Chapter 8)
- Approximation Algorithms (Chapter 11)
- Local Search and Nash equilibria (Chapter 12)

We will also cover some material from research articles
not covered in the text.

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

## Prerequisites

Though we will quickly review this, we will assume that
the student is familiar with the idea of analyzing the
running time of algorithms. We will assume familiarity
with graph search algorithms like breadth-first-search,
and experience of or comfort at implementing very basic data
structures and algorithms.

## Grading

The grading will be based on five or six homeworks (40 points), one
of which will involve programming, one midterm (25 points) and a final
(35 points).

## Exam Dates

The Midterm will be in class on Tuesday, October 14. The Final exam is on
Monday Dec 15 between 2.15 -- 4.15 pm at a location to be announced later.

## Teaching Assistant

Matthew Gibson. Office hours: 1.00-2.00 pm, Tuesday.
Office location: 101C, MacLean Hall. Email: firstname-lastname@uiowa.edu

## Instructor Office Hours

1.30--3.00 pm, Monday and Wednesday.

## Handouts and Homeworks

- First Day Handout
- Homework 1, posted September 2, due in
class on September 11
- Homework 2, posted September 12, due in
class on September 23. Please see this update
, posted September 16.
- Homework 3, posted September 30, due
in class October 9. Deadline extended to monday, October 13, 2.00 pm.
- Homework 4, posted October 17, due in
class on October 28
- Homework 5, posted November 13, due
in class on December 2. Corrected Nov 25.
- Homework 6: Study Sections 12.1 and 12.2 of Chapter 12.