Algorithms 1 - Two Much Wealth [Theory]

by JT Cho

The king of the distant country Sikinia has tasked you to keep records of the individual wealth of his people. There are $n = 2^k$ people living in Sikinia. However, the king does not care about every individual's wealth, but the net-worth of every $2^i$'th wealthiest person. Your . . .

Java Singletons

by JT Cho

This article is part of a series on coding interview topics. Design a type that can only be instantiated once. In software engineering, the singleton pattern is a design pattern that restricts the instantiation of a type to only one object. public class Foo { private static final Foo fooInstance = new . . .

Average Runtime of Quicksort

by JT Cho

It's always boggled my mind how statistics plays a role in the runtime analysis of various algorithms. The two seemingly distinct fields of Computer Science and Statistics mesh in a very surprising way - enabling one to make strong statements regarding the asymptotic complexity of an algorithm. In this article . . .

Bernoulli Laplace Model of Diffusion

by JT Cho

This post is a part of a series on stochastic theory. In this article, we will work through a standard theory problem on the Bernoulli-Laplace model of diffusion. I presume here that you have a basic understanding of what a Markov chain is. Problem Context Let's consider two urns, each . . .

Further Examining Simple Recurrences

by JT Cho

The class I TA for recently began examining recursive algorithms that follow the divide-and-conquer paradigm. These algorithms are a particularly interesting subset that can involve some tricky algebra when proving asymptotic bounds. This article is intended to help those students, as well as delve a lot deeper into the rigorous . . .