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 ...


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.



  • v10.6.4
  • © Arpit Bhayani, 2022