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

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

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

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

**Office Hours: **

**Wednesday: 1:00 pm - 3:00 pm (John Reif)****Tuesday: 1:30 pm - 2:30 pm (Sudheer Sahu)**

**Thursday: 1:30 pm - 2:30 pm (Sudheer Sahu)**

**by appointment (call or email).**

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

·
**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**

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

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

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

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

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

·
**Final98
Final99
Final00
Final01
Final03
**