Advanced Algorithms
23 essays
Essays
Genetic Algorithm to solve the Knapsack Problem
441 reads • 2022-03-07
The 0/1 Knapsack Problem has a pseudo-polynomial run-time complexity. In this essay, we look at an approximation algorit...
Pseudorandom Number Generation using LFSR
609 reads • 2022-02-21
This essay takes a detailed look into pseudorandom number generation using LFSR, a widely adopted technique to generate ...
Fork Bomb
425 reads • 2021-06-09
In this essay, we explore a simple yet effective DoS attack called Fork Bomb, also called Rabbit Virus. This attack fork...
Fully Persistent Arrays
618 reads • 2021-02-14
Persistent Data Structures allow us to hold multiple versions of a data structure at any given instant of time. This ena...
Persistent Data Structures - An Introduction
1861 reads • 2021-02-07
Persistent Data Structures allow us to hold multiple versions of a data structure at any given instant of time. This ena...
Approximate Count-Distinct using Flajolet Martin Algorithm
3131 reads • 2020-12-06
Measuring distinct elements from a stream of values is one of the most common utilities that finds its application acros...
2Q Cache Management Algorithm
1705 reads • 2020-11-29
LRU is one of the most widely used cache eviction algorithms suffers from a bunch of limitations especially when used fo...
Israeli Queues
7250 reads • 2020-11-22
Israeli Queues are fondly named after a peculiar behavior observed in Israel. This behavior was mimicked to solve a very...
1D Procedural Terrain Generation
1062 reads • 2020-11-16
Terrains are at the heart of every Computer Game - be it Counter-Strike, Age of Empires, or even Minecraft. The virtual ...
Set Similarity using Jaccard Similarity Coefficient and MinHash
1481 reads • 2020-11-08
Set similarity measure finds its application spanning the Computer Science spectrum; some applications being - user segm...
Time Series Smoothing - Making Aberrations Stand Out
499 reads • 2020-11-01
Time Series smoothing algorithms removes short-term irregularities from the plot while preserving long-term trends. But ...
Constant Time LFU
6035 reads • 2020-08-23
The most popular implementation of the LFU Cache Eviction Scheme, using a min-heap, implements all three operations with...
Morris's Algorithm for Approximate Counting
2120 reads • 2020-08-02
Morris' Algorithm counts a large number of events using a very small space O(log log n). The algorithm uses probabilisti...
Slowsort - A Pessimal Sorting Algorithm
6485 reads • 2020-07-26
Slowsort is a pessimal sorting algorithm based on the Multiply and Surrender paradigm. The algorithm is designed to be d...
Phi φ Accrual Failure Detection
478 reads • 2020-07-12
Phi φ Accrual Failure Detection algorithm, unlike conventional algorithms, is an adaptive failure detection algorithm th...
Consistent Hashing
1262 reads • 2020-05-24
Consistent Hashing is one of the most sought after techniques when it comes to designing highly scalable distributed sys...
Fractional Cascading - Speeding up Binary Searches
486 reads • 2020-05-10
The performance of binary search when applied on k lists independently can be improved using bridges and the technique i...
Building Finite State Machines with Python Coroutines
7625 reads • 2020-04-19
The most intuitive way of building and implementing Finite State Machines is by using Python Coroutines and in this arti...
Better Ranking using Bayesian Average
526 reads • 2020-04-12
Ranking a list of movies, products, books or even restaurants is tricky and in this article, we find what works for such...
Inverse Document Frequency
417 reads • 2020-03-06
TF-IDF is extensively used in search engines and in various document classification and clustering techniques. Instead o...
Pseudorandom Number Generation using Cellular Automata - Rule 30
1011 reads • 2020-02-14
Generating pseudorandom numbers is an interesting problem in Computer Science. In this article, we dive deep into an alg...
Isolation Forest Algorithm for Anomaly Detection
1134 reads • 2020-01-28
Anomaly detection is an age-old problem and in this article, we dive deep into an unsupervised algorithm, Isolation Fore...
Sleepsort and Concurrency in Golang
460 reads • 2017-07-16
Understanding concurrency in any programming language is tricky let alone Golang; hence to get my hands dirty the first ...
Topics I talk about
Being a passionate engineer, I love to talk about a wide range of topics, but these are my personal favourites.
Arpit's Newsletter read by 14000+ engineers
🔥 Thrice a week, in your inbox, an essay about system design, distributed systems, microservices, programming languages internals, or a deep dive on some super-clever algorithm, or just a few tips on building highly scalable distributed systems.