|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)|
|Homework 6||3/7/2019||3/21/2019 (by 11:59 pm)|
Office Hour (tentative): Tuesdays 4:30 - 5:30 PM, Fridays 3:00 - 4:00 PM at LSRC D226
TA office hoursSundays: 5-7PM in Bio Sci 130 with Chenwei
Recitations: 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:
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 in-class closed-book exams.
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).
|1/10||Intro: Algorithms, Asymptotic Notations||Slides Board Scribe
|Basic Algorithm Design Techniques|
|1/15||Divide and Conquer||Slides Board Scribe
2, KT 5, CLRS 4
|1/17||Slides Board Scribe
||Slides Board Scribe
6, KT 6, CLRS: 15
|1/24||Slides Board Scribe
|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|
Exam 1 (in class)
All previous materials.
|Practice Exam (Ignore Problem 4 as it is for randomized 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||Homework 6||DPV 7 KT: 7 CLRS: 26|
|3/19||Linear Programming, Relaxations||Slides Board||CLRS 29|
|3/26||Linear Programming Algorithms|
Exam 2 (in class)|
Graph algorithms and Linear Programming.
|Topics: Randomized Algorithms and Amortized Analysis|
||Basic Probabilities, Quicksort revisited, fast selection||DPV:
CLRS: 5, 11
|4/11||Amortized Analysis||Homework 8||KT 4.6 CLRS 17, 20|
|4/16||P vs NP, reductions
8 KT: 8
|4/23||Even more reductions
|5/3||Final Exam 2:00 - 5:00 PM
Everything covered in class except for bipartite matching and amortized analysis