Which are the Algorithms every Computer Student must IMPLEMENT at least once in life???

                                No of Words: 722
                               No of back-links: 17
                              CREDITS:> Soham Mehta  

In my daily work [Coding Interview Bootcamp], we come across a lot of neat CS algorithms.

A good place to answer this question would be to see an article that Mathematician Barry Arthur Cipra wrote a few years ago, based on a survey of several practitioners: Top 10 Algorithms in 20th Century. That has an excellent list.

However, I guess what you’re looking for, are CS algorithms that are ubiquitous in everyday things. Algorithms so pervasive in things we pick up every day, yet a normal person doesn’t know they exist, and we didn’t even do them in our CS courses!

Why not implement them, just for fun? Just for gratitude?

I’m going to list a few of those below. Not “top 10”, or “best 10”, but “tantalizing 10”, or just “reasonable 10”. I’m also going to avoid the obvious ones e.g. Binary searches and hash tables. And I’ll avoid some super esoteric ones, like say Krylov.

Some of these are so within reach, that they even form actual coding interview questions! Hope you find them as much fun as I did.

In no particular order:

• Plagiarism detection, using Rabin Karp String matching
• String matching algorithms are pervasive in software. One particularly fun one is Rabin Karp, which is used in Plagiarism detection. As a student in CS (or in any major), plagiarism detection should be of interest ;-)
• Rabin Karp is relatively easy to implement. See this: Rabin–Karp algorithm - Wikipedia
• Rabin Karp has also inspired a string matching routine in Zlib (one of the most popular un/zip libraries ever). See this, directly into the source code.
• Matching users to servers, using Gayle-Shapely Algorithm for Stable Marriage problem
• This is a beautiful algorithm for fair matching. Simple, elegant and effective. In its core form, it’s also straightforward to implement. Has numerous applications. See: Stable marriage problem - Wikipedia

• A toy implementation of Viterbi algorithm
• Ubiquitous in cell phone technology, and many other applications, the Viterbi algorithm is a Dynamic Programming based algorithm that finds the most likely sequence of states.
• See this toy implementation: http://homepages.ulb.ac.be/~dgonze/TEACHING/viterbi.pdf
• Music Search using Fast Fourier Transforms (FFT)
• Music recognition is done by converting it into the frequency domain using FFT. FFT has implementations in the number of languages. See this article for a great start: Shazam It! Music Recognition Algorithms, Fingerprinting, and Processing.
• Implement the RSA algorithm
• SSL transport is the bane of safe existence on the Internet these days. One of the most well-known algorithms insecure transport is RSA, named by the first initials of its inventors.
• Implementing RSA is fun and instructive e.g. C code to implement RSA Algorithm(Encryption and Decryption)
• Safe Browsing (or similar) using Bloom filters
• Bloom filters found very rare usage until the world got more online and we hit scale. But these days, we see new applications very frequently.
• Chrome browser uses Bloom filters to make a preliminary decision on safe browsing. See some novel applications here.
• Implement an LALR parser
• As a CS student, you may have already implemented it as part of your compiler’s class. But if not, then you should. LALR parsing makes syntactic sense of source code, whichever language you use
• Many implementations of LALR exist. e.g. Where can I find a _simple_, easy to understand the implementation of an LR(1) parser generator?
• Also, use YACC to understand LALR parsing better.
• Treemap using Red-Black Trees!
• RB Trees are not algorithms, but they are famed enough, that no discussion of tantalizing DS/Algorithms is complete without discussing them.
• The smoothest way to see/implement RB Trees is to look at Treemap implementation in Java.
• Circle Drawing using Bresenham’s algorithm
• Ever wondered, how circles are drawn on the screen, with minimal jaggedness (aliasing)? Bresenham’s elegant algorithm is at play here. See a version here: Circle Generation Algorithm.
• A refreshing use of a similar algorithm is to make properly sized tabs in Chrome. Something we see almost every day. Such hidden gems!
• See here for some more uses of it: Bresenham
• Implement PageRank

• Can’t miss this. This transformed our lives in ways we never thought possible. Get started here: Pagerank Explained Correctly with Examples

As you’ll see, the most useful algorithms are usually not the hardest ones. They are often the most straightforward ones, ones that are easily understood and thus move the world forward.

I hope you will enjoy them.