Theory of Computer Algorithms, 4005-800-70

Course Description

This course provides an introduction to the design and analysis of algorithms. It covers a large number of classical algorithms and their complexity and will equip students with the intellectual tools to design, analyze, implement, and evaluate their own algorithms

Course Web Page


Edith Hemaspaandra
bldg. 70, room 3625
Email: eh at

Office hours:

Asking questions via email seems to work well for many people.


Monday/Wednesday, 6:00-7:50pm, 70-1620.

Required Book

T. Cormen, C. Leiserson and R. Rivest, Introduction to Algorithms second edition, 2001, MIT press.

Other Materials

I will distribute copies of the slides that I use at the start of class and/or I will post them. Some of the slides were prepared by Dr. Gordon Royle, Department of Computer Science, University of Western Australia and by Dr Misunori Ogihara, Department of Computer Science, University of Rochester. Information about homework assignments, exams, etc. will be linked from the course web page.


CS4 and Discrete Math.

The Work

Homework Assignments

There are five or six graded homework assignments. Each homework assignment will be collected and graded. Homework assignments are due on Wednesday, and are usually posted at least 6 days before they are due. The actual assignments will be available on the reading and homework assignments page.

Unless it is specifically stated otherwise, you may work on and submit your homework in groups of 1 or 2. If you choose to work as a group of 2, both of you should contribute significantly to the solution for every question. You should submit only one copy of the homework with both your names on it. You are not allowed to discuss the homework with anyone except your homework partner and me. You are also not allowed to look up the answers to your homework. You should submit only work that is completely your own and you should be able to explain all of your homework to me.

Homework submissions are due at the start of class (6:00pm). I will not accept late assignments (not even 5 minutes late) for any reason. I will drop the lowest homework grade. However, a zero for cheating will not be dropped.

I will stop answering homework questions at 11:30am the day it is due.

You are not permitted to speak with the grader about anything related to this course. Any (attempted) discussions with the grader regarding current or future homework assignments will be considered cheating.


Exam 1 is scheduled for Wednesday, January 25, 6:00-7:50pm, in 70-1620. The exam is closed book, but you may bring one sheet of letter-sized paper with your own hand-written notes. In addition, you will get a copy of all relevant hand-outs at the start of the exam.

Exam 2 is scheduled for Wednesday, February 22, 6:00-7:50pm, in 70-1620. The exam is closed book, but you may bring one sheet of letter-sized paper with your own hand-written notes. In addition, you will get a copy of all relevant hand-outs at the start of the exam.

The exams can not be made up except for real emergencies in which case proper documentation (like a doctor's note) will be required. If at all possible, you should contact me prior to the exam. Oversleeping, cars that don't start etc. do not constitute a valid excuse.

Programming Project.

There will be one programming project. You may work on and submit this project with another student if you like, but doing it on your own is fine too. Details (including rules on collaboration) will be given on the programming project page.


Numerical grades will be converted to letter grades according to the following scale:
> 88%: A; 77%-88%: B; 66%-77%: C; 55%-66%: D; < 55%: F.
However, your final grade will never be more than one letter grade higher than your average exam grade. In addition, if your average exam grade is below 55%, you fail the course.

Disputing Your Grade

If you feel that an error was made in grading your homework, exam, or project, you have one week from the moment the graded work was handed back to dispute your grade.

Academic Dishonesty

The DCS Policy on Academic Dishonesty will be enforced.
You should only submit work that is completely your own. Failure to do so counts as academic dishonesty and so does being the source of such work. Submitting work that is in large part not completely your own work is a flagrant violation of basic ethical behavior and will minimally be punished with failing the course.


Topics will include