CPS 230: The Design and Analysis ofAlgorithms

Fall 2004


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

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

Lectures:

Tuesdays and Thursdays  2:50-4:05 pm in D243

Instructor:

John Reif

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

TA:

Sudheer Sahu

Office: D206 LSRC Building
Phone:  (919) 660-6512
E-mail: sudheer@cs.duke.edu

Office Hours:

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

·         Divide-and-conquer

·         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 Tuesday 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.

Grading:

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#1 F03

·         Midterm#2 F98 Midterm#2 F99 Midterm#2 F00 Midterm#2 F01 Midterm#2 F02

·        
Final98 Final99 Final00 Final01 Final03

·         Qual98 Qual99 Qual00 Qual01


Newsgroup:

·         duke.cs.cps230

Anonymous Course Feedback:

·         Anonymous comments


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