CS 161 Lectures Current Lecture Schedule

Lectures

Notes:
  • Future Lectures: Greyed-out lectures are still in draft form and may have broken links. (And the in-class materials for all lectures may be updated, especially for lectures that have not yet occured).
  • IPython notebooks: In most browsers, use right-click and save-as to download the .ipynb and .py files. All IPython notebooks will assume you are using Python 3.
  • Videos: Lecture videos can be found through canvas here. For help, click here. They can also be found on mvideox here.
  • Reading assignments: You should do the CLRS reading assignments, either before or after class, to make sure you understand details that may have been skipped during lecture.

    There are also (optional) lecture notes available, most of which are adapted from Virginia Williams' Spring 2015 offering of CS161. These lecture notes are from a previous offering of CS161 and are not being maintained for this version of the course (in particular, they are not relevant for bug bounty points), but you may use them if you find them helpful.

  • What are are these things for? The slides/lecture videos are the best resource for what actually happened in lecture. The IPython Notebooks have implementation details that the slides may be missing. The reading assignments have mathematical details the slides may be missing.

Lecture 1: Why are you here? And do you know how to multiply integers? (1/7)

Resources from class:

Lecture 2: MergeSort, Recurrences, and Asymptotics (1/9)

Before class:

  • Pre-lecture exercise
  • The pre-lecture exercise references this IPython notebook. [NOTE: right-click and save-as (or crtl-click and save-link-as) to download the IPython notebook (same as all .ipynb and all .py files on this site. Be careful that you don't save it as a text file, or Jupyter won't know what to do with it.]
Resources from class: Relevant reading (either before or after class, whatever works best for you):
  • CLRS Sections 2.3 and 3.
  • Lecture Notes (optional lecture notes from last year; based on Virginia Williams' lecture notes).

Lecture 3: More recurrences, the master theorem, and the substitution method (1/14)

Before class:

Resources from class: Relevant reading (either before or after class, whatever works best for you):
  • CLRS Sections 4.3-4.5.
  • Lecture Notes (optional lecture notes from last year; based on Virginia Williams' lecture notes).

Lecture 4: More substitution method and the selection problem (1/17)

Before class:

Resources from class: Relevant reading (either before or after class, whatever works best for you):
  • CLRS Chapter 9
  • Lecture Notes (optional lecture notes from last year; based on Virginia Williams' lecture notes).

Lecture 5: Randomized Algorithms and QuickSort (1/23)

Before class:

Resources from class: Relevant reading (either before or after class, whatever works best for you):
  • CLRS Chapter 7 and 5.1,5.2,5.3.
  • Lecture Notes (optional lecture notes from last year; based on Virginia Williams' lecture notes).

Lecture 6: BucketSort, RadixSort, and Sorting Lower Bounds (1/28)

Before class:

Resources from class: Relevant reading (either before or after class, whatever works best for you):

Lecture 7: Binary Search Trees and Red-Black Trees (1/30)

Before class:

Resources from class: Relevant reading (either before or after class, whatever works best for you):
  • CLRS 12.1, 12.2, 12.3, Ch. 13.
  • Lecture Notes (optional lecture notes from last year; based on Virginia Williams' lecture notes).

Lecture 8: Hashing! (2/4)

Special guest lecturer: Greg Valiant!

Before class:

  • (No pre-lecture exercise today).
Resources from class: Relevant reading (either before or after class, whatever works best for you):
  • CLRS Ch. 11.
  • Lecture Notes (optional lecture notes from last year; based on Virginia Williams' lecture notes).

Lecture 9: Graphs, BFS and DFS (2/6)

Before class:

Resources from class: Relevant reading (either before or after class, whatever works best for you):
  • CLRS Ch. 22.1-22.4.
  • Lecture Notes (optional lecture notes from last year; based on Virginia Williams' lecture notes).

Lecture 10: Finding Strongly Connected Components (2/11)

Before class:

Resources from class: Relevant reading (either before or after class, whatever works best for you):
  • CLRS Ch. 22.5.
  • Lecture Notes (optional lecture notes from last year; based on Virginia Williams' lecture notes).

Lecture 11: Dijkstra's Algorithm and Bellman-Ford (2/13)

Before class:

Resources from class: Relevant reading (either before or after class, whatever works best for you):
  • CLRS Ch. 24.1, 24.3.
  • Lecture Notes (optional lecture notes from last year; based on Virginia Williams' lecture notes).

Lecture 12: Dynamic Programming and shortest paths: Bellman-Ford and Floyd-Warshall (2/25)

Before class:

Resources from class: Relevant reading (either before or after class, whatever works best for you):
  • CLRS Ch. 25.2, 15.1.
  • Lecture Notes (optional lecture notes from last year; based on Virginia Williams' lecture notes).

Lecture 13: More dynamic programming (2/27)

Before class:

    (No pre-lecture exercise today!)
Resources from class: Relevant reading (either before or after class, whatever works best for you):
  • CLRS Ch. 15.4
  • Lecture Notes (optional lecture notes from last year; based on Virginia Williams' lecture notes).

Lecture 14: Greedy Algorithms (3/4)

Before class:

Resources from class: Relevant reading (either before or after class, whatever works best for you):
  • CLRS Ch. 16.1, 16.2, 16.3
  • Lecture Notes (optional lecture notes from last year; based on Virginia Williams' lecture notes).

Lecture 15: Minimum Spanning Trees (3/6)

Before class:

Resources from class: Relevant reading (either before or after class, whatever works best for you):
  • CLRS Ch. 23
  • Lecture Notes (optional lecture notes from last year; based on Virginia Williams' lecture notes).

Lecture 16: Minimum Cuts and Karger's Algorithm (3/11)

Before class:

Resources from class: Relevant reading (either before or after class, whatever works best for you):
  • Kleinberg and Tardos Section 13.2 (here)
  • Lecture Notes (optional lecture notes from last year; based on Virginia Williams' lecture notes).

By request (Piazza post @1533), a few completely optional practice problems: problems and solutions

Schedule

(The future is mutable).
Monday Wednesday Friday
1/7. Lecture 1: Why are you here? 1/9. Lecture 2: MergeSort and Asymptotics (Ch. 2.3 and 3) 1/11. Homework 1 Assigned
1/14. Lecture 3: Solving Recurrences and the Master Theorem (Ch. 4.3-4.5) 1/16. Lecture 4: Median and Selection (Ch. 9) 1/18. Homework 1 Due; Homework 2 Assigned
1/21. MLK Day. No class. 1/23. Lecture 5: Randomized Algorithms and QuickSort (Ch 7, 5.1,5.2,5.3) 1/25. Homework 2 Due. (No homework since we haven't covered enough new stuff).
1/28. Lecture 6: BucketSort and Lower Bounds for Sorting (Ch. 8.1,8.2) 1/30. Lecture 7: Binary Search Trees and Red-Black Trees (Ch. 12.1, 12.2, 12.3, 13) 2/1. Homework 3 Assigned.
2/4. Lecture 8: Hashing (Ch. 11) 2/6. Lecture 9: Graphs and BFS and DFS (Ch. 22.1-22.4) 2/8. Homework 3 Due; Homework 4 Assigned
2/11. Lecture 10: Strongly Connected Components (Ch. 22.5) 2/13. Lecture 11: Dijkstra and Bellman-Ford (Ch. 24.1, 24.3) 2/15. Homework 4 Due; No homework assigned (study for midterm!)
2/18. President's Day; No class. 2/20. MIDTERM 2/22. Homework 5 Assigned.
2/25. Lecture 12: Dynamic Programming: Bellman-Ford (again) and Floyd-Warshall (Ch. 25.2, 15.1) 2/27. Lecture 13: More dynamic programming: LCS, Knapsack, Independent Set (Ch. 15.4) 3/1. Homework 5 due; Homework 6 Assigned
3/4. Lecture 14: Greedy Algorithms (Ch. 16.1, 16.2, 16.3) 3/6. Lecture 15: Minimum Spanning Trees (Ch. 23) 3/8. Homework 6 Due; Homework 7 assigned.
3/11. Lecture 16: Min Cuts and Karger's algorithm (Kleinberg and Tardos 13.2 (posted)) 3/13. Lecture 17: What's next? 3/15. Homework 7 Due