Homework
Homework  Post Date  Due Date  Solution 
Homework 0  Example only; no need for submission  Solution 0  
Homework 1 
1/15/2020 
1/22/2020, by 11:59 pm 
Solution 1 
Homework 2 
1/29/2020 
2/5/2020, by 11:59 pm 
Solution 2 
Homework 3 
2/5/2020 
2/12/2020, by 11:59 pm 
Solution 3 
Homework 4 
2/26/2020 
3/4/2020, by 11:59 pm 
Solution 4 
Homework 5 
3/4/2020 
3/25/2020, by 11:59 pm 
Solution 5 
Homework 6 
4/1/2020 
4/8/2020, by 11:59 pm  Solution 6 
Homework 7 
4/8/2020 
4/15/2020, by 11:59 pm 
Solution 7 
Homework 8 
4/15/2020 
4/22/2020, by 11:59 pm  Solution 8 
Instructor
Rong
Ge
D226 LSRC
Email: rongge@cs.duke.edu
Office Hour: Tuesdays 1:00  2:00 PM, Fridays 11:00 AM  12:00 at
LSRC D226 (First office hour Friday 1/17)
After Spring break: I'm
going to keep the Tuesdays 1  2 PM office hour on zoom. Instead of the
Friday
office hour, I will offer two 30min sessions where I will be on piazza
trying to answer all questions posted (First two will be Thursday
33:30 pm and Friday 10:3011:00 am, 4/2 and 4/3). For the first two
office
hour Tuesday 3/24 and 3/31 I need to change the time to 12:30  1:30 PM.
Teaching
Assistants
TA office hours
Physics 259 6:30  8:30 PM Sundays and Tuesday 2/4Recitations: Check your individual recitation sessions.
After Spring break: See this post on piazza, you are
recommended to stay with your section if your TA is still teaching at
the same time and it's possible for you to attend. If you have any
difficulty, you can go to a different recitation session that is most
convenient for you. We will also record one of the session so you can
watch it offline even if you cannot attend.
For most recent recitation materials please check this folder on Sakai.
Notice: The first
recitation will be a review of materials already covered in 230 and is
optional. Only some of the sessions will be open, you should go to the
classroom based on your time.
1:25 pm and 4:40 pm in LSRC D106, 3:05 pm in Soc. Psych. 126
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.Updated Evaluation:
Note: According to school policy, the
course is defaulted to S/U grading. All of you should expect to get an
S as long as you continue to work on the homework/exams to your capacity, and I'd be
happy to discuss with anyone who has more difficulties. If you do want
a letter grade, you need to submit a form by April 22 (the form is required by Trinity so check your email for the exact date).
Homework:
There will be 8 homeworks. In normal cases
homeworks are due
one week after they are posted. The worst two grade out of 8 homeworks
will be dropped.
Homework will be submitted through GradeScope.
Homework should be typed
and submit as a PDF file. LateX is highly preferred.
If you are not familiar with LaTeX and want to learn, I learned how to
use it by reading this
(but there are also other resources you can find online).
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/8  Intro: Algorithms, Asymptotic Notations  Slides Notes Scribe 

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

1/15  Slides Notes Scribe 
Homework 1  
1/20 
Martin Luther King, Jr. Day holiday. No
classes are held. 

1/22  Dynamic
Programming 
Slides Notes Scribe 
DPV
6, KT 6, CLRS: 15 

1/27  Slides Notes Scribe 

1/29  Slides Notes Scribe 
Homework 2  
2/3 
Greedy Algorithm  Slides Notes Scribe 
DPV 5, KT 4, CLRS: 16  
2/5  Slides Notes Scribe 
Homework 3  
2/10  Slides Notes Scribe 

2/12  Review  Slides Notes 

2/17  MidTerm
Exam 1 (in class) All previous materials. 
Previous midterm 

Graph Algorithms  
2/19  Graph representations and traversal  Slides Notes Scribe 
DPV 3, KT 3, CLRS 22  
2/24  Slides Notes Scribe 

2/26  Shortest Path Algorithms 
Slides Notes Scribe 
Homework 4  DPV: 4.6, 6.6 KT: 6.8 CLRS: 24.1, 25 
3/2 
Minimum Spanning Tree  Slides Notes Scribe 
DPV: 5 KT: 4 CLRS: 16, 23  
3/4  Slides Notes Scribe 
Homework 5  
3/9,11,16,18 
Spring Break 

Linear Programming  
3/23  Linear Programming, Relaxations  Slides Notes Scribe 
CLRS 29  
3/25  Duality  Slides Notes Scribe 

3/30  Bipartite Matching, Max Flow 
Slides Notes Scribe 

4/1 
Linear Programming Algorithms  Slides Notes Scribe 
Homework 6  
Topics: Randomized Algorithms and Amortized Analysis  
4/6 
Basic Probabilities, Quicksort revisited, fast selection  Slides Notes Scribe 
DPV:
virtural chapter KT: 13 CLRS: 5, 11 

4/8  Hashing  Slides Notes Scribe 
Homework 7 

Intractability 

4/13  P vs NP, reductions  Slides Notes Scribe  DPV:
8 KT: 8 CLRS: 34  
4/15  More reductions  Slides Notes Scribe 
Homework 8  
4/20 
Even more reductions  Slides Notes Scribe 

4/22  Amortized Analysis  Slides Notes 
KT 4.6 CLRS 17, 20  
4/30  Final Exam Everything covered in class 
Previous Second Midterm Previous Final 