# Fall 2017: Algorithms, CS:3330:0002 (22C:031:001)

## Coordinates

The course meets 3:30--4:45 pm Tuesday and Thursday
at 110 MLH (MacLean Hall).

## Instructor

Kasturi Varadarajan, 101D MacLean Hall, Phone: 335-0732, email:firstname-lastname@uiowa.edu.

Office Hours: 3:00--4:30 pm Monday and 1:30--3:00 pm Wednesday.

## Textbook

Our text is *Algorithm Design*, by Kleinberg and Tardos. As a
reference, we may also use the lecture notes from Jeff Erickson.

In this course, we will think about different strategies for solving precisely stated computational problems, 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. We will encounter fundamental algorithms such as basic graph algorithms. Developing algorithmic intuition and learning to communicate algorithms effectively will be emphasized. It is convenient to organize the course in terms of the following topics:

- Introduction
- Basic Graph Algorithms
- Greedy Algorithms and Analysis
- Recursive thinking: Divide-and-Conquer
- Recursive thinking: Dynamic Programming
- Network Flow and applications
- NP-completeness

These topics are essentially the first eight chapters of our textbook. Along the way, we will also encounter examples of randomized algorithms.

## Prerequisites

CS:2230 (Data Structures), CS:2210, and (MATH:1850 or MATH:1550)
## Grading

The grading will be based on approximately eight homeworks (25 percent of the final grade), two
in-class midterm exams (20 percent each), and a final (35 percent). About 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.
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 no credit 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 quota is depleted
by one day.

## Exam Dates

The midterms will be in class on Thursday, October 5, and Thursday,
November 9. The final will be during finals week, and I will post the
coordinates here once they become available.
## Teaching Assistants

Heather Kemp and Kallin Khan. Email:firstname-lastname@uiowa.edu. Heather's office hours: Mondays, 8:30 am to 10:00 am, room 201A, MLH. Khan's office hours: Thursdays, 9:30 am to 11:00 am, room 101N, MLH.
## What We Covered Each Week

We will keep track of what we covered each week
here.

## Handouts and Homeworks

- First Day Handout
- Homework 1, due in class Thursday, September 7.
- Homework 2, due in class Thursday, September 21.
- Homework 3, due 11:59 pm Tuesday, October 3.
- Homework 4, due in class Tuesday, October 17.
- Homework 5, due in class Thursday, October 26.