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 7/30/2015 Approximation: Load Balancing, Set Cover, VC (Rounding); Randomized: Min-cut, Coupon Collector, MAX 3-SAT.
[Readings (KT): Ch. 11.1, 11.3, 11.6; Ch. 13.1-13.4; ] [Suggested Exercises (KT): TBA]
13 8/04/2015 Randomized Algorithm: Contention Resolution, Min-cut, Coupon Collector, MAX 3-SAT; Approximation: VC (Pricing Method), PTAS for Knapsack
[Readings (KT): Ch. 11.4, 11.8; Ch. 13.1-13.4 (13.12 may be helpful for those who need to review probability theory)] [Suggested Exercises (KT): TBA]
14 8/06/2015 Randomized Algorithms: Median-Finding and Quick Sort, Hashing; Sorting Algorithms
[Readings (KT): Ch. 13.5, 13.6 (13.7 is optional)] [Suggested Exercises (KT): TBA]
15 8/11/2015 Small Vertex Cover and Solving Hard Problems on Trees. co-NP.
[Readings (KT): Ch. 10.1-10.2; Ch. 8.9;] [Suggested Exercises (KT): TBA]
16 8/13/2015 Class Review.
[Readings (KT): NONE! AWESOME!] [Suggested Exercises: Practice Final Exam!]
8/15/2015 Final Exam at 8:30 am.
[Coverage: Lectures 1 to 16 (inclusive) and all homework assignments.]