CS 161 Lectures Current Lecture Schedule

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).

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.

The slides are the best resource for what actually happened in lecture. The IPython Notebooks have implementation details that the slides may be missing. The lecture notes and reading assignments have mathematical details the slides may be missing. Most of the lecture notes are adapted from Virginia Williams' Spring 2015 offering of CS161.

Lecture 1: Why are you here? And do you know how to multiply integers?

Resources from class:

Lecture 2: MergeSort, Recurrences, and Asymptotics

Before class:

Resources from class: Relevant reading (either before or after class, whatever works best for you):
  • CLRS Sections 2.3 and 3.

Lecture 3: More recurrences and the master theorem

Before class:

Resources from class: Relevant reading (either before or after class, whatever works best for you):
  • CLRS Sections 4.3-4.5.

Lecture 4: The Substitution Method and the Selection problem

Before class:

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

Lecture 5: Randomized Algorithms and QuickSort

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 6: BucketSort, RadixSort, and Sorting Lower Bounds

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

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 8: Hashing!

Before class:

Resources from class: Relevant reading (either before or after class, whatever works best for you):
  • CLRS Ch. 11.

Lecture 9: Graphs, BFS and DFS

Before class:

Resources from class: Relevant reading (either before or after class, whatever works best for you):
  • CLRS Ch. 22.1-22.4.

Lecture 10: Finding Strongly Connected Components

Before class:

Resources from class: Relevant reading (either before or after class, whatever works best for you):
  • CLRS Ch. 22.5.

Lecture 11: Dijkstra's Algorithm and Bellman-Ford

Before class:

  • Pre-lecture exercise: recover from the midterm.
Resources from class: Relevant reading (either before or after class, whatever works best for you):
  • CLRS Ch. 24.1, 24.3.

Lecture 12: Dynamic Programming and shortest paths: Bellman-Ford and Floyd-Warshall

Before class:

Resources from class: Relevant reading (either before or after class, whatever works best for you):
  • CLRS Ch. 25.2, 15.1.

Lecture 13: More dynamic programming

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 14: Greedy Algorithms

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 15: Minimum Spanning Trees

Before class:

Resources from class: Relevant reading (either before or after class, whatever works best for you):
  • CLRS Ch. 23

Lecture 16: Minimum Cuts and Karger's Algorithm

Before class:

Resources from class: Relevant reading (either before or after class, whatever works best for you):
  • Kleinberg and Tardos Section 3.2 (here)

Lecture 17: Max Flow and the Ford-Fulkerson Algorithm

Before class:

Resources from class: Relevant reading (either before or after class, whatever works best for you):
  • CLRS Ch. 26.1, 26.2, 26.3

Lecture 18: What's next?

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
9/25. Lecture 1: Why are you here? 9/27. Lecture 2: MergeSort and Asymptotics 9/29. Homework 1 Assigned
10/2. Lecture 3: Solving Recurrences and the Master Theorem 10/4. Lecture 4: Median and Selection 10/6. Homework 1 Due; Homework 2 Assigned
10/9. Lecture 5: Randomized Algorithms and QuickSort 10/11. Lecture 6: BucketSort and Lower Bounds for Sorting 10/13. Homework 2 Due; Homework 3 Assigned
10/16. Lecture 7: Binary Search Trees 10/18. Lecture 8: Hashing 10/20. Homework 3 Due; Homework 4 Assigned
10/23. Lecture 9: Graphs and BFS and DFS 10/25. Lecture 10: Strongly Connected Components 10/27. Homework 4 Due
10/30. MIDTERM 11/1. Lecture 11: Dijkstra and Bellman-Ford 11/3. Homework 5 Assigned
11/6. Lecture 12: Dynamic Programming: Bellman-Ford (again) and Floyd-Warshall 11/8. Lecture 13: More dynamic programming: LCS, Knapsack, Independent Set 11/10. Homework 5 Due; Homework 6 Assigned
11/13. Lecture 14: Greedy Algorithms 11/15. Lecture 15: Minimum Spanning Trees 11/17. Homework 7 assigned. Homework 6 is due Sunday 11/19.
11/20. Thanksgiving Break 11/22. Thanksgiving Break 11/24. Thanksgiving Break
11/27. Lecture 16: Min Cut and Karger's Algorithm 11/29. Lecture 17: Max Flow and Ford-Fulkerson 12/1. Homework 7 Due
12/4. Lecture 18: What's next? 12/6. "Lecture" 19: Review session 12/8. --