
Lectures  Teaching Assistant  Resources
Description:
This
course is an introductory graduate course on the design and analysis of
algorithms. The course builds on an undergraduatelevel study of the analysis
and implementation of data structures and algorithms (COMPSCI 201). 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
divideandconquer, 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:
An
undergraduatelevel course on the analysis and implementation of data
structures and algorithms (COMPSCI 201 or equivalent) and also four semesters
of college mathematics. This course requires 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:

Times: Tues & Thurs 1:25 PM – 2:40
PM Room: North 311 
Instructor:
Professor John Reif 

Office: 

D223 LSRC
Building 
Phone: 

9196606568 
Email: 


Web page: 


Office hours: 

Tues, Thurs: 2:40
 3:40 PM 
TA: Brandon Fain
Office: 


Phone: 


Email: btfain at cs.duke.edu 


Office hours: Tuesday
& Wednesday 12:001:00 PM 

Course material:
á Solutions to Selected exercises and problems in
CLRS
Optional
auxiliary reading (other good reference books):
Course synopsis:
Summary of topics covered
and lecture notes:
Consult
the schedule of Lectures 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 second 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.
Details about proper style [ps] for writing up homework solutions and some
guidelines for grading are available.
It is recommended but not
required that LaTeX be used for typesetting homework problems.
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. During every exam: all
calculators, computers, cell phones, wireless or bluetoothconnected devices,
and all other electronic devices must be identified and handed over to the
person proctoring the exam. Breaking the rules can result in expulsion. Each
student is required to make a copy of this paragraph, sign it indicating that
the contents are understood, and turn it in to John Reif.
Grading:
There
will be no makeup exams for missed exams. Missing one of the three
midterm exams due to an illness requires filing the webbased ShortTerm
Illness Notification Form at http://www.aas.duke.edu/trinity/treqs/illness, and will result in the remaining midterm exams grades
being reweighted appropriately. By University Policy, missing the Final exam
results in a grade X.
Anonymous course feedback: Anonymous
comments