CS 161: Design and Analysis of Algorithms (Autumn 2018)

[ 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

Course Schedule and Lecture Notes

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 and Final

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

Sections

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.

  • Week 2: [Recitation 1] [Recitation 1 Solutions]
  • Week 3: [Recitation 2] [Recitation 2 Solutions]
  • Week 5: [Recitation 3] [Recitation 3 Solutions]
  • Week 6: [Recitation 4] [Recitation 4 Solutions]
  • Week 8: [Recitation 5] [Recitation 5 Solutions]
  • Week 9: [Recitation 6] [Recitation 6 Solutions]
  • Week 10: [Recitation 7] [Recitation 7 Solutions]
  • Homework Assignments

  • Homework 1 (released 9/25, due 10/2 at 3pm). [pdf] [raw LaTex file] [solutions]
  • Homework 2 (released 10/2, due 10/9 at 3pm). [pdf] [raw LaTex file] [image for raw LaTex file] [solutions]
  • Homework 3 (released 10/9). [pdf] [raw LaTex file] [solutions]
  • Homework 4 (released 10/23, due 10/30 at 3pm). [pdf] [raw LaTex file] [image for raw LaTex file] [solutions]
  • Homework 5 (released 11/1). [pdf] [raw LaTex file] [solutions]
  • Homework 6 (released 11/13, due 11/27 at 3pm). [pdf] [raw LaTex file] [solutions]
  • Homework 7 (released 11/27, due 12/4 at 3pm). [pdf] [raw LaTex file] [image for raw LaTex file] [solutions]
  • Homework 8 / Recitation 7 (released 12/4 at 3pm). [pdf] [solutions]

    Submission Instructions and Policies

    Resources

    Textbooks

    There is no required reading, but we recommend any combination of the following resources:

    LaTeX 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.

    Feedback

    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!