|Homework||Post Date||Due Date||Solution|
|Homework 0||Example only; no need for submission||Solution 0|
|Homework 1||9/5/2017||9/13/2017||Solution 1|
Office Hour: Tuesdays and Fridays 4:30 - 5:30 PM at LSRC D226
Office Hour: Mondays 3:00 - 5:00 PM, LSRC D301.
Office Hour: Wednesdays 3:00 - 5:00 PM, North 311.
Undergraduate Teaching AssistantsAll undergraduate TA office hours will be at Physics 259.
Recitations: Fridays 3:05 - 4:20 PM, Gross Hall 107
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.
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).
|8/29||Intro: Algorithms, Asymptotic Notations||Slides
|Basic Algorithm Design Techniques|
|8/31||Divide and Conquer||Slides Board
2, KT 5, CLRS 4
||Slides Board Notes
6, KT 6, CLRS: 15
|9/12||Slides Board Notes
|9/14||Greedy Algorithm||Slides Board Notes
||DPV 5, KT 4, CLRS: 16|
||Basic Probabilities, Quicksort revisited, fast selection||Slides||DPV:
CLRS: 5, 11
|9/26||Birthday Paradox, Rejection Sampling, Monte-Carlo estimation|
Exam 1 (in class)
All materials in previous lectures.
|10/12||Graph representations and traversal||DPV 3, KT 3, CLRS 22|
|10/19||Shortest Path Algorithms
||DPV: 4.6, 6.6 KT: 6.8
CLRS: 24.1, 25
|10/24||Minimum Spanning Tree||DPV: 5 KT: 4 CLRS: 16, 23|
|10/31||Bipartite Graphs, Maximum Matching||DPV 7 KT: 7 CLRS: 26|
|11/2||Dynamic Array||KT 4.6 CLRS 17, 20|
|11/9||Linear Programming, Relaxations||CLRS 29|
|11/16||Linear Programming Algorithms|
Exam 2 (in class)
All materials between the two mid-terms.
|11/28||P vs NP, reductions
8 KT: 8
|12/5||How to deal with NP-hard
|12/7||Algorithms in machine
|12/14||Final Exam 9 am - noon|