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:

- 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)
- Local Search (Chapter 12)
- Randomized Algorithms (Chapter 13)

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.

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).

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

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

- Lecture Notes
- First Day Handout
- Homework 1, posted September 6, due September 18 in class.
- Homework 2, posted September 20, due October 2 in class.
- Homework 1 graded and returned on September 25, along with solutions. Please see me if you want to pick up your homework.
- The first midterm exam is in class on October 2. Here is a sample midterm.
- Homework 3, posted October 9, due October 18. Instructions for submission will be posted soon.
- Homework 2 graded and returned on Tuesday OCt 16.
- Please submit Homework 3 using ICON into the designated folder. For this homework the deadline is 11:59 pm on thursday, October 18.
- Homework 4, posted October 22, due Thursday November 1 in class.
- Homework 5, posted November 6, due Thursday November 15 in class.
- Homework 6, posted November 26, due December 6. Submit using ICON into the designated folder by 11:59 pm on December 6.
- Three test files for Homework 6: input1.txt, input2.txt, input3.txt.
- The final exam will be held at 12.00 pm, Wednesday, December 19 in our regular classroom. It will be based on the chapters on dynamic programming (Chapter 6) and NP and Computational Intractability (Chapter 8).
- A short Homework 7, posted December 6, due Thursday December 13 in class. Deadline extended. Now due Sunday Dec 16 at 2.30 pm when we meet.
- If you want the solutions to Homework 7, I will leave copies outside my door at 4.00 pm on Dec 16.