# Longest Increasing Subsequence: Patience Sort

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:

# Challenge: Smaller to Larger Random Number Generator

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?

Hint
It’s not a variant on , as that yields a bell curve.
Create a matrix with uniform values as follows:

```do {
RNG7 = M[RNG3()][RNG3()];
} while (RNG7 == 0);
```

# Kruskal’s Algorithm & Quick Union

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:

1. For each edge by weight ascending
2. If nodes are in same component, forget/skip
3. 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:

# Kosaraju’s Algorithm

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

The algorithm runs in two phases:

Phase 1:

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

Phase 2:

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

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

# Topological Sorting

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:

# Ceiling Power-of-Two

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 .

# Challenge: Constant-Time Min-Element Stack

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?
Hint 1
Constant time? Well then it’s stacks all the way down.
Hint 2
Two stacks, to be exact.
Data structure contains two stacks, and . is the minimum element. After calling , push to if . Before calling , pop from if .

# Nth Largest Element

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: