
Lectures  Teaching Assistants  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.
Lectures will focus on introducing major
algorithmic principles of design and analysis, along with mathematical analysis
of algorithmic problems. The weekly lab section will build on that material to
explore questions of implementations and applications to real world problems.
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 an instructor.
Meetings and Lectures: Online Only

Times: Tues & Thurs 12:00 PM –
1:15 PM Via Zoom 
Instructor:
Professor John Reif 

Office: 

D223 LSRC Building 
Phone: 

9196606568 
Email: 


Web page: 


Office hours: 

Weds, Fri: 9:00AM – 10:00 AM – via Zoom 
TA RECITATIONS via Zoom Times: Weds 12:00 PM – 1:15 PM
TA 1: Xin Song 


TA 2: Dan Fu 








PhD Student 


PhD Student 


Office: 

D124 LSRC 
Office: 

D124 LSRC 

Phone: 

9194665957 
Phone: 

9195646425 

Email: 

xin.song@duke.edu 
Email: 

daniel.fu@duke.edu 

Web page: 

Web page: 


Office hours: 

Mon & Wed 3:304:30 PM via phone or Zoom 
Office hours: 

Mon & Wed 4:305:30 PM via phone or Zoom 

Course material:
· Solutions to Selected exercises and problems in CLRS
Optional auxiliary reading (other good
reference books):
Course Topics:
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. See resources page for
additional information.
Homework assignments:
All assignments will be released to Students on the
course Sakai webpage, and all solutions should similarly be submitted on the
course Sakai webpage. No credit is given for late solutions. You should turn in
what you have on time for partial credit rather than receive a 0. For
exceptional circumstances, see the instructor in advance, rather than after the
due time. Our policy is that one (and only one) homework during the entire term
is allowed not to be handed in, at no loss of credit. Furthermore, if you hand
in all the homework, then we will drop the lowest graded homework.
Students will be asked to design algorithms for classic problems
and provide mathematical analysis of correctness and asymptotic efficiency.
Students will turn in a written set of solutions. It is recommended but not
required that LaTeX be used for typesetting homework problems. If handwritten solutions are illegible, they will not be graded. Details
about proper style for writing
up homework solutions and some guidelines for grading are available.
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.
Honor code: For
homework problems, discussion among students is permitted, but students must
write up solutions independently on their own. 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. For details about what is acceptable, see this honesty matrix.
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 will result in the
remaining midterms and final exam grades being reweighted appropriately. By
University Policy, missing the Final exam results in a grade X.
Anonymous course feedback: Anonymous comments