CPS 130: Introduction to the Design and Analysis of Algorithms |
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.
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.
|
Times: Tues & Thurs 2:50 PM – 4:05 PM Room: Biosci 111 |
Professor John Reif |
||
Office: |
|
D223 LSRC Building |
Phone: |
|
(919) 660-6568 |
Email: |
|
|
Web page: |
|
|
Office hours: |
|
Tues, Thurs: 4:05 pm - 5:00 pm |
CPS130-01R Recitation by
TA |
|
Times:
Friday 1:15PM – 2:30PM Room:
Soc
Psy 126 |
Office: |
|
D330 LSRC Building |
Phone: |
|
(919) 660-6589 |
Email: |
|
|
Web page: |
|
http://www.cs.duke.edu/people/graduate/?csid=0001648 |
Office hours: |
|
Tues, Thurs: 4:05 pm - 5:00 pm |
· Solutions to Selected exercises and
problems in CLRS
Optional
auxiliary reading (other good reference books):
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.
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, pdf version, and source LaTeX code will be available for
each homework problem.
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.
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.