12
$\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.

Improve this question
$\endgroup$
3
  • $\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
    Commented Nov 3, 2013 at 22:42
  • $\begingroup$ Search the MIT archives. $\endgroup$
    – Tommy
    Commented Nov 6, 2013 at 5:05
  • 1
    $\begingroup$ Johan Håstad (also) has lecture notes on advanced algorithms: nada.kth.se/~johanh/algnotes.pdf $\endgroup$
    – Huck Bennett
    Commented Dec 9, 2013 at 17:26

7 Answers 7

Reset to default
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).

Improve this answer
$\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 

Improve this answer
$\endgroup$
1
  • $\begingroup$ review & table of contents of the 1st ref Atallah/Blanton $\endgroup$
    – vzn
    Commented Nov 5, 2013 at 18:03
4
$\begingroup$

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

Improve this answer
$\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.

Improve this answer
$\endgroup$
1
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. 

Improve this answer
$\endgroup$
2
  • 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
    Commented Nov 5, 2013 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
    Commented Nov 10, 2013 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.
Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ nice course, but much wider than what the OP was asking $\endgroup$
    – Alessandro Cosentino
    Commented Nov 6, 2013 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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