Computer Science 125: Algorithms & Complexity

Additional Readings

• Sorting
  • Sorting benchmark page
  • Wikipedia pages on Van Emde Boas trees , Bucket sort , Counting sort .
• Greedy
  • Wikipedia pages on Cayley's Formula and Kirchhoff's Theorem on the number of minimum spanning trees in a graph.
• Divide and conquer
  • Wikipedia pages on Strassen's algorithm , Fast Fourier transform , and Schonage-Strassen integer multiplication
  • Paper by Virginia Williams on the matrix multiplication coefficient, getting it to below 2.372873.
  • Find out about recent progress on sparse FFT and its many applications.
• Dynamic Programming
  • Dynamic Programming on Wikipedia
  • Dynamic Programming as Shortest Paths , possibly the way we should be teaching it?
  • Top ten DP interview questions , according to Quora
  • Survey on Dynamic Programming and Vision
• Machine Models
  • Find out more about the Transdichotomous RAM model
  • Check out the Complexity Zoo
  • Pseudo-polynomial time, explained
• Shortest paths
  • A whole summer school on shortest paths -- lots of great slides. (See, for example, this set of slides covering many shortest path algorithms.)
  • A lot of work on shortest paths these days are on "road networks". Here's a sample paper of this type.
  • You may also naturally have "stochastic" versions of the problem in real life. Here's an old result in that space.
• Linear programming
  • Karmarkar's algorithm and the ellipsoid method are ways to solve LPs in provable polynomial time that we did not discuss in class.
  • Background on the simplex algorithm Some notes on worst case behaviors of simplex.
  • List of optimization software.
• Network flow
  • A recent survey on network flow algorithms , with pointers to some of the latest and greatest results.