CPS 130: Introduction to the Design and Analysis of Algorithms |
|
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:
|
|
|
Instructor:
|
Professor John Reif |
||
|
Office: |
|
D223 LSRC Building |
|
Phone: |
|
(919) 660-6568 |
|
Email: |
|
|
|
Web page: |
|
|
|
Office hours: |
|
2:00pm-3:00pm Tuesday, Thursday |
Teaching Assistants
The TA for this course is: Nikhil Gopalkrishnan
For details on office hours and such, see the TA page.
Recitations:
Th 3:05-3:55 in LSRC B102 and Wednesdays 11:30am-12:20pm in LSRC D301
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 . See resources
page for additional information.
Homework assignments:
Homeworks are due roughly every
week and must be turned in before class on the day 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%)
- Quiz I (7.5%)
- Quiz II (7.5%)
- Closed-book midterm exam 1 (10%)
- Closed-book midterm exam 2 (10%)
- Closed-book final exam (30%)
- Class interaction (includes attendance and in-class questions (15%)
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:
Last Modified: Thursday, 02-Aug-2007 08:01:02 EDT