Homework
Homework  Post Date  Due Date 
Homework 1  9/12  9/27 
Homework 2  9/26  10/14 
Homework 3  10/10  11/2 
Homework 4  11/1  11/15 
Homework 5  11/14  12/2 
Homework 6  12/1  12/9 
Instructor
Rong
Ge
D226 LSRC
Email: rongge@cs.duke.edu
Office Hour: Tuesdays 3:00  5:00 PM at LSRC D226
Teaching
Assistant
Yuan Deng
Email: yuan.deng@duke.edu
Office Hour: Thursdays 5:00  7:00 PM at LSRC D309
Undergraduate Teaching Assistants
Arun Ganesh
Email: arun.ganesh@duke.edu
Office Hour: Wednesdays 12:00  2:00 PM at LSRC D309
Bodong (Wilson) Zhang
Email: bodong.zhang@duke.edu
Office Hour: Mondays 10:0011:00 AM at LSRC D301
Aditya Mukund
Email: am439@duke.edu
Office Hour: Mondays 5:00  6:00 PM at LSRC D301
Weiyao (Will) Wang
Email: ww109@duke.edu
Office Hour: Fridays 5:00  6:00 PM at LSRC D301
Fred Zhang
Email: h.z@duke.edu
Office Hour: Mondays 7:00  8:00 PM at LSRC D301
Recitations: Fridays 3:05  4:20 PM, Physics 128
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, midterm exam and final exam. Both 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  Notes 

Basic Algorithm Design Techniques  
8/31  Divide and Conquer  Notes 
DPV
2, KT 5, CLRS 4 
9/5  Notes  
9/7  Dynamic
Programming 
Notes  DPV
6, KT 6, CLRS: 15 
9/12  Notes  
9/14  Greedy Algorithm  Notes 
DPV 5, KT 4, CLRS: 16 
9/19  Notes 

Graph Algorithms  
9/21 
Graph representations and traversal  Notes  DPV 3, KT 3, CLRS 22 
9/26  Notes  
9/28  Shortest Paths algorithms  Notes  DPV: 4.6, 6.6 KT: 6.8 CLRS: 24.1, 25 
10/3  Minimum
Spanning Tree 
Notes 
DPV: 5 KT: 4 CLRS: 16, 23 
10/5  Bipartite Graphs, Maximum Matching  Notes  DPV 7 KT: 7 CLRS: 26 
10/10  Fall break, No class  
10/12  Review: How to find the right technique  
10/17  MidTerm
Exam (in class) All materials in previous lectures. 

Amortized Analysis  
10/19  Dynamic Array 
Notes  KT 4.6 CLRS 17, 20 
10/24  Disjoint set  Notes  
Randomized Algorithms  
10/26  Basic Probabilities, Quicksort revisited, fast selection  Notes  DPV: virtural chapger KT: 13 CLRS: 5, 11 
10/31  Birthday Paradox, Coupon Collector, Balls in Bins  Notes  
11/2  Hashing  Notes  
Linear Programming  
11/7  Linear Programming, Relaxations  Notes  CLRS 29 
11/9  Duality  Notes  
11/14  Linear Programming Algorithms  Notes  
Machine Learning Algorithms  
11/16  Basic Machine Learning, Principled Component Analysis  Slides Notes  
11/21  Gradient Descent and Least Squares  Notes  
11/23  Thanksgiving  
Intractability  
11/28  P vs NP, reductions 
Notes  DPV: 8 KT: 8 CLRS: 34 
11/30 
More reductions 
Notes 

12/5  How to deal with NPhard problems? 
Notes  
12/7  Review/Information about Exam 
Slides Notes  
12/17  Final Exam 2 pm  5pm 