|Homework||Post Date||Due Date||Solution|
|Homework 0||Example only; no need for submission||Solution 0|
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
2, KT 5, CLRS 4
6, KT 6, CLRS: 15
|1/31||Greedy Algorithm||Homework 3||DPV 5, KT 4, CLRS: 16|
Exam 1 (in class)
All previous materials.
|2/19||Graph representations and traversal||DPV 3, KT 3, CLRS 22|
|2/26||Shortest Path Algorithms
||DPV: 4.6, 6.6 KT: 6.8
CLRS: 24.1, 25
|2/28||Minimum Spanning Tree||Homework 5||DPV: 5 KT: 4 CLRS: 16, 23|
|3/7||Bipartite Graphs, Maximum Matching||Homework 6||DPV 7 KT: 7 CLRS: 26|
|3/19||Linear Programming, Relaxations||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