algorithm.mkd

NP Problem

3-Partition Problem

Given a multiset S of size $n = 3m$, can S be partitioned into m subsets $S_1$, $S_2$, $S_m$ such that the sum of the numbers in each subset is equal? What if $S_i$ is between $B/4$ and $B/2$.

Divide and Conqur

Repeated doubling

Loop in link list

How to check if there is a loop in link list in linear time? How to locate the right position the loop begins?

Grpah Algorithm

MST

Boruvka's algorithm

T = empty;
WHILE G has >= 1 vertex: 
    each vertex of G adds its lightest edge to T;
    the added edges are contracted in G; 
END WHILE

Prim's algorithm

T = graph with only the lightest edge;
FOR i = 2 to n-1:
    add to T the minimum length edge with exact one endpoint in T;
END FOR

Kruskal's algorithm

T = empty
FOR i = 1 to n-1:
    add to T the shortest edge that does not introduce a cycle;
END FOR

Numeric algorithm

square root algorithm

double sqrt(double s) {
    double x = s, y = 0;
    while (fabs(x - y) < 0.000001) {
        y = x;
        x = (x + s/x)/2;
    }
    return x;
}

Data Structures

Arrays

Shift an array without only one space.

List

Skip list

Trees

van Emde Boas tree

Suffix Array and Suffix Tree

Find a pattern in text using suffix array in linear time

Build sufix array for string "p#t$", compare suffix 0 with its two neighbors to see if they match in length |p|.

Therorems

Four-color theorem

Randomization

$N$ Professor's Problem

Suppose we have a room of professors and we wish to calculate the average salary of this group. The only limitation we have, though, is that we must not allow any professor to learn any information about any of the salaries of the other professors. This includes knowing the exact value of a person's salary and knowing if this person's salary is higher or lower or equal.

Use a serial of random numbers which are generated by a single prime key.

Minimum-cut

Interpolation search (extrapolation search)