Welcome to CS161!
HW No. | Due Date | Comments |
---|---|---|
HW 0 [pdf] |
June 30 at 4pm on Gradescope |
Homework 0 will NOT be graded. You may submit your solution on Gradescope to get yourself familiar with the tool. [ Solution ] If you find any error(s) in solution, please report on Piazza. |
HW 1
[pdf] |
July 3 at 4pm on Gradescope |
Grades released on July 9 at 3:20pm. (See stats here.) Please see Piazza post about HW1 updates here. [ Solution ] If you find any error(s) in solution, please report on Piazza (use the link above). |
HW 2
[pdf] |
July 10 at 4pm on Gradescope |
Posted on July 2 at 11:25pm. Last updated on July 5 at 4:30pm. Please see Piazza post about HW2 updates here. [ Solution ] If you find any error(s) in solution, please report on Piazza (use the link above). |
HW 3
[pdf] |
July 17 at 4pm on Gradescope | Posted on July 9 at 11:05pm. Last updated on July 15 at 9:00am. Please see Piazza post about HW3 updates here. [ Solution ] If you find any error(s) in solution, please report on Piazza (use the link above). |
HW 4
[pdf] |
July 31 at 4pm on Gradescope |
Posted on July 23 at 10:40pm. Last updated on July 23 at 10:40pm. Please see Piazza post about HW4 updates here. We've added some HINTS on Q2 and Q5 (on July 28 at 2pm). |
HW 5 | Aug 7 at 4pm on Gradescope | (Will be released on July 31 or before.) |
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.] |