[ Course Schedule  Midterm and Final  Homework Assignments  Recitations  Resources ]
Instructor: Gregory Valiant (email: gvaliant at cs)
Location and time: Monday and Wednesday 3:00 PM  4:20 PM, NVIDIA Auditorium
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: divideandconquer, dynamic programming, greedy algorithms, amortized analysis, randomization. Algorithms for fundamental graph problems: minimumcost 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: 7 homework assignments (35%), a midterm (25%), and a final exam (40%). We will drop your lowest homework grade.
Teaching Assistants
Luna FrankFischer [Head TA], luna16 at stanford
Dilsher Ahmed, dilsher at stanford
Michael Chen, mchen36 at stanford
Ashok Cutkosky, ashokc at stanford
Shloka Desai, shloka at stanford
David Eng, dkeng at stanford
Julien KawawaBeaudan, julienkb at stanford
Sam Kim, samhykim at stanford
Maxime Voisin, maximev at stanford
Daniel Wright, dlwright at stanford
Jimmy Wu, jimmyjwu at stanford
Andi Yang, andiy at stanford
Wilbur Yang, wilbury at stanford
Topics and readings for future lectures are tentative and may be changed as the course proceeds. The readings refer to the 3rd edition of CLRS (see Resources below), but older editions should be fine as well.
Monday  Wednesday  Friday 
1/9 Introduction, Why are you here? Read: Ch. 1 Notes (draft) 
1/11 MergeSort, Recurrences, Asymptotics Read: Ch. 2.3, 3 Notes (draft) 
1/13 Homework 1 released 
1/16 MLK Day (no classes)  1/18 Integer Multiplication, Solving Recurrences Read: Ch. 4.34.5 DasguptaPapadimitriouVazirani Sec. 2.2: [pdf] Notes (draft) 
1/20 Homework 1 due Homework 2 released 
1/23 Median and Selection Read: Ch. 9 Notes (draft) 
1/25 Quicksort, Probability and Randomized Algorithms Read: Ch. 7, 5 Notes (draft) 
1/27 Homework 2 due Homework 3 released 
1/30 Sorting Lower Bounds, Counting Sort Read: Ch. 8.12 Avrim Blum's Notes on sorting lower bounds Notes on Bucket Sort and Radix Sort (draft) 
2/1 Binary Search Trees Read: Ch. 12 Notes (draft) 
2/3 Homework 3 due Homework 4 released 
2/6 Hashing Read: Ch. 11 Notes (draft) 
2/8 Graphs, DFS, BFS Read: Ch. 22, 24 Notes (draft)  2/10 Homework 4 due Homework 5 released 
2/13 Strongly Connected Components Read: Ch. 24, 6 Notes (draft)  2/15 Dijkstra's Algorithm, Amortized Analysis, BellmanFord Algorithm Read: Ch. 24.1, 24.3 Notes (draft) 
2/17 Homework 5 due 
2/20 President's Day (no class) 
2/22 MIDTERM (CEMEX Auditorium) 

2/27 Dynamic Programming: FloydWarshall, Longest Common Subsequence Read: Ch. 25.2, 15.4 Notes (draft) 
3/1 Chain Matrix Multiplication, Knapsack, Independent Set Notes (draft) 
3/3 Homework 6 released 
3/6 Greedy Algorithms Read: Ch. 16 Notes (draft) 
3/8 Minimum Spanning Trees (MST) Read: Ch. 23 Notes (draft) 
3/10 Homework 6 due Homework 7 released 
3/13 Minimum Cut/Maximum Flow Notes1 and Notes2. Read: Ch. 26.13 
3/15 Whats Next?  3/17 Homework 7 due 
3/20 Final Exam, 3:30pm6:30pm 
Midterm: Wednesday, February 22, in class, 3:00 pm  4:20 pm
Final: Monday, March 20, 3:306:30pm.
Both the midterm and final are closedbook. In the midterm, you are allowed to bring one lettersized doublesided page of notes, that YOU have prepared YOURSELF. In the final, you are allowed to bring two lettersized doublesided page of notes (that you have prepared yourself).
The following practice exams are posted here as a resource; the material covered is similar to what we covered this quarter, but not identical.
Practice Midterm 1
Solutions to the Practice Midterm 1
Practice Midterm 2 (new)
Solutions to the Practice Midterm 2 (new)
Regrade Policy
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. The schedule (including locations) of the recitation sections appears in the office hours calendar. Each section covers the material of the previous week except for Friday sections that cover the material of the same week.
The main textbook we use is:
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, 3rd Edition, MIT Press
The book is available online through the Stanford library.
We will also occasionally use:
Jon Kleinberg, Éva Tardos, Algorithm Design, Pearson/AddisonWesley
Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, Algorithms, McGrawHill Education
We strongly recommend typesetting solutions to the homework assignments using LaTeX. LaTeX provides a convenient way to produce highquality 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.