Notes on Lecture Materials
- Future Lectures: are still in draft form and may have broken links.
- 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.
- What are all these things for?
- The slides/lecture videos are the best resource for what actually happened in lecture.
- The reading assignments have mathematical details the slides may be missing. You should do the reading assignments, either before or after class, to make sure you get these missing details.
- The IPython Notebooks have implementation details that the slides may be missing. They are there in case you want to play around with them or double-check something about implementation, but they are not required.
Lecture 1: Why are you here? And do you know how to multiply integers?
(4/3)
Lecture 2: Asymptotics, Worst-Case Analysis, and MergeSort
(4/5)
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 (4/10)
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 (4/12)
Before class:
Resources from class:
Relevant reading (either before or after class, whatever works best for you):
Lecture 5: Randomized Algorithms and QuickSort (4/17)
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 (4/19)
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 (4/24)
Before class:
Resources from class:
Relevant reading (either before or after class, whatever works best for you):
Lecture 8: Hashing! (4/26)
Before class:
Resources from class:
Relevant reading (either before or after class, whatever works best for you):
Lecture 8.5: Embedded EthiCS and Review! (5/1)
Before class:
- Come with questions for midterm review!
Resources from class:
Lecture 9: Graphs, BFS and DFS (5/3)
Before class:
Resources from class:
Relevant reading (either before or after class, whatever works best for you):
Lecture 10: Finding Strongly Connected Components (5/8)
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 (5/10)
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 (5/15)
Before class:
Resources from class:
Relevant reading (either before or after class, whatever works best for you):
Lecture 13: More dynamic programming (5/17)
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 (5/22)
Before class:
Resources from class:
Relevant reading (either before or after class, whatever works best for you):
Lecture 15: Minimum Spanning Trees (5/24)
Before class:
Resources from class:
Relevant reading (either before or after class, whatever works best for you):
5/29: No class (Memorial Day)
Have a nice long weekend!
Lecture 16: Max Flow and the Ford-Fulkerson Algorithm (5/31)
Before class:
Resources from class:
Relevant reading (either before or after class, whatever works best for you):
Lecture 16.5: Embedded EthiCS and Review! (6/5)
Before class:
- Come with questions for final exam review!
Resources from class:
Lecture 17: What's next? (6/7)
Before class:
Resources from class:
Relevant reading (either before or after class, whatever works best for you):