CPS 130: Introduction to the Design and Analysis ofAlgorithms
Spring 2003
Description:
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.
Prerequisites:
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.
Instructor:
Office:
D223 LSRC Building
Phone:
(919) 660-6568
Lectures:
Mondays and Wednesdays (and sometimes Fridays)
2:20-3:35 in LSRC Building B101.
TA:
Office: N003 North Building
Phone: (919) 660-4003
E-mail: wbpan@cs.duke.edu
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).
Recitations:
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:
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.
Grading:
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).
Newsgroup:
Anonymous Course Feedback:
John Reif / Duke University
/ reif@cs.duke.edu