The Most Important Algorithms
risc.jku.at
The Most Important Algorithms
1–10 of 50 posts
Re: The Most Important Algorithms
#2Thanks for posting this, I have a bunch of algorithms to learn. :)
Re: The Most Important Algorithms
#3Thanks for posting this, I have a bunch of algorithms to learn. :)
Instead of going by a checklist, try to approach it by domain: Searching; Sorting; floating point, integer computing, and bit-manipulation; numerical analysis and computation; DSP; optimization and dynamic-programming; information theoretic stuff like compression and encryption; graph theoretic algorithms; symbolic algebra; geometric and hierarchic data structures and algorithms; statistical, probabilistic and inferential algorithms; string and sequence processing along with linguistic techniques, etc.
The whole point of big encyclopedic texts like Cormen et al. is to wet your feet and give you a broad exposure to various techniques. That way you have a small idea on what you want to use next, and you know which domain to focus your research.
My one recommendation is to ditch programming languages with huge boot-times when playing with algorithms. You want something that you can interact with live and see results; in that regard, even a symbolic algebra system like Maxima would be better than C, C++ and Java. Lisp and Python would be ideal for most algorithms.
Re: The Most Important Algorithms
#4quite a lot of structure amongst these algorithms that the list misses out:
- dynamic programming comes from solving Bellman's equation and Q-learning is an approximate means of doing dynamic programming.
- It's possible to do beam a* search, where beam search, a* search, and best-first (greedy) search are special cases.
- in the continuous domain, greedy search is essentially gradient ascent.
- you can use discrete differentiation to find the gradients for gradient ascent (actually, i would replace the first order method suggestion of this list with newton-raphson or some quasi-newton raphson method like BFGS).
- EM ties some bits together.
- if you replace the max of the viterbi algorithm with a summation, then you get the sum-product algorithm which is essential in the E step of EM. if you use viterbi instead of sum-product, you get something known as zero-temperature EM, which is an approximate form of EM
- the M step of EM is typically just gradient ascent!
- you can use max flow to do a similar thing to viterbi on certain graphs
and so on...
Re: The Most Important Algorithms
#5Thanks for posting this, I have a bunch of algorithms to learn. :)
Instead of going by a checklist, try to approach it by domain: Searching; Sorting; floating point, integer computing, and bit-manipulation; numerical analysis and computation; DSP; optimization and dynamic-programming; information theoretic stuff like compression and encryption; graph theoretic algorithms; symbolic algebra; geometric and hierarchic data structures and algorithms; statistical, probabilistic and infere…
I am going through Cormen et al. with the objective of getting my feet wet but the whole process is painfully slow. I thought it would be nice to have at least some familiarity on the widely used algorithms across the globe. However, you are right on ditching programming languages with huge boot times. I am happily trying out my algorithms in Python.
Re: The Most Important Algorithms
#6Thanks for posting this, I have a bunch of algorithms to learn. :)
Instead of going by a checklist, try to approach it by domain: Searching; Sorting; floating point, integer computing, and bit-manipulation; numerical analysis and computation; DSP; optimization and dynamic-programming; information theoretic stuff like compression and encryption; graph theoretic algorithms; symbolic algebra; geometric and hierarchic data structures and algorithms; statistical, probabilistic and infere…
That's my usual approach, so the algorithms outside the domains I've studied were unfamiliar. Would you be able to recommend books in graph theory, and statistics/probability? I'd be much obliged.
Re: The Most Important Algorithms
#7quite a lot of structure amongst these algorithms that the list misses out: - dynamic programming comes from solving Bellman's equation and Q-learning is an approximate means of doing dynamic programming. - It's possible to do beam a* search, where beam search, a* search, and best-first (greedy) search are special cases. - in the continuous domain, greedy search is essentially gradient ascent. - you can use discrete…
I think the dynamic programming meant here is more general. They mean saving results of a recursively formulated algorithm in a table so that you don't have to recompute them. This can be used for example for finding longest common subsequences, but it is much more general.
Can you elaborate on the general search procedure?
Is there a good resource that ties algorithms together like you've done here, but less concise?
Re: The Most Important Algorithms
#8Earlier quoted context omitted.
Instead of going by a checklist, try to approach it by domain: Searching; Sorting; floating point, integer computing, and bit-manipulation; numerical analysis and computation; DSP; optimization and dynamic-programming; information theoretic stuff like compression and encryption; graph theoretic algorithms; symbolic algebra; geometric and hierarchic data structures and algorithms; statistical, probabilistic and infere…
That's my usual approach, so the algorithms outside the domains I've studied were unfamiliar. Would you be able to recommend books in graph theory, and statistics/probability? I'd be much obliged.
this is a splendid book that covers the most probabilistic/statistical algorithms:
http://www.inference.phy.cam.ac.uk/mackay/itila/
Re: The Most Important Algorithms
#9quite a lot of structure amongst these algorithms that the list misses out: - dynamic programming comes from solving Bellman's equation and Q-learning is an approximate means of doing dynamic programming. - It's possible to do beam a* search, where beam search, a* search, and best-first (greedy) search are special cases. - in the continuous domain, greedy search is essentially gradient ascent. - you can use discrete…
I think the dynamic programming meant here is more general. They mean saving results of a recursively formulated algorithm in a table so that you don't have to recompute them. This can be used for example for finding longest common subsequences, but it is much more general. Can you elaborate on the general search procedure? Is there a good resource that ties algorithms together like you've done here, but less concise…
they do mean dynamic programming in a more general sense: but dynamic programming was invented originally to solve Bellman's equation. it turns out many other problems have a similar structure which is quite surprising! before bellman's seminal work in 1940s, it wasn't known how to efficiently these problems. indeed, you can often do something like Q-learning for finding approximate solutions to dynamic programming problems even faster.
the general search procedure is just A* search but with the beam search pruning each time you expand the fringe of exploration.
i don't know a good source, i picked this up from a bunch of courses/research.
Re: The Most Important Algorithms
#10Earlier quoted context omitted.
I think the dynamic programming meant here is more general. They mean saving results of a recursively formulated algorithm in a table so that you don't have to recompute them. This can be used for example for finding longest common subsequences, but it is much more general. Can you elaborate on the general search procedure? Is there a good resource that ties algorithms together like you've done here, but less concise…
they do mean dynamic programming in a more general sense: but dynamic programming was invented originally to solve Bellman's equation. it turns out many other problems have a similar structure which is quite surprising! before bellman's seminal work in 1940s, it wasn't known how to efficiently these problems. indeed, you can often do something like Q-learning for finding approximate solutions to dynamic programming p…
Thanks! You should consider writing an article about this :)