Patience sorting is a greedy sort that solves LIS in time . It goes as follows (from princeton.edu):

My implementation is in git and below:

Continue reading

Here’s another way to solve the longest increasing subsequence problem: Patience sorting (Wikipedia).

Patience sorting is a greedy sort that solves LIS in time . It goes as follows (from princeton.edu):

My implementation is in git and below:

Continue reading

The following is a dynamic programming implementation to find the longest increasing subsequence (Wikipedia). It runs in time .

This was used in my solving of SPOJ 11110. Easy Longest Increasing Subsequence ELIS and is in git and below:

Continue reading

Let’s say you have a random number generator RNG3() that uniformly returns from and you must use it to build RNG7() that uniformly returns from . How might you do it?

In my previous post I implemented Prim’s algorithm with pairing heap. Now, here’s another way to find the minimum spanning tree, using Kruskal’s algorithm (Wikipedia) with quick union. If you compare the code between posts, this is a whole lot simpler.

**The gist:**

- For each edge by weight ascending
- If nodes are in same component, forget/skip
- Else take edge and merge the two components

Here’s my implementation used in the solving of SPOJ 368. Cobbled Streets CSTREET, in git and below:

Continue reading

The following is an implementation of Prim’s algorithm (Wikipedia) using a pairing heap (Wikipedia). This is a greedy algorithm used to find a weighted undirected graph’s minimum spanning tree (Wikipedia).

My implementation is used to solve SPOJ 3188. Minimum Spanning Tree MST, and is in git and below:

Continue reading

Kosaraju’s algorithm (Wikipedia) finds a graph’s strongly connected components in linear time.

The algorithm runs in two phases:

**Phase 1:**

- grab an unseen node and perform depth-first search.
- add node to stack after children processed.
- while unseen nodes exist…

**Phase 2:**

- pop node off stack.
- graph traversed against directed edges.
- all within traversal belong to one strongly-connected component.
- while stack is not empty…

This algorithm is used in my solving of SPOJ 13990. Web islands WEBISL; implementation is in git and below:

Continue reading

The following is an implementation of topological sorting on a graph (Wikipedia). This sort runs in , where = number of vertices and = number of edges.

**Topological sort**: arrange directed graph — one node per column — so that all edges point right.

If each node is a job to be scheduled, and each incoming edge indicates a prerequisite, a topological ordering is a valid job scheduling; sweeping left to right, all prerequisites have been satisfied.

My implementation is in git and below:

Continue reading

Here’s a method find the next power of 2 (in languages where signed numbers are encoded as two’s complement).

long int pow_2_ceil(long int t) { if (t == 0) return 1; if (t != (t & -t)) { do { t -= t & -t; } while (t != (t & -t)); t <<= 1; } return t; }

Each loop strips the least-significant 1-bit directly; time is where .

Here’s another problem from the Algorithm Design Manual (Skiena), Interview Problem 4-44:

Design a stack that supports push, pop, and retrieving the minimum element in constant time. Can you do this?

If you need the nth largest element of an unsorted list, an obvious solution comes to mind:

sort(list); return list[nth];

This is easy to code but runs a little slow, in .

For something fast, there’s an algorithm that runs in expected called QuickSelect (Wikipedia), a cross between Quicksort and binary search. Like Quicksort, there’s a worst-case time of , so where handling large user-supplied inputs consider choosing the partition pivot element randomly.

**The gist**:

function quickselect(list, nth) begin = 0, end = list.size() loop partition list[begin, end) if partition equals nth, return list[partition] else drill down on partition's appropriate side loop end

My implementation is in git and below:

Continue reading