Analysis of Algorithms

Department of Mathematics and Computer Science Hobart and William Smith Colleges Winter, 1998. Instructor: David J. Eck. Monday, Wednesday, Friday, 1:20--2:30 PM. Room Napier 202.

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 we will spend a significant amount of time doing mathematical
proofs. You'll also be asked to do some proofs on the homework.

The text for this course is *Computer Algorithms: Introduction to
Design and Analysis,* by Sara Baase. As for what parts of the text
we will cover, we will have to play it by ear.

There will be weekly homework assignments, which will be collected and graded. Many of the homework assignments will be taken from the text. Other assignments will ask you to write programs. You are free to write programs in Pascal, Java, C, or C++, as long as I have access to the compiler you are using. This means you can use Visual J++, Visual C++, CodeWarrior, THINK Pascal, or the VAX.

In addition to the general assignments, I plan to ask individuals to do class presentations of material from the text or from other sources. In most cases, I will expect you to write a program to go along with your presentation. Presentations will be counted as part of your homework grade.

There will be a midterm exam and a final exam. 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 mid-term exam will be given on Friday, February 6. On the same day, I will give out the take-home part of the mid-terms. The take home part will be due on the following Wednesday, February 11.

The scheduled final exam period for this class is Tuesday, March 17, at 7:00 PM. The in-class part of the final exam will take place at that time. I will give out the take-home part of the final on or before the last day of class. It will be due on Tuesday, March 17.

Your grade for the course will be computed as follows:

Mid-term Exam: 25% Final Exam: 30% Homework: 45%

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 e-mail address is ECK (or eck@hws.edu over the Internet). E-mail is good way to communicate with me, since I usually answer messages the day I receive them.