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:
Continue reading

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:
Continue reading

Topological Sorting

The following is an implementation of topological sorting on a graph (Wikipedia). This sort runs in O(delim{|}{V}{|} + delim{|}{E}{|}), where delim{|}{V}{|} = number of vertices and delim{|}{E}{|} = number of edges.

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

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

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 O(m) where m = number of 1-bits.

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
Hint 2
Answer

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 O(nlgn).

For something fast, there’s an algorithm that runs in expected O(n) called QuickSelect (Wikipedia), a cross between Quicksort and binary search. Like Quicksort, there’s a worst-case time of O(n^2), 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