Utility Codes

1. Randomized Median Finder :- A utility code which computes the median of n elements in O(n). It is based on a randomized median finding algorithm which is faster then the deterministic selection algorithm. Is derived from the algorithm mentioned in the book Probability and Computing by Mitzenmacher.

2. Range Minimum Query :- A utility code for the RMQ problem ( (O(nlogn,), O(1) ) time. Is derived from the topcoder algorithm tutorial Range Minimum Query and Lowest Common Ancestor

3. Knuth Morris Pratt :- A utility code for string search given a text and a pattern, computes the indexes at which pattern is found in the given text. A O(m+n) algorithm where m and n are lengths of the text and the pattern. Refer to the wikipedia page for more details.

4. Linear General Selection Algorithm :- A utility code which is the implementation of the median of median selection algorithm given in the textbook "Introduction to Algorithm" By Cormen in Chapter 9. The algorithm finds the kth element in the array(1-indexed) in worst case O(n). Refer to the wikipedia page for more details.

5. Morris Inorder Traversal :- A small utility code which is the stackless, non recursive implementation of an in-order traversal on a binary search tree.

6. Closest Pair of Points :- A utility code which finds the closest pair of points in O(nlogn) given a set of n points in the 2-D plane which is better then the naive soution of O(n^2). The code assumes that the x-coordinates values are unique. The algorithm implemented is based on the explanations given in the textbook Algorithm Design by Jon Kleinberg.

All sources on this page are under MIT License.