[ Course Schedule | Midterm and Final | Sections | Homework | Resources | Feedback ]
Instructor: Aviad Rubinstein (email: aviad at stanford)
Location and time:
Lecture:
Tuesday and Thursday 3:00 PM - 4:20 PM, Sapp Center for Science Teaching and Learning 111
Section:
Tuesday, 6:00 PM - 7:20 PM, 70-72A1 (Dana)
Wednesday, 10:30 AM - 11:50 AM, 110-101 (Jayden)
Wednesday, 10:30 AM - 11:50 AM, 420-245 (Deepak)
Wednesday, 1:30 PM - 2:50 PM, 420-245 (Ingerid)
Wednesday, 3:00 PM - 4:20 PM, 460-429 (Haojun)
Wednesday, 4:30 PM - 5:50 PM, 110-114 (Annie)
Wednesday, 6:00 PM - 7:20 PM, 420-245 (Abraham)
Thursday, 9:00 AM - 10:20 AM, 110-114 (Stefanie)
Thursday, 10:30 AM - 11:50 AM, 420-245 (Jon)
Thursday, 10:30 AM - 11:50 AM, School of Education 230 (Richard)
Thursday, 1:30 PM - 2:50 PM, Thornton 207 (Anchit)
Important!
Sign up on Piazza for discussions and announcements.
We strongly encourage discussion and asking questions on Piazza. Questions to the course staff (that are not addressed to a specific person) can be sent using a private post in Piazza.
Course Description
This course will cover the basic approaches and mindsets for analyzing and designing algorithms and data structures. Topics include the following: Worst and average case analysis. Recurrences and asymptotics. Efficient algorithms for sorting, searching, and selection. Data structures: binary search trees, heaps, hash tables. Algorithm design techniques: divide-and-conquer, dynamic programming, greedy algorithms, amortized analysis, randomization. Algorithms for fundamental graph problems: minimum-cost spanning tree, connected components, topological sort, and shortest paths. Possible additional topics: network flow, string searching.
Prerequisites: CS 103 or CS 103B; CS 109 or STATS 116.
Requirements: ~8 homework assignments (20%), 2 midterms (20% and 25%), and a final exam (35%).
Teaching Assistants
Richard Mu [Head TA], rmu at stanford
Dana Murphy [Head TA], dkm0713 at stanford
Stefanie Baby, stef96 at stanford
Jon Deaton, jdeaton at stanford
Ingerid Fosli, ifosli at stanford
Anchit Gupta, anchitg at stanford
Haojun Li, haojun at stanford
Deepak Narayanan, deepakn at stanford
Jayden Navarro, jaynavar at stanford
Eric Redondo, eredondo at stanford
Annie Shi, annies at stanford
Abraham Starosta, starosta at stanford
Topics and readings for future lectures are tentative and may be changed as the course proceeds.
Tuesday | Thursday |
9/25 Lecture 1: Why are you here? Read: Ch. 1 Slides: [pdf] [pptx] Notes (draft): [pdf] |
9/27 Lecture 2: MergeSort, Recurrences, Asymptotics Read: Ch. 2.3, 3 Slides: [pdf] [pptx] Notes (draft): [pdf] |
10/2 Lecture 3: Solving Recurrences and the Selection Problem Read: Ch. 4.3-4.5, Ch. 9 Slides: [pdf] [pptx] Notes (draft): [pdf] |
10/4 Lecture 4: Randomized Algorithms and QuickSort Read: Ch. 7 and 5.1-5.3 Slides: [pdf] [pptx] Notes (draft): [pdf] |
10/9 Lecture 5: Sorting Lower Bounds and O(n)-Time Sorting Read: Ch. 8.1-2 Slides: [pdf] [pptx] Notes (draft): [pdf] Avrim Blum's Notes on sorting lower bounds: [pdf] |
10/11 Lecture 6: Binary Search Trees Read: Ch. 12 Slides: [pdf] [pptx] Notes (draft): [pdf] |
10/16 MIDTERM 1 (CEMEX Auditorium) |
10/18 Lecture 7: Hashing Read: Ch. 11 Slides: [pdf] [pptx] Notes (draft): [pdf] |
10/23 Lecture 8: Graphs, BFS, and DFS Read: Ch. 22.1-22.4 Slides: [pdf] [pptx] Notes (draft): [pdf] |
10/25 Lecture 9: Finding Strongly Connected Components Read: Ch. 22.5 Slides: [pdf] [pptx] Notes (draft): [pdf] |
10/30 Lecture 10: Dynamic Programming and Floyd-Warshall Read: Ch. 25.2, 15.1 Slides: [pdf] [pptx] Notes (draft): [pdf] |
11/1 Lecture 11: More Dynamic Programming Read: Ch. 15.4 Slides: [pdf] [pptx] Notes (draft): [pdf] |
11/6 MIDTERM 2 (Cubberley Auditorium) |
11/8 Lecture 12: Dijkstra's Algorithm and Bellman-Ford Read: Ch. 24.1, 24.3 Slides: [pdf] [pptx] Notes (draft): [pdf] |
11/13 Lecture 13: Greedy Algorithms Read: Ch. 16.1, 16.2, 16.3 Slides: [pdf] [pptx] Notes (draft): [pdf] |
11/15 Lecture 14: Minimum Spanning Trees Read: Ch. 23 Slides: [pdf] [pptx] Notes (draft): [pdf] |
11/20 Thanksgiving Break |
11/22 Thanksgiving |
11/27 Lecture 15: Min Cuts, Max Flows, and Ford-Fulkerson Read: Ch. 26.1, 26.2, 26.3 Slides: [pdf] [pptx] Notes (draft): [pdf] |
11/29 Lecture 16: Min Cuts and Karger's Algorithm Read: Kleinberg and Tardos Section 3.2: [pdf] Slides: [pdf] [pptx] Notes (draft): [pdf] |
12/4 Lecture 17: Approximation Algorithms: Max-Cut and Vertex Cover Slides: [pdf] [pptx] Notes (draft): [pdf] |
12/6 Lecture 18: What's Next? Slides: [pdf] [pptx] |
Midterm 1: Tuesday, October 16, 3:00 pm - 4:20 pm, CEMEX Auditorium
Midterm 1
Midterm 1 Solutions
Midterm 2: Tuesday, November 6, 3:00 pm - 4:20 pm, Cubberley Auditorium
Midterm 2
Midterm 2 Solutions
Final: Tuesday, December 11, 3:30 pm - 6:30 pm, Hewlett 200
Final
Final Solutions
Both the midterm and final are closed-book. For Midterm 1, you are allowed to bring one handwritten singled-sided letter-sized page of notes, that YOU have prepared YOURSELF. For Midterm 2 and the final, you are allowed to bring one handwritten double-sided letter-sized page of notes (that you have prepared yourself).
The following practice exams are posted here as a resource; the material covered is similar, but not identical, and their structure may differ from this quarter's final exam.
Practice Midterm 1
Practice Midterm 1 Solutions
Practice Midterm 2
Practice Midterm 2 Solutions
Practice Midterm 3
Practice Midterm 3 Solutions
Practice Final
Practice Final Solutions
We hold recitation sections in order to review some of the material and solve additional exercises with the students in smaller groups. The sections are optional but highly recommended.
There is no required reading, but we recommend any combination of the following resources:
We strongly recommend typesetting solutions to the homework assignments using LaTeX. LaTeX provides a convenient way to produce high-quality documents and it is the standard used for typesetting computer science papers.
Guide: An introduction to LaTeX can be found here. Other guides can be found at howtoTeX and Wikibooks.
Online environments: If you do not wish to install LaTeX, ShareLaTeX and Overleaf are online environments that compile previews of your documents as you type and allow you to share documents with collaborators (this feature won't be useful in this course, though). As a Stanford student, you get a free Overleaf Pro account.
LyX: LyX is a version of LaTeX with graphical interface.
Finding mathematical symbols: The introduction mentioned above contains a table of mathematical symbols in LaTeX. Alternatively, consider Detexify.
Please give us feedback via this anonymous feedback form.
We welcome any comments, suggestions or complaints about the class, and will use your feedback to improve!