Department of Mathematics and Computer Science Hobart and William Smith Colleges Spring, 1999. Instructor: David J. Eck. Monday, Wednesday, Friday, 12:00--1:10 PM. Room Napier 102.
This is a course in the analysis of algorithms. This means that the primary focus of the course is not supposed to be on details of particular algorithms. Instead, the focus is on such things as: the mathematical analysis of the time and memory requirements of algorithms, the verification of the correctness of an algorithm, and various techniques for the development of algorithms. In fact, our main activity in the course will be to look at particular algorithms, but we will always spend some time analyzing their run time efficiency. This is a rather mathematical course, and as part of the course we will sometimes be doing mathematical proofs. You'll also be asked to do some proofs on the homework.
The text for this course is An Introduction to Algorithms, by Thomas Cormen, Charles Leiserson, and Ronald Rivest. Among the thirty-seven chapters in the text are many that cover material that you should already be familiar with from previous courses. In many cases, however, it is covered at a higher level, so we will cover some of those sections -- partly for review and partly to get a better perspective on the material. Other chapters will be entirely new to you. As for exactly what we cover, we'll play it by ear to some extent. Some of the advanced topics that I definitely want to include are: dynamic programming, amortized analysis, algorithms for parallel computers, the FFT (fast Fourier transform), cryptography algorithms, and NP-completeness.
Your first assignment for the course is to read Chapter 1 of the text, pages 1 to 18.
In most weeks, there will be a homework assignment, which will be collected and graded. Some of the assignments will be problems from the text. Other assignments will ask you to write programs. You are free to write programs in any programming language you like, as long as I have access to the compiler or interpreter that you are using. This means you can use any of the compilers on math.hws.edu, Visual J++, Visual C++, or CodeWarrior.
In addition to the homework, there will be a final project based on material taken from the text or elsewhere. The project will involve a paper, a class presentation, and probably a program. Class presentations will take place during the last week of classes and should take up between one-third and one-half of a class period. The paper and program are due no later than the scheduled final exam for this course, Sunday June 6 at 1:30 PM.
There will be two in-class tests. Each of these will have two parts, an in-class part and a take-home part. The main difference between take-home tests and homework assignments is that you are not allowed to have any discussion about take-home tests with other people.
The in-class part of the first test will be given on Wednesday, April 28. On the same day, I will give out the take-home part of the test. The take home part will be due on the following Monday, May 3.
The second in-class test will be on Friday, May 28. At the same time, I will give out the take-home part of the test. The take home part is due no later than the scheduled final exam time for the class, Sunday June 6 at 1:30 PM.
Your grade for the course will be computed as follows:
First Test: 30%
Second Test: 30%
Homework: 20%
Project: 20%
My office is room 301 in Lansing Hall. My office phone extension is 3398. I am on campus most days, and you are welcome to come in anytime you can find me there. I will announce regular office hours (when I promise to try my best to definitely be in my office) as soon as I schedule them.
My email address is eck@hws.edu. Email is good way to communicate with me, since I usually answer messages the day I receive them.