CPS 130: Introduction to the Design and Analysis of
Algorithms
|
|
Lectures -
Homework -
Handouts -
Teaching Assistants -
Resources |
Forum
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 theoretical and also practical 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.
Meetings:
| Lectures: |
|
Tuesdays and Thursdays, 1:15-2:30
LSRC Building, D106
|
Instructor:
Teaching Assistants
The TA for this course is:
Erik Halvorson.
For details on office hours and such, see the TA page.
Recitations:
Course material:
-
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.
See resources page for additional information.
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, rather than after
the due time. Homework assignments will be archived in the
homework directory.
The postscript version and pdf version will be available for
each homework.
Details about proper style [ps] for writing up homework solutions and
some guidelines for grading are available. More detailed notes on
how to write up technical material
[ps.gz]
in the Computer Science field (much of which is beyond the scope of this course)
are available.
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:
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:
- Homework assignments (20%)
- Closed-book midterm exam 1 (15%)
- Closed-book midterm exam 2 (15%)
- Closed-book midterm exam 3 (15%)
- Closed-book final exam (35%)
- Optional Class Project (only if approved by instructor)
There will be no make-up exams for missed exams. Missing one of the
three midterm exams due to an illness requires filing the web-based Short-Term
Illness Notification Form at
http://www.aas.duke.edu/trinity/t-reqs/illness,
and will result in the remaining midterm exams grades being re-weighted (to 20%
each). By University Policy, missing the Final exam results in a grade X.
Discussion Forum:
CPS130 Forum is
available for questions, announcements, and general discussion.
Anonymous course feedback:
Anonymous comments
Last Modified: Sunday, 28-Aug-2005 16:17:11 EDT