Design and Analysis of Algorithms
CSC 491-701/710

Marcus Schaefer

Latest additions

String Algorithms (with applets) (thanks Massimo)

Computational Tractability: The View from Mars

Proofs of Euler's theorem

Homeworks and Examples

Assignments will be available through this webpage. Homeworks are due at the beginning of class. There are no late homeworks (since we do solutions in class). However, I will drop the lowest homework score.

Homework due
hw1 9/18
hw2 9/25
hw3 10/2
hw4 10/9
hw5 10/23
hw6 10/30
hw7 11/6
hw8 11/13
  Notes, Examples
Week 1 Advice on Problem Solving (postscript, pdf)
Week 2 Randomized Quicksort Analysis (postscript, pdf, latex)
Week 4 Optimal binary search trees (postscript, pdf)

Questions and Answers


Classes and office hours

The class meets M 5:45pm-9:00pm  (room Lewis 1009).

My office hours are MTu, 4:00pm-5:30pm.

During that time you can find me in the CS&T building, room 749.

If you want to set up an appointment at another time, or simply ask a question,

send email to


For general information (literature, course summary), see the class syllabus.

  • Mathematical Background
  • Divide and conquer algorithms
  • Dynamic programming
  • Greedy algorithms
  • NP-Completeness
  • Coping with NP-completeness

Grades and exams

Homework: 40%, Midterm: 30%, Final exam: 30%. Extra credit is counted separately.

General Policies

Academic Honesty


An incomplete grade is given only for an exceptional reason such as a death in the family, a serious illness, etc. Any such reason must be documented. Any incomplete request must be made at least two weeks before the final, and approved by the Dean of the School of Computer Science, Telecommunications and Information Systems. Any consequences resulting from a poor grade for the course will not be considered as valid reasons for such a request.

Marcus Schaefer
Last updated: August 11th, 2006.