Which are the 10 algorithms every computer science student must implement at least once in life?

0
Mudassir Ali
Feb 10, 2020 05:58 AM 0 Answers
Member Since Dec 2019
Subscribed Subscribe Not subscribe
Flag(0)
Mudassir Ali
- Feb 10, 2020 05:58 AM

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.

Reply on This
Replying as Submit
0 Subscribers
Submit Answer
Please login to submit answer.
0 Answers