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

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

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

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

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

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