fjaos'jfodsajfodsjaofjdsa'fafjjasdfsdafPlease refresh this page to receive new updates.

Ask Question
Read
Answer
Notifications
Jinai Arh
Jinai
Students
Algorithms
Computer Science Education
Computer Programming
Which are the 10 algorithms every computer science student must implement at least once in life?
Answer
Request
Follow4k
Comment
Share80Downvote
Promoted by Loggly
Reveal what matters in your log data.
Live Webinar, April 20th:Collect and analyze data generated by AWS services and applications with Loggly.
Sign Up at pages.awscloud.com
37 Answers
Soham Mehta
Soham Mehta, InterviewKickstart.com. We do this for a living
Updated Jan 12 · Upvoted by Dan Zhang, Computer Engineering PhD student at UT Austin; interned at Microsoft and Apple and Abhishek Dwivedi, MTech in Computer Science from NMiMS
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 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 pickup 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”. What I mean is, that there are many more than 10 that I list here.

I’m going to avoid the obvious ones e.g. Binary searches and hash tables. I’ll also avoid some super esoteric ones, like say Krylov.

I’ll bias towards ones that are very pervasive in everyday things, are more easily implement-able, you have likely heard of them as a CS student, yet it’s unlikely that you have done them in a CS course. Most importantly, all of these run right under your nose, every day.

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.

Without further ado, 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, 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/~dgon...
Music Search using Fast Fourier Transforms (FFT)
Music recognition is done by converting it into frequency domain using FFT. FFT has implementations in number of languages. See this article for a great start: Shazam It! Music Recognition Algorithms, Fingerprinting, and Processing.
Implement RSA algorithm
SSL transport, is the bane of safe existence on Internet these days. One of the most well-known algorithms in secure 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 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 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!
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, 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.
87.4k Views · View Upvotes
Upvote1.2kDownvoteComments8
Share
Promoted by CUBA Platform
Open source Java Web Framework
Visual design, code generation, enterprise components out of the box.
Download at cuba-platform.com
Peteris Erins
Peteris Erins, Product Manager at QuantumBlack, previously at Twitter, Google
Written Jan 26, 2013 · Upvoted by Siddarth Sampangi, UCSD B.S. in CS '14; UMass Amherst M.S. in CS '16 and Igor Markov, EECS Professor at Michigan - currently at Google
Coming from an intensive programming contest background, having read Introduction to Algorithms, etc., but then moving on to doing real-life projects, I find that some of the more interesting and powerful algorithms in a problem solving setting find little use in the industry.

I'm thus going to present algorithms that carry over to engineering, not just research and TopCoder. Another goal was for these algorithms to be useful and widely applicable hammers in their own right, not just as an idea. The benefits of most "algorithms" will be hard to explain them to someone who has not yet been introduced to them, but I tried my best of giving a hint for their role.

Naive Bayes. Classification is a natural first step to machine learning and the Naive Bayes classifier combines that with the trending concept of Bayesian inference. Despite its simplicity, can address key problems like spam classification.
Map-Reduce. A simple and visual way of leveraging multiple computers to solve a single task. More on its different uses here: MapReduce Patterns, Algorithms, and Use Cases.
Hill Climbing. Introduces optimization over a non-exhaustible domain and leads to a whole array of powerful methods like gradient-descent, simulated annealing. Optimization allows us to do decision making, it's important.
Binary search. Introduces logarithmic complexity and how the structure of data can change complexity characteristics of operations.
Exponentiation (powers) by halving. Great example of a recursive attack. You would be surprised how many problems can be described as exponentiation (for an associative operation) of something: a number, a matrix and more. Again it's magical that associativity of an operation allows you to turn a linear factor into a logarithmic one.
Floyd-Warshall. Graphs as matrices, shortest paths, negative cycles, dynamic programming in five lines of code.
Inductive inference. Inductive inference. This idea on how to find programs that do certain things without having a human write them I believe is the key to the future of AI and simulating and understanding the human mind.
Markov Chain Monte Carlo. Approximate integral, expected value computation based on a conditional specification of the probability distribution. This gives us a general way of doing data analysis.
Shor's algorithm. Non-trvial example of a quantum algorithm that shows a significant complexity improvement. Reveals how quantum computing works.
PageRank. How to iteratively solve for tightly related variables to extract metrics on graphs.
138.4k Views · View Upvotes
Upvote703DownvoteComments8+
Share
Promoted by Shopify
Create Ecommerce Website
Start a 14-day free trial now! Easy setup and free 24/7 support.
Free Trial at shopify.com
Sachin Gupta
Sachin Gupta, Programming for some years now :)
Written Sep 27, 2015
Don't have a list of 10 algorithms, but 7 algorithms that every programmer should know. The first 2 in the list are Sorting and Searching algorithms, which in themselves have many algorithms that should be known, so the list actually goes beyond just 10.

Sorting Algorithms
Searching Algorithms
Hashing
Dynamic Programming
Binary Exponentiation
String matching and parsing
Primality Testing
These topics have been taken from this blog post (Top 7 algorithms and DS every programmer should know) that covers all of these topics in detail.
29.6k Views · View Upvotes
Upvote137DownvoteComment
Share
Ron Reiter
Ron Reiter, 20 years a computer geek
Written May 21, 2016
Aside for the must’s (BFS, DFS, sorting, hashing, binary search and tree traversal, divide and conquer, and basic data structures which are not exactly algorithms per se) I would like to suggest a few more from a practical perspective. Not exactly the “top 10” but very useful, practical and simple ones.

Maze creation algorithms - this would give a great context to where to actually use the DFS, BFS, Dijkstra and A* algorithms. And it’s fun. The maze creation algorithm itself is not useful, but it’s a great playground for graph solving algorithms, which are extremely useful in the real world. A* is also nice because all strategy games we play today use it to plan out the shortest walking route, so you can try it out on a maze.
Bloom filter - probably one of the most useful algorithms to know that exist in the data structures world. It helps reducing lookup cost. It is important because lookups are usually very common and expensive, so a bloom filter checks if data access is even necessary beforehand. You could stick a bloom filter in just about any data structure. Very easy to code.
Hidden Markov Model - I have used this algorithm at least twice in two different contexts - one for breaking ciphers and another for compression. It can be even used for computer vision applications. It’s very useful when trying to predict probability of the next output of a system given a series of previous outputs. Read more about the Forward Algorithm. It is also extremely easy to code.
Huffman Coding - The simplest form of efficient encoding. Teaches a lot about how data is stored on the computer, and about the theoretical limits of storing data efficiently. Also used in zip, gzip, etc.
RLE Compression - The simplest form of compression out there. Very easy to code.
2D Ray Caster - The simplest form of a 3D first person shooter you could build. This is how games like Wolfenstein 3D and Doom work. It’s useful because it’s extremely simple, and because raycasting is one of the core foundations of computer graphics. It is also extremely easy to code and understand. Requires very basic understanding of trigonometry.
Deterministic & Heuristic game solvers - A very fun exercise for learning how AI works when playing games against the computer. The easiest one would be to write the tic-tac-toe AI, but you could also go and create chess and checkers, and then implement some heuristics to know the next best move. Also useful to understand the infinite complexity of chess and checkers compared to “solved” games such as tic-tac-toe.
FFT (Fast Fourier Transform) - Programming FFT is not something important to learn because it is based on a lot of theoretical background. But using FFT and similar algorithms such as DCT, wavelets, etc. is also very useful to know for analyzing, compressing and modifying sound, images and video. Anything you can think of in signal processing - from changing pitches, auto-tuning, MP3 compression, JPEG compression, video compression, photoshopping, is done by transforming signals from the spatial domain to the frequency domain, and vice versa.
Public-key cryptography - Very powerful algorithms that solve the key issue of eavesdropping. Both RSA (public/private) and Diffie-Hellman (mutual key exchange) are very easy to implement, and provide you with great understanding on how secure information travels in insecure channels today - secure web pages, certificates, SSH and end-to-end encryption are just a few examples. Requires a bit of modulu arithmetics background but still very simple to implement.
Control loop feedback algorithm (PID) - The most basic algorithm for programming actual robots and IoT devices which controls a specific state by receiving feedback from sensors and applying commands to motors to adjust the state. Examples are: thermostats, autonomous cars, computer guided missiles, etc. This is very easy to implement, but it will require a Raspberry Pi and some sensors to try out. The easiest thing to implement would be a robot that follows a straight line or keeps a specific distance from a wall.
12.4k Views · View Upvotes
Upvote73DownvoteComments3
Share
There's more on Quora...
Pick new people and topics to follow and see the best answers on Quora.
Update Your Interests
Related Questions

What are some must have books for current undergraduate computer science students like CLRS?
What proportion of college students take at least some computer science?
As a computer science grad student, what languages must I know?
What are algorithmic problems that every cse student must solve?
What are some amazing computer science algorithms?
What are the top Stack Overflow questions every computer science student must see?
What are some questions related to computer science on Quora that every computer science student should read?
What are the most interesting famous Computer Science algorithms that you made your own implementation for?
What are the artificial intelligence (AI) algorithms that every computer science student must be aware of?
What are some of the computer science undergraduate courses (available online) which a student must take for graduation?
More Related Questions
Question Stats

4,091 Followers
694,415 Views
Last Asked Feb 21
Edits
Top Stories from Your Feed
Read In Feed
Answer written ·
Cooking
 · 23h
As a professional chef, when was the last time you ate ketchup in a meal?
Rik Osborne
Rik Osborne, Gets called "Chef" but is really just a good cook
Written 23h ago
The last time I ordered a fast-food burger and fries.Ketchup isn’t some lowly condiment that professionals look down on. It’s a perfectly good condiment that is suitable for some foods and is unsui...
Read In Feed
Answer written ·
Computer Science
 · Topic you might like · Apr 5
What's something that you should never say to an I.T. person?
Ted Pettit
Ted Pettit
Written Apr 5
The one thing I learned, years ago, from a column that used to be circulated by a guy who was a grouchy computer admin at a university (precursor to an "I.T. person"):Never ever ever say "My passw...
Read In Feed
Answer written ·
Visiting and Travel
 · Mar 3
What should I learn in my 20s that will help me to financially retire at 35 and travel the world for the rest of my life?
Dylin Redling
Dylin Redling, Founder at Retire By 45 (2016-present)
Written Mar 3
I retired at 43, but if I knew in my 20s what I know now, then I could’ve retired at 35. Here are the 6 steps I’ve developed to help young people set themselves up for a successful early retirement:...