CS 161: Design and Analysis of Algorithms (Fall 2016)

[ Course Schedule | Midterm and Final | Homework Assignments | Recitations | Resources ]

Instructor: Moses Charikar (email: moses at cs)

Location and time: Monday and Wednesday 1:30 PM - 2:50 PM, CEMEX 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
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: 7 homework assignments (35%), a midterm (25%), and a final exam (40%).

Teaching Assistants
Will Chen, wic006 at stanford
Ofir Geri (Head TA), ofirgeri at cs
Seth Hildick-Smith, sethjhs at cs
Luke Johnston, lukej at stanford
Anthony Kim, tonye(last-name) at stanford
Sam Kim, samhykim at stanford
Priyanka Nigam, pnigam at stanford
Jimmy Wu, jimmyjwu at stanford
Wilbur Yang, wilbury at cs

Course Schedule and Lecture Notes

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
9/26
Introduction, Why are you here?
Read: Ch. 1
Notes (draft)
9/28
MergeSort, Recurrences, Asymptotics
Read: Ch. 2.3, 3
Notes (draft)
9/30
Homework 1 released
10/3
Integer Multiplication, Solving Recurrences
Read: Ch. 4.3-4.5
Dasgupta-Papadimitriou-Vazirani Sec. 2.2: [pdf]
Notes (draft)
10/5
Median and Selection
Read: Ch. 9
Notes (draft)
10/7
Homework 1 due
Homework 2 released
10/10
Quicksort, Probability and Randomized Algorithms
Read: Ch. 7, 5
Notes (draft)
10/12
Sorting Lower Bounds, Counting Sort
Read: Ch. 8.1-2
Board transcript
Avrim Blum's Notes on sorting lower bounds
Notes on Bucket Sort and Radix Sort (draft)
10/14
Homework 2 due
Homework 3 released
10/17
Binary Search Trees
Read: Ch. 12
Board transcript
Notes (draft)
10/19
Hashing
Read: Ch. 11
Board transcript
Notes (draft)
10/21
Homework 3 due
Homework 4 released
10/24
Graphs, DFS, BFS, Dijkstra's Algorithm
Read: Ch. 22, 24
Notes (draft)
Slides available on Piazza
10/26
Strongly Connected Components
Read: Ch. 24, 6
Notes (draft)
Slides available on Piazza
10/28
Homework 4 due
10/31
Midterm
11/2
Dijkstra's Algorithm, Amortized Analysis, Bellman-Ford Algorithm
Read: Ch. 24.1, 24.3
Notes (draft)
11/4
Homework 5 released
11/7
Dynamic Programming: Floyd-Warshall, Longest Common Subsequence
Read: Ch. 25.2, 15.4
Notes (draft)
11/9
Chain Matrix Multiplication, Knapsack, Independent Set
Notes (draft)
11/11
Homework 5 due
Homework 6 released
11/14
Greedy Algorithms
Read: Ch. 16
Notes (draft)
11/16
Minimum Spanning Trees (MST)
Read: Ch. 23
Notes (draft)
11/18
Homework 6 due
Homework 7 released
11/21-11/25
Thanksgiving break - no classes
11/28
Maximum Flow
Read: Ch. 26.1-3
11/30
More Maximum Flow, Graph Matchings
Read: Ch. 26.2-3
12/2
Homework 7 due
12/5
The Wider World of Algorithms
12/7
Review Session
12/14
Final Exam

Midterm and Final

Midterm: Monday, October 31, in class, 1:30 pm - 2:50 pm
Final: Wednesday, December 14, 3:30 pm - 6:30 pm (Location TBA)

Both the midterm and final are closed-book, but you are allowed to bring one letter-sized double-sided page of notes.

Practice Midterm
Solutions to the Practice Midterm

Midterm
Midterm Solutions

Homework Assignments

Homework Advice

Submission Instructions and Policies

Regrade Policy

Recitations

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.

Exercises

We post here the exercises planned for the recitations.

Resources

Textbooks

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/Addison-Wesley
Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, Algorithms, McGraw-Hill Education

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.

Examples: homework1.tex homework2.tex homework3.tex homework4.tex homework5.tex homework6.tex homework7.tex