The course meets 10.55--12.10 pm Tuesday and Thursday at 214 MLH (MacLean 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:
In addition, if time permits, we will study a (possibly empty) subset of the material in Chapters 10, 11, and 12.
This is just the preliminary plan and it will certainly undergo some modifications. We will also not stick to the order suggested above.
C- or higher in 22C:021 (CS:2310), and 22M:025 (MATH:1850) or 22M:031 (MATH:1550). The main prerequisite is 22C:21 (Data Structures), see for instance this previous offering. In particular we will assume that the students have (to quote our textbook) "written programs that implement basic algorithms, manipulate discrete structures such as trees and graphs, and apply basic data structures such as arrays, lists, queues, and stacks". This experience will allow us to discuss algorithms at the level of pseudo-code while clearly understanding that the pseudo-code is quite readily and reasonably translated toan actual program in some language (like Java).
The grading will be based on seven homeworks (6 points each), quizzes (a total of 10 points), a midterm (20 points) and a final (28 points). Up to two of the seven homeworks will require programming. I will assume Java as the default choice for the programming language in these two homeworks. (But do contact me if you are not sufficiently familiar with Java.) There will be a short quiz every thursday (except on the midterm day) thats worth one point. The overall contribution of the quizzes to the grade will be the minimum of 10 and the total score on the quizzes.
There will be no make-up quizzes. Make-up exams and late homework submissions will not be entertained either, except in very convincing cases of emergency. The graded quiz will be returned the next class. We will also aim to return the graded homeworks and midterm within one week after they are turned in.
I expect to follow, to the extent possible, the grade distribution recommended by the College of Liberal Arts and Sciences for an advanced course. Naturally, the actual performance may force a significant deviation from this distribution. I will use plus/minus grades.
No collaboration is allowed on the exams and quizzes. For homework problems, collaboration is alright. We even encourage it, assuming each of you has first spent some time (about 45 minutes) thinking about the problem yourself. However, no written transcript (electronic or otherwise) of the collaborative discussion should be taken from the discussion by any participant. It will be assumed that each of you is capable of orally explaining the solution that you turn in, so do not turn in something you don't understand.
The midterm will be during class hours on Thursday, March 10. The final exam will be on Monday, May 9, from 12.00--2.00 pm, as scheduled by the registrar's office. Both exams will happen in our classroom.
Chao Yang
Office hours: 2.30-4.00, Tue and Thu, at 101C MLH
Email:firstname-lastname@uiowa.edu
Here is a log of the topics we cover each class along with some useful pointers.
You may also find these lecture notes from an earlier offering useful for some (but not all) topics.