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.
  • 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?

Resources from class:

Lecture 2: MergeSort, Recurrences, and Asymptotics

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 3: More recurrences, the master theorem, and the substitution method

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: More 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.

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 Cut and Max Flow (Ch. 26.1, 26.2, 26.3) 3/13. Lecture 17: What's next? 3/15. Homework 7 Due