Homework
Homework  Post Date  Due Date  Solution 
Homework 0  Example only; no need for submission  Solution 0  
Homework 1  9/5/2017  9/13/2017  Solution 1 
Homework 2  9/13/2017  9/20/2017  
Homework 3  9/20/2017  9/27/2017 
Instructor
Rong
Ge
D226 LSRC
Email: rongge@cs.duke.edu
Office Hour: Tuesdays and Fridays 4:30  5:30 PM at
LSRC D226
Teaching
Assistant
Alex Steiger
Email: asteiger@cs.duke.edu
Office Hour: Mondays 3:00  5:00 PM, LSRC D301.
Keerti Anand
Email: kanand@cs.duke.edu
Office Hour: Wednesdays 3:00  5:00 PM, North 311.
Undergraduate Teaching Assistants
All undergraduate TA office hours will be at Physics 259.Recitations: Fridays 3:05  4:20 PM, Gross Hall 107
Text Book:
Lecture notes will be uploaded on the course website after every lecture. In addition, the following books cover most of the syllabus:Prerequisites:
There are two hard prerequisites (equivalent courses are also acceptable):
Evaluation:
The grades will be determined by homework, two midterm exams and final exam. All exams are inclass closedbook exams.Homework:
Please submit through sakai.
Homework should be typed
and submit as a PDF file. Latex is highly preferred.
Please make sure to read the guideline
on collaboration. Every incidence of cheating will be reported.
Questions about homework problems should be posted to Piazza
(instead of emailing the TAs or the instructor).
Synopsis:
Date  Contents  Notes  References 
8/29  Intro: Algorithms, Asymptotic Notations  Slides
Board
Notes 

Basic Algorithm Design Techniques  
8/31  Divide and Conquer  Slides Board 
DPV
2, KT 5, CLRS 4 
9/5  Slides
Board Notes 

9/7  Dynamic
Programming 
Slides Board Notes 
DPV
6, KT 6, CLRS: 15 
9/12  Slides Board Notes 

9/14  Greedy Algorithm  Slides Board Notes 
DPV 5, KT 4, CLRS: 16 
9/19  Slides Board 

Randomized Algorithms  
9/21 
Basic Probabilities, Quicksort revisited, fast selection  Slides  DPV:
virtural chapger KT: 13 CLRS: 5, 11 
9/26  Birthday Paradox, Rejection Sampling, MonteCarlo estimation  
9/28  Hashing  
10/3  Review 

10/5  MidTerm
Exam 1 (in class) All materials in previous lectures. 

10/10  Fall Break  
Graph Algorithms  
10/12  Graph representations and traversal  DPV 3, KT 3, CLRS 22  
10/17  
10/19  Shortest Path Algorithms 
DPV: 4.6, 6.6 KT: 6.8 CLRS: 24.1, 25 

10/24  Minimum Spanning Tree  DPV: 5 KT: 4 CLRS: 16, 23  
10/26  
10/31  Bipartite Graphs, Maximum Matching  DPV 7 KT: 7 CLRS: 26  
Amortized Analysis  
11/2  Dynamic Array  KT 4.6 CLRS 17, 20  
11/7  Disjoint Sets 

Linear Programming  
11/9  Linear Programming, Relaxations  CLRS 29  
11/14  Duality  
11/16  Linear Programming Algorithms  
11/21  MidTerm
Exam 2 (in class) All materials between the two midterms. 

11/23  Thanksgiving  
Intractability  
11/28  P vs NP, reductions 
DPV:
8 KT: 8 CLRS: 34 

11/30 
More reductions 

12/5  How to deal with NPhard
problems? 

12/7  Algorithms in machine
learning. 

12/14  Final Exam 9 am  noon 