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

[ Course Schedule | Homework Assignments | 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
9/30
Homework 1 released
10/3
Integer Multiplication, Solving Recurrences
Read: Ch. 4.3-4.5
10/5
Median and Selection
Read: Ch. 9
10/7
Homework 1 due
Homework 2 released
10/10
Quicksort, Probability and Randomized Algorithms
Read: Ch. 7, 5
10/12
Sorting Lower Bounds, Counting Sort
Read: Ch. 8.1-2
10/14
Homework 2 due
Homework 3 released
10/17
Binary Search Trees
Read: Ch. 12
10/19
Hashing
Read: Ch. 11
10/21
Homework 3 due
Homework 4 released
10/24
Open Addressing, Graphs, DFS
Read: Ch. 22
10/26
DFS, Topological Sort
Read: Ch. 24, 6
10/28
Homework 4 due
10/31
Midterm
11/2
BFS, Shortest Paths, Dijkstra's Algorithm
Read: Ch. 24.3
11/4
Homework 5 released
11/7
Dijkstra's Runtime, Amortized Analysis for Binary Counter, Dynamic Programming: Bellman-Ford
Read: 24.1, 24.3
11/9
Dynamic Programming: Floyd-Warshall, Longest Common Subsequence,
Read: Ch. 25.2, 15.4
11/11
Homework 5 due
Homework 6 released
11/14
Greedy Algorithms: Activity Selection
Min Spanning Tree (MST): Prim's and Kruskal's Algorithms
Read: Ch. 16, 23
11/16
Finish MSTs, Minimum Cut: Karger's algorithm
Read: Kleinberg-Tardos Ch. 13.2: [pdf]
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 Dates

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

Homework Assignments

Submission Instructions and Policies

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