Algorithms

Implementations of most significant algorithms and some of their applications. All implementations are in Java, closely following the book "Algorithms, 4th ed." by Sedgewick, R. and Wayne, K. (2012 edition).

Codebase also mirrors the Coursera course on Algorithms, structuring code in weeks. Build is done via SBT, and uses automatic dependency management - except for algs4.jar which is an unmanaged dependency.

Current index:

1. (Week 1) Union-find

• Percolation (solves dynamic connectivity problem using Weighted Quick UF in linearithmic time)

2. (Week 2) Elementary data structures

• Simple Stack (backed by a singly-linked list, LIFO)
• Stack with Maximum (stack which tracks the maximum element currently on stack)
• Simple Queue (backed by doubly-linked, circular linked list, FIFO)
• Two-stack Queue (backed by two simple stacks)
• Deque (double-ended queue backed by doubly-linked list - all operations O(1))
• Randomized Queue (queue backed by array - all operations amortized O(1))
• Floyd's cycle detection (finds a repeated value on stack)
• Clone random linked list (clone doubly-linked list with random pointer in linear time without modifying the linked list itself)

3. (Week 3) Sorting

• Selection sort (in-place, O(N²/2))
• Insertion sort (in-place, stable, O(N²/4) for random arrays, O(kN) for partially sorted arrays)
• Shell sort (in-place: O(N^3/2), tight code, generalised insertion sort, complexity varies with h-sequence function)
• Shell sort - via array (ditto as above but pre-computes h-sequence and stores the values in an array)
• Merge sort - top-down (stable, O(NlgN))
• Merge sort - bottom-up (stable, O(NlgN), does not use recursion)
• Quick sort (in-place, O(NlgN), probabilistic guarantee, fastest in practice)
• Quick sort - Dijkstra's 3-way (ditto as above, improves performance in presence of duplicate keys)
• Quick sort - Entropy Optimal (ditto as above, average number of compares within constant factor of best-possible compare-based algorithm)
• Quick select (finds order statistic - k^th smallest number in O(N), probabilistic guarantee)
• Heap sort (in-place, O(2NlgN), tight code, suffers from data non-locality performance penalty)
• Priority queue - Max (backed by binary heap, build O(N), insert/remove max O(lgN), generalised stack/queue)
• Planar intersection (count identical 2D points in two sets without using hash-based data structure, sub-quadratic)
• Planar permutation (check if two sets of 2D points are permutation of each other without using hash-based data structure, sub-quadratic)
• Dutch national flag sort (Dijkstra's precursor idea for 3-way quick sort)
• Binary search (requires pre-sorted input, O(lgN))
• Selection filter (Returns number of 3D points closest to the origin in Euclidean distance)
• Index priority queue
• Min/max priority queue (supports insert(), deleteMax(), deleteMin() in O(lgN), and max(), min() in O(1))
• Dynamic median finding (supports insert() in O(lgN), findMedian() in O(1) and deleteMedian() in O(lgN))
• Fast PQ insert (minimum priority queue that supports insert() in O(loglogN) compares and deleteMin() in O(~2logN) compares)
• Taxicab numbers (taxicab number is an integer that can be expressed as the sum of two integers in two different ways: a³ + b³ = c³ + d³, e.g. 1729 = 9³ + 10³ = 1³ + 12³. Algorithm finds all taxicab numbers a, b, c, d smaller that N in time proportional to O(N²logN) time and space proportional to O(N²).)

4. (Week 4) Searching

• Symbol table (binary search tree, all ops O(lgN), except delete operation which is O(sqrt(N)))
• Check if a binary tree is a BST (uses extra space proportional to height of tree)
• Inorder traversal with constant extra space
• Self-organising search (algorithm that rearranges items to make those accessed frequently likely to be found early in the search)
• Interpolation search (binary search variation that mimics the process of looking near the beginning of a dictionary when the word begins with a letter near the beginning of the alphabet )