CPS 230: The Design and Analysis ofAlgorithms

Fall 2002

Project Annoucement: Project is due on Dec. 9th.


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 lower bounds and computational models.

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 John Reif. 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.)


Mondays and Wednesdays (and sometimes Fridays) 2:20-3:35 in D106
Recitation labs generally on unscheduled Fridays (or on unscheduled Mondays or Wednesdays) at 2:20-3:35.


John Reif

Office: D223 LSRC Building
Phone: (919) 660-6568
E-mail: reif@cs.duke.edu


Tingting Jiang

Office: D125 LSRC Building
Phone:  (919) 660-6576
E-mail: ruxu@cs.duke.edu

Office Hours:

         Wednesday: 3:35pm - 4:45pm (John Reif)

         Thursday:  2:30pm-3:30pm (Tingting Jiang)

         Friday: 1:00pm-2:00pm (Tingting Jiang)

         by appointment (call or email).

Course material:

The course will be based on

         Cormen, Leiserson, Rivest, and Stein.Introduction to Algorithms, McGraw Hill, second edition, 2001.   Be sure to get the second edition!

         Various lecture notes and research papers (downloads).

Other good reference books:

         A. Aho, J. Hopcroft, and J. Ullman, Design and Analysis of Algorithms, Addison Wesley 1974.

         G. Brassard and P. Bratley, Algorithmic - Theory and Practice, Prentice Hall, 1988.

         D. Kozen, The Design and Analysis of Algorithms, Springer Verlag, 1991.

         R. Tarjan, Data Structures and Network Algorithms, SIAM Publications, 1983.

         C. H. Papadimitriou, Computational Complexity, Addison Wesley, 1994.

Course Synopsis:

         Mathematical foundations: Growth of functions, summations, recurrences, average-case and randomized analysis


         Sorting and selection

         Computational models and lower bounds

         Searching: Search trees, red-black trees, augmented search trees, van Emde Boas trees

         Amortized analysis: Dynamic tables, splay trees

         External memory algorithms: External sorting, B-trees

         Priority queues: Heaps and heapsort, binomial heaps, Fibonacci heaps

         Greedy algorithms: Huffman codes

         Dynamic programming

         Graph algorithms: Breadth-first search, depth-first search, minimal spanning trees, shortest paths, network flow

         Union-Find structures

         Matrix Algorithms

         Fast Fourier Transform

         Approximation algorithms

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.


Resources:  Computer Science Student Resources

Theoretical Computer Science Cheat Sheet: ps pdf  Ten pages of commonly used formulas and other useful information for computer scientists. By Professor Steven Seiden of Louisiana State U.

Mary Vernon's Useful Formulas Page ps pdf

How to Solve and Write Up Homework Problems: ps pdf   Helpful advice from Prof. Alan Sherman of the U. of Maryland, Baltimore County.

Efficient Reading of Papers in Science and Technology: ps pdf  This short brochure from an unknown author is well worth studying.

Free Online Dictionary of Computing: An online glossary, with cross-referencing.

Dictionary of Algorithms, Data Structures, and Problems: Includes definitions, problem analysis, code samples, and in some cases animations.

Homework Assignments:

Homeworks are due roughly every week and must be turned in before class on Wednesday of the week they're due. No credit is given for late solutions. For exceptional circumstances, see John Reif 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 on 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 can  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 John Reif.


Student grades for the class will be based on

         Homework assignments (approx. 30%).

         Closed-book midterm exam(s) and final exam (approx. 55%).

         Class Project (approx. 15%).

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 Midterm#2 F01

         Final98 Final99 Final00 Final01

         Qual98 Qual99 Qual00 Qual01

Best Solutions for Homework:

 Homework 1 (By  Ajdan)

 Homework 2 (By  Paul)

 Homework 3 (By  Vijeta)

 Homework 4 (By Sita)

Homework 5 (By  Thomas)

Homework 6 ( By Haoying )

Homework 7 (By Leelavati)

Homework 8    (By Ajdan)

Homework 9    (By Sudheer)

Homework 10    (By Badrish)

Homework 11    (By Sudheer)



Anonymous Course Feedback:

         Anonymous comments

John Reif / Duke University / reif@cs.duke.edu