Stable Marriage Problem

Stable Marriage Problem is the problem of finding a stable matching between two sets of elements given a set of preferences for each element. Formally, given a set M = {m1, m2, …, mn} of n men, a set W = {w1, w2, …, wn} of n women, a preference list (i.e., an ordering of n men) for each woman and a preference list (i.e., an ordering of n women) for each man, the problem is to find a set S of pairs (m,w) for some m ∈ M and w ∈ W such that

  • Each m ∈ M and w ∈ W appears in exactly one pair in S
  • If (m, w) ∈ S and (m’, w’) ∈ S, then it cannot be the case that m prefers w’ to w and w’ prefers m to m’

Continue reading

Testing Bipartiteness

A bipartite graph G = (V, E) is a graph whose vertex set V can be partitioned into two disjoint sets X and Y such that every edge in E has one endpoint in X and the other in Y. Informally, a graph is bipartite if we can color its vertices red or black such that each edge connects a red vertex to a black vertex.

Continue reading

Beating Binary Search: The Interpolation Search

Interpolation search is an algorithm for finding a given key in a sorted array. While binary search always chooses the middle element for comparison, discarding one half of the search space or the other, interpolation search tries to predict where the key would lie in the search space via a linear interpolation, reducing the search space to the part before or after the estimated position if the key is not found there. This method will only work if calculations on difference between key values are sensible.

Continue reading