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