CS 161: Design and Analysis of Algorithms – Spring 2015

Instructor: Virginia Vassilevska Williams
Time: Mondays and Wednesdays 11:00a-12:15p
Location: NVIDIA Auditorium

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. Introduction to network flows and graph matchings.

Prerequisites:

Before taking CS 161, it is important that you complete CS 103 and CS 109/STATS 116, or the equivalents.
In particular, you should be comfortable with proofs, discrete mathematics, basic graph and set theory, and introductory probability theory.

Useful Information:
Exams:

There will be two exams for the course: one midterm and one final.
The midterm will be on Monday, May 4th at 7:00p. The final exam will be on Friday, June 5 from 8:30a, as specified by the registrar.
Locations: TBD
There will NOT be an alternate final exam, so plan accordingly.

Homework:

Before working on the homework, please read the homework policy.


Lectures:
  1. Introduction, Why are you here? [pdf]