The Dutch National Flag Algorithm takes as input an array of comparable elements and a pivot. It outputs nothing, and after it’s done running the array has its elements moved around in-place so that all elements less than the pivot come first, then all elements equal to the pivot, and then all elements greater than the pivot. This algorithm shows up in quicksort, of which it’s the only really complicated part in my opinion. What makes it special is that it runs in one pass and uses only constant space. The intuition behind this algorithm and the way its indices change eluded me until recently, so I’m writing this post to explain it.

Moore’s Voting Algorithm finds the majority element in a homogenous array in a single pass, with constant space. It’s easy to see why that’s optimal in both space and time. The algorithm is based on a neat insight that’s easy to derive and implement. This post explains that insight. The algorithm follows naturally. Without further ado:

How do you rotate a square matrix counter-clockwise? That’s easy enough: you map the cell located at $(r, c)$ to the cell located at $(n-c-1, r)$, where $n$ is the length of a side of the square matrix.

This blog post discusses the solution to one of the exercises in an online course I’ve been doing in my spare time.

This post is an attempt to put my understanding of the intuition behind the Y combinator into words. It is a follow up to my earlier, introductory post on the untyped lambda calculus.

This post is a collection of notes I put together when trying to understand the concept of problem reduction. It is more or less taken directly from Ullman and Hopcroft’s excellent textbook on Automata Theory.

This blog post is an introduction to the lambda calculus. It doesn’t assume too much prior knowledge. In fact, I’ve tried to make this post self-contained. If something is unclear, please let me know!

What’s this?

Note: This article was written for the Computer Science students at IIT Bombay. I thought it might be useful for a wider audience, so I published it here on my blog. I hope you enjoy it!