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.
Link to all lecture VIDEOS.

Lecture No. Date Topics and Reading
01 [PDF] 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] 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 [PDF] 6/30/2015 Dynamic Programming: Five Problems (WISP, SLSP, Subset-Sum, Sequence Alignment, and Bellman-Ford Algorithm).
[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 [PDF] 7/2/2015 Bellman-Ford Algorithm / Divide and Conquer: Merge Sort, Counting Inversion, Master Method, Closest Pair Problem, and Integer Multiplication Problem
[KT: Ch. 6.8, 2.4, 5.1-5.5] [Suggested Exercises (KT): 5.1, 5.2, 5.4, 5.6]
05 [DRAFT] 7/7/2015 Data Structures / Intro to Network Flow and Max-Flow Min-Cut Theorem
[KT: Ch. 7.1-7.3] [Suggested Exercises (KT): 7.1, 7.2, 7.3]
06 [DRAFT] 7/9/2015 Applications of Network Flow: Bipartite Matching, Disjoint Path Problem, Circulation with Demands
[KT: Ch. 7.5-7.7] [Suggested Exercises (KT): 7.8, 7.13, 7.22]
07 [DRAFT] 7/14/2015 Applications of Network Flow: Survey Design, Airline Scheduling, Image Segmentation, Project Selection
[KT: Ch. 7.8-7.11] [Suggested Exercises (KT): 7.20, 7.22, 7.29]
08 7/16/2015 Topics TBA. (Possibly, review for midterm).
[KT: TBA] [Suggested Exercises: Practice Midterm (TBA)]
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.]