Homework
Homework  Post Date  Due Date  Solution 
Homework 0  Example only; no need for submission  Solution 0  
Homework 1  1/17/2019  1/24/2019 (by 11:59 pm)  Solution 1 
Homework 2  1/24/2019  1/31/2019 (by 11:59 pm)  Solution 2 
Homework 3  1/31/2019  2/11/2019 (by 5 pm)  Solution 3 
Homework 4  2/21/2019  2/28/2019 (by 11:59 pm)  Solution 4 
Homework 5  2/28/2019  3/7/2019 (by 11:59 pm)  Solution 5 
Homework 6  3/7/2019  3/21/2019 (by 11:59 pm)  Solution 6 
Homework 7  3/21/2019  3/28/2019  Solution 7 
Homework 8  4/10/2019  4/17/2019  Solution 8 
Homework 9  4/17/2019  4/24/2019  Solution 9 
Instructor
Rong
Ge
D226 LSRC
Email: rongge@cs.duke.edu
Office Hour (tentative): Tuesdays 4:30  5:30 PM, Fridays 3:00  4:00
PM at
LSRC D226
Teaching
Assistant
Haoming Li
Email: haoming.li@duke.edu
Shweta Patwa
Email: sjpatwa@cs.duke.edu
Chenwei Wu
Email: cwwu@cs.duke.edu
TA office hours
Sundays: 57PM in Bio Sci 130 with ChenweiRecitations: Check your individual recitation sessions.
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:
There will be 9 homeworks. In normal cases
homeworks are due
one week after they are posted. The worst grade out of 9 homeworks
will be dropped.
Homework will be submitted through GradeScope. 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  Homework  References 
1/10  Intro: Algorithms, Asymptotic Notations  Slides Board Scribe 

Basic Algorithm Design Techniques  
1/15  Divide and Conquer  Slides Board Scribe 
DPV
2, KT 5, CLRS 4 

1/17  Slides Board Scribe 
Homework 1  
1/22  Dynamic
Programming 
Slides Board Scribe 
DPV
6, KT 6, CLRS: 15 

1/24  Slides Board Scribe 
Homework 2  
1/29  Slides Board Scribe  
1/31  Greedy Algorithm  Slides Board Scribe 
Homework 3  DPV 5, KT 4, CLRS: 16 
2/5  Slides Board Scribe 

2/7  Slides Board Scribe  
2/12  Review  Slides Board  
2/14  MidTerm
Exam 1 (in class) All previous materials. 
Practice Exam (Ignore Problem 4 as it is for randomized algorithms)  
Graph Algorithms  
2/19  Graph representations and traversal  Slides Board Scribe  DPV 3, KT 3, CLRS 22  
2/21  Slides Board Board2 Scribe  Homework 4  
2/26  Shortest Path Algorithms 
Slides Board Scribe  DPV: 4.6, 6.6 KT: 6.8 CLRS: 24.1, 25 

2/28  Minimum Spanning Tree  Slides Board Scribe  Homework 5  DPV: 5 KT: 4 CLRS: 16, 23 
3/5  Slides Board Scribe  
3/7  Bipartite Graphs, Maximum Matching  Slides Board Scribe  Homework 6  DPV 7 KT: 7 CLRS: 26 
Fall Break  
Linear Programming  
3/19  Linear Programming, Relaxations  Slides Board Scribe  CLRS 29  
3/21  Duality  Slides Board Scribe  Homework 7  
3/26  Linear Programming Algorithms  Slides Board Scribe  
3/28  Review  Slides Board  
4/2  MidTerm
Exam 2 (in class) Graph algorithms and Linear Programming.  Practice Exam  
Topics: Randomized Algorithms and Amortized Analysis  
4/4 
Basic Probabilities, Quicksort revisited, fast selection  Slides Board Scribe 
DPV:
virtural chapger KT: 13 CLRS: 5, 11 

4/9  Hashing  Slides Board Scribe 

4/11  Amortized Analysis  Slides Board Scribe  Homework 8  KT 4.6 CLRS 17, 20 
Intractability  
4/16  P vs NP, reductions 
Slides Board Scribe  DPV:
8 KT: 8 CLRS: 34 

4/18 
More reductions 
Slides Board Scribe  Homework 9  
4/23  Even more reductions 
Slides Board Scribe  
5/3  Final Exam 2:00  5:00 PM Everything covered in class except for bipartite matching and amortized analysis 
Final Review Slides Board Practice Exam Old Exam (harder) 