CPS 130: Introduction to the Design and Analysis ofAlgorithms

Spring 2003


This course is an introductory undergraduate course on the design and analysis of algorithms. The course builds on the study of the analysis and implementation of data structures and algorithms from CPS100. The goal is to introduce a number of important algorithm design techniques as well as basic algorithms that are interesting both from a practical and theoretical point of view.We will cover basic algorithm design techniques such as divide-and-conquer, dynamic programming, and greedy techniques for optimization. We will cover techniques for proof of the correctness of algorithms and also asymptotic analysis of algorithm time bounds by the solution of recurrence equations. We will apply these design and analysis techniques to derived algorithms for a variety of tasks such as sorting, searching, and graph problems. Some specific algorithm topics include: deterministic and randomized sorting and searching algorithms, depth and breadth first search graph algorithms for finding paths and matchings, and algebraic algorithms for fast multiplication and linear system solving. 


CPS 100 or equivalent and four semesters of college mathematics.

This course requires undergraduate background in data structures (as covered in CPS100) as well as a certain amount of mathematical sophistication (e.g., as required to solve recurrence equations). A quiz on recurrence equations early in the course will provide you with some feedback on whether your mathematics training will suffice. If you feel that you may not have sufficient background, please talk with the instructor John Reif. 


Professor John Reif
Office: D223 LSRC Building 
Phone: (919) 660-6568
E-mail: reif@cs.duke.edu
Web Page: www.cs.duke.edu/~reif


Mondays and Wednesdays (and sometimes Fridays) 2:20-3:35 in LSRC Building B101. 


Wenbin Pan

Office: N003 North Building
Phone:  (919) 660-4003
E-mail: wbpan@cs.duke.edu

 Leelavati Narlikar

Office: N003 North Building
Phone:  (919) 660-4003
E-mail: lee@cs.duke.edu

Office Hours: 

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

Thursday:  2:30pm-3:30pm (TA)

Friday: 1:00pm-2:00pm (TA)

by appointment (call or email).


Wednesday(Recitation #8432): 1:10pm - 2:00pm (TA)LSRC A158

Friday(Recitation #8434):  10:30am-11:20am (TA)LSRC A158

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).
Optional Auxiliary Reading: Other good reference books: 
G. Brassard and P. Bratley, Algorithmic - Theory and Practice, Prentice Hall, 1988.
D. Kozen, The Design and Analysis of Algorithms, Springer Verlag, 1991.
A. Aho, J. Hopcroft, and J. Ullman, Design and Analysis of Algorithms, Addison Wesley 1974.
R. Tarjan, Data Structures and Network Algorithms, SIAM Publications, 1983.
C. H. Papadimitriou, Computational Complexity, Addison Wesley, 1994.

Course Synopsis:

Mathematical Analysis of Algorithms: Growth of functions, summations, recurrences, average-case and randomized analysis 
Sorting and selection: Divide-and-conquer and Randomized Techniques
Search Trees: Search trees 
Amortized analysis 
Priority queues 
Greedy algorithms 
Dynamic programming 
Graph algorithms 
Matrix and Algebraic Algorithms 

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: pspdf  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: pspdf   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. 

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 up technical material in the Computer Science field (much of which is beyond the scope of this course) are available in gzipped ps or pdf.

It is recommended but not required that LaTeX be used for typesetting homework problems. 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. 25%).
Two Closed-book  quizes (second optional, averaged total of 7.5%).
Closed-book midterm exam 1 (approx. 15%).
Closed-book midterm exam 2 (approx. 15%).
Closed-book final exam (approx. 37.5%).
Optional Class Project (only if approved by instructor).



Anonymous Course Feedback:

Anonymous comments

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