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  Solution 2 
Homework 3  9/20/2017  9/27/2017  Solution 3 
Homework 4  9/27/2017  10/4/2017  Solution 4 
Homework 5  10/18/2017  10/25/2017  Solution 5 
Homework 6  10/25/2017  11/1/2017  Solution 6 
Homework 7  11/1/2017  11/8/2017  Solution 7 
Homework 8  11/9/2017  11/15/2017  See sakai for solutions after submission. 
Homework 9  11/15/2017  11/29/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 Notes 
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 Notes 

Randomized Algorithms  
9/21 
Basic Probabilities, Quicksort revisited, fast selection  Slides Board Notes  DPV:
virtural chapger KT: 13 CLRS: 5, 11 
9/26  Rejection Sampling, MonteCarlo estimation  Slides Board Notes  
9/28  Hashing  Slides Board Notes  
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  Slides Board Notes  DPV 3, KT 3, CLRS 22 
10/17  Slides Board Notes  
10/19  Shortest Path Algorithms 
Slides Board Notes  DPV: 4.6, 6.6 KT: 6.8 CLRS: 24.1, 25 
10/24  Minimum Spanning Tree  Slides Board Notes  DPV: 5 KT: 4 CLRS: 16, 23 
10/26  Slides Board Notes  
10/31  Bipartite Graphs, Maximum Matching  Slides Board Notes 
DPV 7 KT: 7 CLRS: 26 
Amortized Analysis  
11/2  Dynamic Array  Slides Board Notes 
KT 4.6 CLRS 17, 20 
11/7  Disjoint Sets 
Slides Board Notes 

Linear Programming  
11/9  Linear Programming, Relaxations  Slides Board 
CLRS 29 
11/14  Duality  Slides 

11/16  Linear Programming Algorithms  Slides Board 

11/21  MidTerm
Exam 2 (in class) Graph Algorithms + Amortized Analysis (Sample Exam) 

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 