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