Course Syllabus

This version of the syllabus reflects material taught in Fall 2011. The outline for different years is mostly similar.

The study of algorithms is, at one level, the study of techniques driven by rigorous formal analysis: divide and conquer, greedy algorithms, recursion, O() notation and the like. At another level, algorithms are about abstraction: what is the core computational structure underlying a problem, and how might we unlock it ?

In this course, we will study algorithms at the level of techniques, and at the level of structure. Formalization, a key step in the practice of using algorithms, will play an important role in this class.

Textbook

There will be no official textbook for this class. Reading material for the lectures will be drawn mostly from Jeff Erickson’s collection of lecture notes in algorithms. A valuable textbook reference is

• Algorithm Design, by Kleinberg and Tardos. 

Other references that you might find useful are

• Algorithms, by Dasgupta, Papadimitriou and Vazirani
• An Introduction to Algorithms, by Cormen. Leiserson, Rivest and Stein. 

Lecture Outline

• Basic Techniques:
• Lecture 1: Divide and Conquer I: the master theorem, examples, and the prune-and-search paradigm. Please read these notes on recurrences and the master theorem, and these notes on recursion and divide-and-conquer.
• Additional material: The Karatsuba Algorithm
• More additional material: Extra notes on recurrrences, including a discussion of how to use the annihilator method for analyzing recurrences. It’s a very handy approach for recurrences involving exponential time behavior.
  
• Lecture 2: Divide and Conquer II: Fast Fourier Transforms.
• Additional material: A menagerie of methods for polynomial multplication.
• Lecture 3: Dynamic programming: “think top-down, solve bottom-up”. Fibonacci sequences, largest common subsequence
• Lecture 4: Dynamic programming, continued: Edit distance, independent sets on graphs.
• Lecture 5: Greedy algorithms: Examples, proof techniques
• Lecture 6: Matroids – an algebraic framework for when greedy algorithms work.
• If you’re interested in optional further reading, there’s a wealth of material on matroids, and even a complete characterizations of the kinds of structures on which greedy algorithms are optimal. Matroids were first connected to greedy structured by Edmonds (also famous for proposing the notion of polynomial time as efficient), and Korte and Lovasz developed the notion of a greedoid as a further generalization. The culmination of this effort came in 1993, with a paper by Helman, Moret and Shapiro that completely characterized the nature of structures (in short, they’re “matroid-like”) that admit optimal greedy algorithms.
• Network flows:
• Lecture 7: The max-flow problem: the Ford-Fulkerson algorithm and min-cut-max-flow. Here are my slides from today’s lecture.
• Lecture 8: Flow algorithms
• Lecture 9: Applications.
• Lecture 10: Matchings and extensions (but not min-cost flow)
• Randomized Algorithms
• Lecture 11: What is a randomized algorithm ? Randomized Quicksort.
• Lecture 12: Treaps and Skip lists
• Lecture 13: Hashing
• Lecture 14: Cuckoo Hashing.  Coupon collectors, balls and bins, and tail bounds for algorithms. These notes are also useful.
• Complexity Theory:
• Lecture 15: Lower bounds and decision trees.
• Lecture 16: Problems, Languages, P and NP.
• Lecture 17: Reductions among problems (same notes as above)
• Lecture 18: Fun with reductions. Yes, fun !
• Approximation Algorithm Design: Beyond NP-hardness
• Lecture 19: What is an approximation algorithm ? Examples.
• Lecture 20: Approximations continued (using above notes)
• Lecture 21: More approximations (using above notes): PTASs and strong NP-completeness
• Lecture 22: Linear Programming
• Big Data: strategies for managing large data sets

Material in this module is drawn from lectures in this class at Stanford. Please visit the page for related reading and source papers.

• Lecture 23: Models for computing with large data. Distinct element estimation
• Lecture 24: Fingerprints, shingling and estimating set similarity
• Lecture 25: Bloom filters
• Special topics: audience choice !

What we cover next is upto you ! In the past I’ve covered quantum computing, algorithmic game theory, how to steal elections, zero knowledge proofs (or how to convince someone your proof is correct without telling them the proof), computational origami, and more ! You decide, I teach. Email me with your thoughts.

• Lecture 26: Pancake Flipping. And hot off the griddle, Pancake Flipping is NP-hard !
• Lecture 27: Quantum Computing
• Lecture 28: Computational Origami. Geometric Folding Algorithms, the Peaucellier’s linkage,  and a movie,  unfolding a polygon, and the story of the five-point star. More on fold-and-cut problems and map folding.
• Lecture 28: Algorithmic Game Theory

 

Policies

Please see the homework policy page.

Homework/Projects

There will be between 5-7 assignments, which will include both “pen-and-paper” questions and at least one programming question. In addition, if you are registered for CS 6150, you will also be expected to do a semester-long project. More details on the nature of the project will be provided shortly.

Submitting homeworks

All homeworks and project reports will be turned in online as PDF. You will find that LaTeX will be the best way for you to write the homeworks (especially with the amount of math involved). LaTeX is available on all CADE machines. A not-so-short guide to LaTeX is available, and tex.stackexchange.com is another valuable resource.