The course meets 2.30--3.45 pm Tuesday and Thursday at E105, Adler Journalism and Mass Comm. Bldg.

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:

- Introduction to algorithm design and analysis (Chapters 1 and 2)
- Greedy Algorithms (Chapter 4)
- Divide and Conquer (Chapter 5)
- Dynamic Programming (Chapter 6)
- NP and Computational Intractability (Chapter 8)

We will also cover some material from outside the text, including single pass algorithms for large data streams. Please see notes for Lectures 20 and 21 from a previous offering of the course.

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 first midterm will be in class on Thursday, October 2. The second midterm will be in class on Thursday, November 6. The final Exam is on Tuesday, December 16, from 2.15--4.15 pm, at a location to be announced later.

Lu Bi. Office hours (new): 3.55--5.25 pm, Wed and Thu. Office location: B20J, MacLean Hall. Email: firstname-lastname@uiowa.edu

1.30--3.00 pm, Monday and Wednesday.

- 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.
- A first midterm exam from a previous offering
- Homework 3, posted September 29, due in class on October 9. Source code to be submitted via icon by October 9. You can use Java, C#, or C++ as your programming language.
- Homework 4, posted October 14, due in class on October 23.
- Students who but did not get a positive score on Homework 3, please re-do by October 30 for half the credit.
- Homework 5 , posted November 6, due in class November 13.
- Homework 6 , posted November 18, due in class December 2.
- Homework 7, posted December 2, due December 11. Submit using ICON into the designated folder by 11:59 pm on December 11. Three test files: input1.txt, input2.txt, input3.txt.