CS 161: Design and Analysis of Algorithms (Winter 2017)

[ 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: 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
Luna Frank-Fischer [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 Kawawa-Beaudan, 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

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
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.3-4.5
Dasgupta-Papadimitriou-Vazirani 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.1-2
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, Dijkstra's Algorithm
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, Bellman-Ford Algorithm
Read: Ch. 24.1, 24.3
Notes (draft)
2/17
Homework 5 due
2/20
President's Day (no class)
2/22
MIDTERM
2/27
Dynamic Programming: Floyd-Warshall, 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.1-3
3/15
Whats Next?
3/17
Homework 7 due
3/20
Final Exam, 3:30pm-6:30pm

Midterm and Final

Midterm: Wednesday, February 22, in class, 3:00 pm - 4:20 pm
Final: Monday, March 20, 3:30-6:30pm.

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

Homework Assignments

Homework Advice
-
  • Homework 1 (released 1/13, due 1/20 at 3pm). [ pdf ] [raw LaTex file]

    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