The course meets 9.30--10.20 am Monday, Wednesday, and Friday at 118 MacLean Hall.
Kasturi Varadarajan, 101D MacLean Hall, Phone: 335-0732, email:firstname-lastname@uiowa.edu. Office Hours: 11.00 am -- 12.00 noon, Mon, Tue, and Wed.
We will practise the precise statement of various computational problems, think about different strategies or algorithms to solve them, reason about their correctness, evaluate these alg orithms from the point of view of efficiency (usually running time), and develop a feel for the difficulty of problems and the applicability of various techniqu es we will learn. Unlike the data structures course, this exploration of algorithmic efficiency will be on the abstract side, and so we won't play with implementations of many of the algorithms and ideas we discuss (though there will be some of that).
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 st ructures 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 to an actual program in some language (like Java).
The grading will be based on several homeworks (35 percent), quizzes (5 percent), two in-class midterms (15 percent each), and the final (30 percent).
There will be a quiz every friday that will take no more than five minutes. I expect there to be twelve to fourteen quizzes overall. Each quiz will be worth 1 point. Your overall grade on the quiz will be the minimum of 5 and the expression (5 * total points on quizzes)/10. Notice that you can do 10 quizzes perfectly and get the maximum grade on the quizzes. So you will not be allowed to make up missed quizzes.
There will be seven to nine homeworks, and two of these will involve programming.
The policy on late homeworks is that you have a quota of three days for the entire semester that you may use for late submissions. So for example, there will be no penalty if you submit the fifth homework a day late, the seventh two days late, and the rest of the homeworks on time. Once you use up your quota of three days, any homework submitted late will not be accepted and you will get 0 points for that homework.
When you submit a homework X days late, your quota gets decreased by X irrevocably. You can only be late by an integer number of days -- if you submit 10 hours after the deadline, for example, your quote is depleted by one day.