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

Lecture 17: What's next? (3/13)

NOTE: Due to a faulty power supply in NVIDIA auditorium, there is no video recording for this lecture! However, there was no new content in this lecture that is required for the course, so this lecture is optional.

The main point of this lecture was to advertise some of the cool stuff that's coming up in future algorithms/theory classes. We apologize to the SCPD students and to the on-campus students who didn't make it to class, and we hope that the slides available below convey the material if you are interested in it. (Again, this lecture is optional for this course). If you missed the lecture and are interested in future algorithms courses (and your interest is not sated by the slides below), please email me (marykw) to set up a time to meet and chat about it! I love talking about this stuff!!! (Disclaimer, I might not be able to meet until Spring quarter).

Before class:

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

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