Algorithms

Strassen’s Algorithm for Matrix Multiplication

Given two n by n matrices A and B, the “typical” way of computing their product C = A • B is given by:

Matrix Multiplication: Intuitive Method

Reservoir Sampling

Suppose we are given a set S of n items, where n is either very large or inputed as a constant stream of items. The goal of reservoir sampling is to randomly choose k items from the set S, so that the probability that some item i in S is in the “reservoir” of k items is given by k/n. Each item…

Quicksort — The Best Sorting Algorithm?

The time complexity of Quicksort is O(n log n) in the best case, O(n log n) in the average case, and O(n^2) in the worst case. But because it has the best performance in the average case for most inputs, Quicksort is generally considered the “fastest” sorting…

The Egg Dropping Puzzle

Suppose a building has n floors. If we have m eggs, how can we find the minimum number of drops needed to determine from which floors it is safe to drop an egg (in other words, it won’t break)?

The Many Ways of Reversing a Linked List

A linked list is a data structure that consists of a set of data elements, called nodes. Each node then has an object (integer, string, etc…) and a pointer to the next node as its attributes.