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: ~10 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:

Midterm and Final

Midterm 1: Tuesday, October 16, 3:00 pm - 4:20 pm, CEMEX Auditorium
Midterm 2: Tuesday, November 6, 3:00 pm - 4:20 pm
Final: Tuesday, December 11, 3:30 pm - 6:30 pm

Both the midterm and final are closed-book. In the midterm, you are allowed to bring one handwritten letter-sized singled-sided page of notes, that YOU have prepared YOURSELF. In the final, you are allowed to bring one handwritten letter-sized double-sided 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. Note that since the class has often historically only had a single midterm, the primary purpose of reviewing these practice exams for midterm 1 would be to give an idea of the length/format of the midterm, rather than providing additional practice on concepts specific to midterm 1.

Practice Midterm 1
Solutions to Practice Midterm 1
Practice Midterm 2
Solutions to Practice Midterm 2

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]
  • 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]

    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!