Notes:
- Lecture Schedule: A lecture schedule is posted on the main page.
- 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.
- Note about recordings: Video cameras located in the back of the room will capture the instructor presentations in this course. For your convenience, you can access these recordings by logging into the course Canvas site. These recordings might be reused in other Stanford courses, viewed by other Stanford students, faculty, or staff, or used for other education and research purposes. Note that while the cameras are positioned with the intention of recording only the instructor, occasionally a part of your image or voice might be incidentally captured. If you have questions, please contact a member of the teaching team.
- Reading assignments: You should do the reading assignments, either before or after class, to make sure you understand details that may have been skipped during lecture.
- 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/6)
Lecture 2: Asymptotics, Worst-Case Analysis, and MergeSort
(1/8)
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):
Lecture 3: More recurrences, the master theorem, and the substitution method (1/13)
Before class:
Resources from class:
Relevant reading (either before or after class, whatever works best for you):
Lecture 4: More substitution method and the selection problem (1/15)
Before class:
Resources from class:
Relevant reading (either before or after class, whatever works best for you):
Lecture 5: Randomized Algorithms and QuickSort (1/22)
Before class:
Resources from class:
Relevant reading (either before or after class, whatever works best for you):
Lecture 6: BucketSort, RadixSort, and Sorting Lower Bounds (1/27)
Before class:
Resources from class:
Relevant reading (either before or after class, whatever works best for you):
- AI Ch. 5.6; CLRS 8.2 and 8.3
Lecture 7: Binary Search Trees and Red-Black Trees (1/29)
Before class:
Resources from class:
Relevant reading (either before or after class, whatever works best for you):
Lecture 8: Hashing! (2/3)
Before class:
Resources from class:
Relevant reading (either before or after class, whatever works best for you):
Lecture 9: Graphs, BFS and DFS (2/5)
Before class:
Resources from class:
Relevant reading (either before or after class, whatever works best for you):
Lecture 10: Finding Strongly Connected Components (2/10)
Before class:
Resources from class:
Relevant reading (either before or after class, whatever works best for you):
Lecture 11: Dijkstra's Algorithm and Bellman-Ford (2/12)
Before class:
Resources from class:
Relevant reading (either before or after class, whatever works best for you):
Lecture 12: Dynamic Programming and shortest paths: Bellman-Ford and Floyd-Warshall (2/19)
Before class:
Resources from class:
Relevant reading (either before or after class, whatever works best for you):
Lecture 13: More dynamic programming (2/24)
Before class:
(No pre-lecture exercise today!)
Resources from class:
Relevant reading (either before or after class, whatever works best for you):
Lecture 14: Greedy Algorithms (2/26)
Before class:
Resources from class:
Relevant reading (either before or after class, whatever works best for you):
Lecture 15: Minimum Spanning Trees (3/2)
Before class:
Resources from class:
Relevant reading (either before or after class, whatever works best for you):
Lecture 16: Minimum Cuts and Karger's Algorithm (3/4)
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 17: Max Flow and the Ford-Fulkerson Algorithm (3/9)
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? (3/11)
Before class:
Resources from class:
Relevant reading (either before or after class, whatever works best for you):