11
$\begingroup$

I am looking for resources (preferably a handbook) on advanced topics in algorithms (topics beyond what is covered in algorithms textbooks like CLRS and DPV).

The type of material that can be used for teaching a topics in algorithms course like Erik Demaine and David Karger's Advanced Algorithms course.

Resources that would give an overview of the field (like a handbook) are preferable, but more focused resources like Vijay Vazirani's "Approximation Algorithms" book are also fine.

$\endgroup$
  • $\begingroup$ This is similar to my previous question about data structures: handbook of advanced data strctures. I would like to use them as pointers for my students to learn about more advanced topics in algorithms. Resources which are available online for students are preferable. $\endgroup$ – Kaveh Nov 3 '13 at 22:42
  • $\begingroup$ Search the MIT archives. $\endgroup$ – Tommy Nov 6 '13 at 5:05
  • 1
    $\begingroup$ Johan Håstad (also) has lecture notes on advanced algorithms: nada.kth.se/~johanh/algnotes.pdf $\endgroup$ – Huck Bennett Dec 9 '13 at 17:26
6
$\begingroup$

The Design of Approximation Algorithms by Williamson & Shmoys (http://www.designofapproxalgs.com/) is a great book for many approximation methods such as greedy algorithms, semidefinite programming, etc. Also, it covers some topics within complexity that are closely related to approximation algorithms (inapproximability, Unique Games-based hardness of MAX-CUT).

$\endgroup$
5
$\begingroup$

You may find of interest the following recent handbooks. The range of topics covered goes well beyond CLRS, and the material is well suited for graduate and Ph.D. students, even though you may choose a few selected topics for advanced undergraduate students.

Algorithms and Theory of Computation Handbook Second Edition (Special Topics and Techniques)

Handbook of Applied Algorithms Solving Scientific, Engineering and Practical problems

Handbook of Approximation Algorithms and Metaheuristics 

$\endgroup$
  • $\begingroup$ review & table of contents of the 1st ref Atallah/Blanton $\endgroup$ – vzn Nov 5 '13 at 18:03
4
$\begingroup$

I rather liked "Algorithmics for Hard Problems" by Juraj Hromkovic

$\endgroup$
4
$\begingroup$

Have look at the Encyclopedia of Algorithms by Kao (Editor). It contains over 500 entries and many of them contain advanced algorithms.

$\endgroup$
4
$\begingroup$

Computational Geometry: Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Cheong. Computational Geometry: Algorithms and Applications; David Mount's Course Notes.

Randomized Algorithms: Motwani and Raghavan. Randomized Algorithms; Excellent Notes by James Aspnes; Mitzenmacher and Upfal. Probability and Computing.

Network Flows: Ahuja, Magnanti, and Orlin. Network Flows.

Approximation Algorithms: Dorit Hochbaum. Approximation Algorithms for NP-Hard Problems. 

$\endgroup$
  • 1
    $\begingroup$ Since there might not be a single "Advanced Algorithms Handbook", a community wiki answer along these lines (by advanced algorithms topic) would be nice. $\endgroup$ – Huck Bennett Nov 5 '13 at 19:40
  • $\begingroup$ +1 for Ahuja, et. al. Great book -- unfortunately, it doesn't cover many of the recent results such as Orlin's $O(mn)$-time algorithm and Madry's algorithm that solves Laplacians for electrical flows. $\endgroup$ – rahulmehta95 Nov 10 '13 at 18:57
0
$\begingroup$

not exactly what is desired yet similar to your example, consider CS G399: Gems of Theoretical Computer Science; Spring 2009 lecture notes by Viola. its more a proof-centric perspective however most are essentially advanced algorithms in key frontier research areas. (also note lower bounds proofs can be regarded as compression algorithms.)

This course covers some of the most exciting and recent progress in theoretical computer science. It presents state-of-the-art results on active research areas, and teaches related proof techniques. A tentative list of topics includes:

  • Lower bounds for constant-depth circuits.
  • The Nisan-Wigderson pseudorandom generator.
  • Cryptography in constant parallel time.
  • The complexity of Nash equilibria.
  • Undirected connectivity in logarithmic space (SL = L).
  • Communication complexity.
  • Primes is in P.
  • Fast matrix multiplication.
$\endgroup$
  • 2
    $\begingroup$ nice course, but much wider than what the OP was asking $\endgroup$ – Alessandro Cosentino Nov 6 '13 at 3:43
0
$\begingroup$

this ref is recommended by Lance Fortnow (on his blog).

Jan van Leeuwen, editor. Handbook of Theoretical Computer Science, volume A: Algorithms and Complexity. MIT Press, 1994.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.