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 Stats on Homework and Exams:

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).
[Readings (KT): Ch. 6.1-6.4, 6.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
[Readings (KT): Ch. 6.8, 2.4, 5.1-5.5] [Suggested Exercises (KT): 5.1, 5.2, 5.4, 5.6]
05 [PDF] 7/7/2015 Data Structures / Intro to Network Flow
[Readings (KT): Ch. 7.1-7.3] [Suggested Exercises (KT): 7.1, 7.2, 7.3]
06 [PDF] 7/9/2015 Max-Flow Min-Cut Theorem / Applications of Network Flow: Bipartite Matching, Disjoint Path Problem, Circulation with Demands
[Readings (KT): Ch. 7.3, 7.5-7.7] [Suggested Exercises (KT): 7.8, 7.13, 7.22]
07 [PDF] 7/14/2015 Applications of Network Flow: Survey Design, Airline Scheduling, Image Segmentation, Project Selection (optional)
[Readings (KT): Ch. 7.8-7.10; 7.11 is optional] [Suggested Exercises (KT): 7.20, 7.22, 7.29]
08 [PDF] 7/16/2015 Review for midterm. (come and ask questions, if you have any.)
09 7/21/2015 Midterm (In-class) at 11:00am.
See here for details.
[ Practice Midterm (Solution) ] [ Midterm Solution (Report errors here.) ]
10 [PDF] 7/23/2015 Computational Tractability: Reductions, P vs. NP, and NP-complete problems.
[Readings (KT): Ch. 8.1-8.4] [Suggested Exercises (KT): 8.1, 8.2]
11 [PDF] 7/28/2015 NP-complete problems: TSP, Hamiltonian Cycle, 3-D Matching, Graph Coloring, Numerical Problems.
[Readings (KT): Ch. 8.5-8.8 and 8.10] [Suggested Exercises (KT): 8.5, 8.7, 8.41]
12 [PDF] 7/30/2015 Approximation: Load Balancing, Set Cover, VC (Rounding); Randomized APX: MAX 3-SAT.
[Readings (KT): Ch. 11.1, 11.3, 11.6; Ch. 13.4; (Ch. 13.12 and 13.3 may be helpful for those who need to review probability theory)] [Suggested Exercises (KT): 11.1, 11.3, 11.12, 13.3]
13 [PDF] 8/04/2015 Randomized Algorithm: MAX 3-SAT, Global Min-cut, Randomized Median Finding, Randomized Quick Sort
[Readings (KT): 13.4, 13.2, 13.5; (Ch. 13.12 and 13.3 may be helpful for those who need to review probability theory)] [Suggested Exercises (KT): 13.1, 13.3, 13.12. ]
14 [PDF] 8/06/2015 Finding small vertex cover; Approximation: VC (Pricing Method); P, NP, and co-NP.
[Readings (KT): Ch. 10.1; 11.4; 8.9] [Suggested Exercises (KT): 10.1]
15 8/11/2015 Review for Final Exam.
[Readings (KT): None. ] [Suggested Exercises: Practice Final Exam!]
16 8/13/2015 What is next after CS161: Topics you can study/learn after taking CS161.; Q and A
[Readings (KT): NONE! AWESOME!] [Suggested Exercises: Practice Final Exam!]
8/15/2015 Final Exam at 8:30 am. SEE HERE
[Coverage: Lectures 1 to 16 (inclusive) and all homework assignments.]
Practice Final Exam (Solutions) (If you find typos/errors, please use the Piazza post above to report/ask.)