CPS 230: The Design and Analysis of Algorithms

Fall 2001

Description:

This course is an introductory graduate course and advanced undergraduate course on the design and analysis of algorithms. We will cover algorithm design techniques such as divide-and-conquer, dynamic programming, and greedy algorithms for a variety of tasks such as sorting, searching, and graph problems. We will also cover linear programming (if time permits), lower bounds and models, and NP-completeness.

This course requires undergraduate background in algorithms and/or data structures and, above all, mathematical sophistication. If you feel that you may not have sufficient background, please talk with the instructor Jeff Vitter. A good option that has worked well for such students in the past is to take CPS 130 instead, also offered Fall semester.  (Master's students can count two 100-level courses toward their Master's degree with approval from the DGS.)

Lectures:

Mondays and Wednesdays 2:20-3:35 in D106
Possible recitation labs or office hours on Fridays at 2:20-3:35.

Instructor:

Jeff Vitter

Office: D214A LSRC Building
Phone: (919) 660-6503
E-mail: jsv@cs.duke.edu

TA:

Ankur Gupta

Office: D122 LSRC Building
Phone:  (919) 660-6507
E-mail: agupta@cs.duke.edu

Office Hours:

Course material:

The course will be based on Other good reference books:

Course Synopsis:

Summary of Topics Covered and Lecture Notes:

Consult the schedule of lecture topics for a list of topics and a copy of lecture notes for the lectures to date.  Other handouts can be found in the handouts directory, and homeworks and old midterm and final exams can be found in the homework directory.

Grading:

Student grades for the class will be based on

You might find some of the past tests helpful for review:

  • Midterm#1 F98
  • Midterm#1 F99
  • Midterm#1 F00
  • Midterm#2 F98
  • Midterm#2 F99
  • Midterm#2 F00
  • Final98
  • Final99
  • Final00
  • Qual98
  • Qual99
  • Qual00

    • Homework Assignments:

    Homeworks are due roughly every other week and must be turned in before class on Monday of the week they're due. No credit is given for late solutions. For exceptional circumstances, see Jeff in advance.

    Homework assignments will be archived in the homework directory.  The postscript version, pdf version, and source LaTeX code will be available for each homework problem. LaTeX should be used for typesetting homework problems.

    Details about proper style for writing up homework solutions and some guidelines for grading appear in ps or pdf format.  More detailed notes on how to write (much of which is beyond the scope of this course) are available in gzipped ps or pdf.  Plus you can make use of the LaTeX source file, the LaTeX macros, a LaTeX template file, a LaTeX guide, and hypertext LaTeX help.

    Honor Code wrt Homework Problems:

    For homework problems, discussion among students is permitted, but students MUST write up solutions independently on their own.  No materials or sources from prior years' classes or from the Internet can be consulted.  Breaking the rules will result in expulsion. Each student is required to make a copy of this page, sign it indicating that the contents are understood, and turn it in to Jeff.

    Newsgroup:

    Anonymous Course Feedback:

    Last modified: Mon Nov 26 12:15:41 EST 2001

    Jeff Vitter / Duke University / jsv @ cs.duke.edu