Welcome to CS161!

Class Information

Teaching Staff (Course Assistants)

Communication

Grading: Homework and Exams

Homework Assignments Exams Policy on collaboration and outside sources: Grading Policy

Lecture Schedule (subject to change)

KT refers to Kleinberg and Tardos.
Lecture slides will be uploaded at least an hour before each lecture.
Note that the slides may be updated afterwards.
Final version of lecture slides will be uploaded soon after each lecture ends.

Lecture No. Date Topics and Reading
01 [PDF]
[ VIDEO ]
6/23/2015 Introduction / Big-Oh Notation / Intro to Greedy Algorithms
[Readings (KT): Ch. 1, 2.1-2.4, 4.1-4.2] [Suggested Exercises (KT): 1.5, 1.8, 2.3, 2.5, 4.5.]
02 [PDF]
[ VIDEO ]
6/25/2015 More Greedy Algorithms: Dijkstra and Heap, Minimum Spanning Tree and Union-Find
[Readings (KT): Ch. 2.5, 4.2, 4.4-4.6] [Suggested Exercises (KT): 4.8, 4.11, 4.13, 4.21]
03
[DRAFT]
6/30/2015 Dynamic Programming: Weighted Interval Scheduling, Knapsack Problem and Sequence Alignment
[KT: Ch. 6.1-6.4, 6.6] [Readings (KT): Ch. 2.5, 4.2, 4.4-4.6] [Suggested Exercises (KT): 6.6, 6.11, 6.17, 6.19, 6.28]
04 7/2/2015 Bellman-Ford Algorithm / Intro to Divide and Conquer: Merge Sort and Master Method
[KT: Ch. 6.8, 2.4, 5.1-5.3]
05 7/7/2015 More Divide and Conquer: Closest Pair, Integer Multiplication / Data Structures
[KT: Ch. 5.4-5.5]
06 7/9/2015 Intro to Network Flow: Ford-Fulkerson Algorithm and Max-Flow Min-Cut Theorem
[KT: Ch. 7.1-7.2]
07 7/14/2015 Applications of Network Flow: Matching, Disjoint Path Problem
[KT: Ch. 7.5-7.6]
08 7/16/2015 Extension of Network Flow: Circulation and Demands / Image Segmentation Problem
[KT: Ch. 7.7, 7.10]
09 7/21/2015 Midterm (In-class) at 11:00am.
[Coverage: Lectures 1 up to 8 and Homework 1 up to 3, inclusive. (subject to change and will be finalized 1 week prior to exam.) ]
10 7/23/2015 Computational Tractability: P vs. NP and Reductions.
[KT: Ch. 8; more to be announced later ]
11 7/28/2015 NP-completeness and reductions.
[KT: Ch. 8; more to be announced later ]
12 7/30/2015 Randomized Algorithms. (Details to be announced.)
[KT: Ch. 13.1-13.5 ]
13 8/04/2015 Approximation Algorithms. (Details to be announced.)
[KT: Ch. 10.1, 11.1, 11.3 ]
14 8/06/2015 Approximation Algorithms.(Details to be announced.)
[KT: Ch. 11.8, 11.6 ]
15 8/11/2015 TBA. (Details to be announced.)
[KT: TBA ]
16 8/13/2015 Extra Topics. Class Review.
[KT: TBA ]
8/15/2015 Final Exam at 8:30 am.
[Coverage: Lectures 1 to 15 (inclusive) and all homework assignments.]