#  Computer Science 125: Algorithms & Complexity 

 



## **Additional Readings**

- Sorting
    - [Sorting benchmark page](http://sortbenchmark.org/)
    - Wikipedia pages on [Van Emde Boas trees ](https://en.wikipedia.org/wiki/Van_Emde_Boas_tree), [Bucket sort ](https://en.wikipedia.org/wiki/Bucket_sort), [Counting sort ](https://en.wikipedia.org/wiki/Counting_sort).
- Greedy
    - Wikipedia pages on [Cayley's Formula ](https://en.wikipedia.org/wiki/Cayley's_formula)and [Kirchhoff's Theorem ](https://en.wikipedia.org/wiki/Kirchhoff's_theorem)on the number of minimum spanning trees in a graph.
- Divide and conquer
    - Wikipedia pages on [Strassen's algorithm ](https://en.wikipedia.org/wiki/Strassen_algorithm), [Fast Fourier transform ](https://en.wikipedia.org/wiki/Fast_Fourier_transform), and [Schonage-Strassen integer multiplication](https://en.wikipedia.org/wiki/Schonhage-Strassen_algorithm)
    - [Paper by Virginia Williams ](http://theory.stanford.edu/~virgi/matrixmult-f.pdf)on the matrix multiplication coefficient, getting it to below 2.372873.
    - Find out about recent progress on [sparse FFT ](http://groups.csail.mit.edu/netmit/sFFT/)and its many applications.
- Dynamic Programming
    - [Dynamic Programming on Wikipedia](https://en.wikipedia.org/wiki/Dynamic_programming)
    - [Dynamic Programming as Shortest Paths ](http://matwbn.icm.edu.pl/ksiazki/cc/cc35/cc3536.pdf), possibly the way we should be teaching it?
    - [Top ten DP interview questions ](https://www.quora.com/What-are-the-top-10-most-popular-dynamic-programming-problems-among-interviewers), according to Quora
    - [Survey on Dynamic Programming and Vision](http://www.cs.cornell.edu/~rdz/Papers/FZ-survey.pdf)
- Machine Models
    - Find out more about the [Transdichotomous RAM model](https://en.wikipedia.org/wiki/Transdichotomous_model)
    - Check out the [Complexity Zoo](https://complexityzoo.uwaterloo.ca/Complexity_Zoo)
    - [Pseudo-polynomial time, explained](https://en.wikipedia.org/wiki/Pseudo-polynomial_time)
- Shortest paths
    - A [whole summer school ](http://www.diku.dk/PATH05/program.html)on shortest paths -- lots of great slides. (See, for example, this [set of slides ](http://www.diku.dk/PATH05/GoldbergSlides.pdf)covering many shortest path algorithms.)
    - A lot of work on shortest paths these days are on "road networks". Here's [a sample paper ](http://arxiv.org/pdf/1201.6564.pdf)of this type.
    - You may also naturally have "stochastic" versions of the problem in real life. Here's [an old result ](http://math.mit.edu/~kelner/Publications/Docs/ESA06A_nikolova_final.pdf)in that space.
- Linear programming
    - [Karmarkar's algorithm](https://en.wikipedia.org/wiki/Karmarkar%27s_algorithm) and the [ellipsoid method ](https://en.wikipedia.org/wiki/Ellipsoid_method)are ways to solve LPs in provable polynomial time that we did not discuss in class.
    - Background on the [simplex algorithm ](https://en.wikipedia.org/wiki/Simplex_algorithm)Some notes on [worst case behaviors of simplex.](http://disi.unal.edu.co/~gjhernandezp/aa/Simplex/What%20is%20the%20Worst%20Case%20Behavior%20of%20the%20Simplex%20Algorithm.pdf)
    - [List of optimization software.](https://en.wikipedia.org/wiki/List_of_optimization_software)
- Network flow
    - A [recent survey on network flow algorithms ](https://courses.cs.ut.ee/MTAT.03.238/2014_fall/uploads/Main/maxflow.pdf), with pointers to some of the latest and greatest results.