The course meets 1.05--2.20 pm Tuesday and Thursday at 112 MH (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:
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 progarmming (probably in 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.
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, October 14. The final exam will be on Thursday, Dec 16, from 2.15--4.15 pm. Both exams will happen in our classroom.
Hang Dou, B20J, MacLean Hall
Office hours: 2--3.30 pm Mon and Wed
Email:firstname-lastname@uiowa.edu
You may also find these lecture notes from an earlier offering useful for some (but not all) topics.