5 important algorithms everyone should know

1. Merge Sort O(nlogn) (where n is the input size)

Of course we need to include a sorting algorithm in this list, but why Merge Sort? Why not any of the other comparison based sorting algorithms all of which run in O(nlogn)? The reason is that Merge Sort is probably the most simplest implementation of a “divide and conquer” algorithm out there. The Merge Sort recurrence is also very common in other problems, so you can’t really avoid it. The simplicity is very attractive, it is in my opinion far easier to teach a novice Merge Sort rather than Quick Sort or any other contemporaries.

2. Dijkstra’s Algorithm -O(|E|+|V|log|V|) (where E = set of edges and V = set of vertices with a fibonacci heap)

Dijkstra’s Algorithm is used to solve the “shortest path” path problem on a graph without negative weights. The number of applications where such a solution is needed is endless. No matter if your dealing with complex network routing or simply trying to navigate to a desired destination the solution is the same. With the constant evolution of the internet I can only see Dijkstra’s Algorithm becoming more and more important.

3. Breadth-First-Search/ Depth-First-Search O(|E|+|V|) (where E = set of edges and V = set of vertices)

Very simple with numberless applications. These two algorithms are used to solve many standard graph related problems very efficiently. Some of the most common uses are:

  • connectedness testing
  • shortest path(unweighted)
  • bipartite testing
  • topological sort
  • planarity testing
  • maze solving

4. Fast Fourier Transformation O(nlogn) (where n is the input size)

The FFT is an efficient algorithm for computing a discrete Fourier transformation and its inverse. This is invaluable to data compression, whether through sound(mp3) or image(jpeg) we have all used the benefits of this algorithm. Unfortunately not enough people understand how it works, so study up on your primitive roots of unity, take some time to learn it and you will see the true beauty of this algorithm.

5. RSA O(k^2) – public key operations, O(k^3) – private key operations, O(k^4) – key generation (where k is the number of bits in the modulus)

RSA was a great step for public key encryption and been built into many security protocols. RSA is still very secure with sufficiently long keys. With the advent of quantum computers, factoring becomes a polynomial time task so RSA begins to fall apart, but it is still very relevant and a great breakthrough none the less.

Advertisements

~ by underaglassmoon on August 30, 2010.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: