Lectures

Overview

This page contains lecture materials. Some notes:

  • 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.
  • Lecture Videos: Can all be found on Canvas.
    • 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 optional resources, there in case you want to play around with them or double-check something about implementation.

September 23
Lecture 1: Why are you here?

Before Class:

  • Nothing, it's the first class!
During Class: Relevant Reading: (Before of after class, whatever works best for you).
  • AI Chapter 1

September 25
Lecture 2: Asymptotics, Worst-Case Analysis, and MergeSort

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.]
During Class: Relevant Reading: (Before of after class, whatever works best for you).

September 30
Lecture 3: Solving Recurrences and the Master Theorem

Before Class:

During Class: Relevant Reading: (Before of after class, whatever works best for you).
  • AI Chapter 4

October 2
Lecture 4: Median and Selection

Before Class:

During Class: Relevant Reading: (Before of after class, whatever works best for you).

October 7
Lecture 5: Randomized Algorithms and QuickSort

Before Class:

During Class: Relevant Reading: (Before of after class, whatever works best for you).
  • AI Chapters 5.1-5.5

October 9
Lecture 6: BucketSort and Lower Bounds for Sorting

Before Class:

During Class: Relevant Reading: (Before of after class, whatever works best for you).
  • AI Chapter 5.6; CLRS 8.2 and 8.3. (Note: you can access CLRS for free online through the Stanford library; see the Resources page for more).

October 17
Lecture 7: Binary Search and Red-Black Trees

Before Class:

During Class: Relevant Reading: (Before of after class, whatever works best for you).
  • AI Chapter 11.

October 14
Exam I!

See Exams for more.

October 21
Lecture 8: Hashing

Before Class:

During Class: Relevant Reading: (Before of after class, whatever works best for you).
  • AI Chapter 12.1-12.4

October 23
Lecture 9: Graphs, DFS, and BFS

Before Class:

During Class: Relevant Reading: (Before of after class, whatever works best for you).
  • AI Chapter 8.1-8.5

October 28
Lecture 10: Strongly Connected Components

Before Class:

During Class: Relevant Reading: (Before of after class, whatever works best for you).
  • AI Chapter 8.6

October 30
Lecture 11: Dijkstra and Bellman-Ford

Before Class:

During Class: Relevant Reading: (Before of after class, whatever works best for you).
  • AI Chapter 9

November 4
Democracy Day

No class.

November 6
Exam II!

See Exams for more.

November 11
Lecture 12: Dynamic Programming: Bellman-Ford (again) and Floyd-Warshall

Before Class:

During Class: Relevant Reading: (Before of after class, whatever works best for you).
  • AI Chapter 16, 18

November 13
Lecture 13: More Dynamic Programming: LCS, Knapsack, Independent Set

Before Class:

During Class: Relevant Reading: (Before of after class, whatever works best for you).
  • AI Chapter 17

November 18
Lecture 14: Greedy Algorithms

Before Class:

During Class: Relevant Reading: (Before of after class, whatever works best for you).
  • AI Chapter 13, 14

November 20
Lecture 15: Minimum Spanning Trees

Before Class:

During Class: Relevant Reading: (Before of after class, whatever works best for you).
  • AI Chapter 15

November 25, 27
Fall Break!

Happy Thanksgiving :)

December 2
Lecture 16: Max-Flow and Ford-Fulkerson

Before Class:

During Class: Relevant Reading: (Before of after class, whatever works best for you).
  • CLRS Ch. 26.1, 26.2, 26.3

December 4
Lecture 17: What's next?

Before Class:

  • N/A
During Class: Relevant Reading:
  • N/A