Welcome to CS 161!

Homework

Homework will be due Thursdays at 9:30 am.

• Grading guidelines
• Homework 1 - [feedback form] - [solutions]
• Homework 2 - [feedback form] - [solutions]
• Homework 3 - [feedback form] - [solutions]
• Homework 4 - [feedback form] - [solutions]
• Homework 5 - [feedback form] - [solutions]
• Homework 6 - [feedback form] - [solutions]

Exams

The final exam will be in NVIDIA Auditorium, from 8:30-11:30 am, on Friday, August 12.

Addison will be hosting a final exam review session this Wednesday, from 2:30-3:20 pm, in NVIDIA Auditorium. The session will be recorded.

• Practice final - [solutions]

Lectures

Jessica will be holding lectures in Gates B1, on Tuesdays and Thursdays from 9:30-11:20 am. The lectures will be recorded and lecture notes will be posted on the course website.

• Lecture 1 - Insertion sort, loop invariants, runtime analyses, asymptotic analysis.
• Lecture 2 - Merge sort, divide and conquer.
• Lecture 3 - Recurrence relations (substitution method, recursion trees, master theorem); maximum subarray problem.
• Lecture 4 - Heaps.
• Lecture 5 - Partition, median of medians algorithm, more recurrence practice.
• Lecture 6 - Randomized algorithms, quicksort.
• Lecture 7 - Lower bounds on comparison sorting, counting sort, stacks, queues, linked lists.
• Lecture 8 - Binary search trees, red-black trees.
• Lecture 9 - Hashing.
• Lecture 10 - Graphs, depth-first search, topological sort.
• Lecture 11 - Strongly connected components, breadth-first-search, Dijkstra's algorithm.
• Lecture 12 - Dynamic programming.
• Lecture 13 - Greedy algorithms, activity selection problem, knapsack problem, Floyd-Warshall algorithm.
• Lecture 14 - Bellman-Ford algorithm, amortized analysis.
• Lecture 15 - Minimum spanning trees.
• Lecture 16 - Max flow.

Course information

• Textbook: Introduction to Algorithms (you can download the Stanford library copy through the link)
• Gradescope (use code 92EX2M): Gradescope
• Piazza: Piazza
• Syllabus: Syllabus
• Feedback form (for comments/suggestions/complaints about the course): Feedback
• Errata form (you get 2 points extra credit for finding errors in course material): Errata
• Email the instructor: Jessica Su (jtysu [at] stanford [dot] edu)

Office hours

This week's office hours will be held in the basement of the Huang Engineering Center, on

• Monday 3-5 pm (Jessica)
• Monday 7-9 pm (Peng Hui)
• Tuesday 7:30-9:30 pm (Jessica)
• Thursday 7:30-9:30 pm (David)

Remote students may join here (note: this is a new link, the old one doesn't work anymore for some reason).

Sections (completely optional)

David will be holding software engineering interview preparation workshops in Gates 104 most Mondays (6/27, 7/11, 7/18, 7/25, 8/1) from 6-6:50 pm.

• 6/27: [notes] [slides]
• 7/11: [slides]
• 7/18: [slides]
• 7/25: [slides]

Peng Hui will hold a seminar on how to write proofs, in Gates 104, on Friday 6/24, from 2-3 pm. [section notes]

Addison will be holding a final exam review session during the last week of the course.

Other resources

• CS 103 material from winter quarter.
• A guide to proofs (CS 103)
• A guide to writing induction proofs (CS 103)
• More material about proofs (CS 103)
• Thomas Cormen's explanation of loop invariants on Quora
• Material from CS 109 (Introduction to Probability for Computer Scientists)

Other non-resources

• Please click here to help me with my research project! This is for the Twitter crawler I talked about in Lecture 1 (the one that technically runs in O(1) time, even though it's quite slow).