----------------------------------------------------------------------

Breadth-First Search (shortest path, equal weighted edges)

s = start node
e = end node
d[v] = shortest known distance from node s to node v
p[v] = previous node on shortest path from node s to node v

int bfs(node s, node e) {
    for each node v {
        d[v] = INF
        p[v] = INF
    }
    d[s] = 0
    queue q
    q.push(s)
    while !q.empty() {
        node v = q.front()
        q.pop()
        if v == e {
            return d[v]
        }
        for each neighbor x {
            if d[x] > d[v] + 1 {
                d[x] = d[v] + 1
                p[x] = v
                q.push(x)
            }
        }
    }
    return INF
}

----------------------------------------------------------------------

Dijkstra's Algorithm (shortest path, different weighted edges)

s = start node
e = end node
d[v] = shortest known distance from node s to node v
p[v] = previous node on shortest path from node s to node v
c[v][x] = cost to take edge from node v to node x

int dijkstra(node s, node e) {
    for each node v {
        d[v] = INF
        p[v] = INF
    }
    d[s] = 0
    priority_queue q
    q.push(s)
    while !q.empty() {
        node v = q.extract_min()
        if v == e {
            return d[v]
        }
        for each neighbor x {
            if d[x] > d[v] + c[v][x] {
                d[x] = d[v] + c[v][x]
                p[x] = v
                q.push(x)
            }
        }
    }
    return INF
}

----------------------------------------------------------------------

Bellman-Ford (shortest path, negative weighted edges)

s = start node
e = end node
d[v] = shortest known distance from node s to node v
p[v] = previous node on shortest path from node s to node v
c[v][x] = cost to take edge from node v to node x

int bellmanford(node s, node e) {
    for each node v {
        d[v] = INF
        p[v] = INF
    }
    d[s] = 0
    for i = 1 to n - 1 {
        for each edge (u, v) {
            if d[v] > d[u] + c[u][v] {
                d[v] = d[u] + c[u][v]
                p[v] = u
            }
        }
    }
    for each edge (u, v) {
        if d[v] > d[u] + c[u][v] {
           return -1
        }
    }
    return d[e]
}

----------------------------------------------------------------------

Floyd-Warshall (all-pairs shortest path)

for each edge (u, v) {
    d[u][v] = c[u][v]
    p[u][v] = u
}
for each node v {
    d[v][v] = 0
}
for each node k {
    for each node i {
        for each node j {
            if d[i][j] > d[i][k] + d[k][j] {
               d[i][j] = d[i][k] + d[k][j]
               p[i][j] = p[k][j]
            }
        }
    }
}

void printPath(int i, int j) {
     if (i != j) {
	printPath(i, p[i][j]);
	}
	cout << j;
}

----------------------------------------------------------------------

Transitive Closure (is node u reachable from node v?)

for each edge (u, v) {
    d[u][v] = true if u is connected to v, false otherwise
}
for each node v {
    d[v][v] = 1
}
for each node k {
    for each node i {
        for each node j {
            d[i][j] = d[i][j] || (d[i][k] && d[k][j])
        }
    }
}

----------------------------------------------------------------------

MiniMax (what is the maximum edge along the path with the smallest
maximum from node u to node v?)

for each edge (u, v) {
    d[u][v] = c[u][v]
}
for each node v {
    d[v][v] = 0
}
for each node k {
    for each node i {
        for each node j {
            d[i][j] = min(d[i][j], max(d[i][k], d[k][j]))
        }
    }
}

----------------------------------------------------------------------

MaxiMin (what is the minimum edge along the path with the largest
minimum from node u to node v?)

for each edge (u, v) {
    d[u][v] = c[u][v]
}
for each node v {
    d[v][v] = 0
}
for each node k {
    for each node i {
        for each node j {
            d[i][j] = max(d[i][j], min(d[i][k], d[k][j]))
        }
    }
}

----------------------------------------------------------------------

Safest Path (what is the probability of survival from node u to node v?)

c[u][v] = probability of surviving the edge from node u to node v
prob[u][v] = probability of surviving from node u to node v

for each edge (u, v) {
    prob[u][v] = c[u][v]
}
for each edge v {
    prob[v][v] = 1
}
for each node k {
    for each node i {
        for each node j {
            prob[i][j] = max(prob[i][j], p[i][k] * p[k][j])
        }
    }
}

----------------------------------------------------------------------

Topological Sort (ordering with dependencies, can also check for cycles)

vector s
queue q = Set of all nodes with no incoming edges
while !q.empty() {
    u = q.front()
    q.pop()
    s.push_back(u)
    for each edge (u, v) {
        remove edge (u, v) from graph
        if v has no other incoming edges
           q.push(m)
    }
}
if graph still has edges then graph has at least one cycle and thus no
topological ordering

DFS version of Topological Sort

list s

for each node v {
    d[v] = false
}
for each node v {
    if !d[v] {
        visit(v)
    }
}
void visit(node v) {
    d[v] = true
    for each neighbor u {
        if !d[u] {
            visit(u)
        }
    }
    s.push_front(v)
}

----------------------------------------------------------------------
Strongly Connected Components (Kosaraju's algorithm)

stack s

for each node v {
    d[v] = false
}
for each node v {
    if !d[v] {
       visit(v)
    }
}
Reverse each edge in the graph
for each node v {
    d[v] = false
}
while !s.empty() {
    v = s.top()
    s.pop()
    if !d[v] {
       print_component(v)
    }
}
void visit(node v) {
     d[v] = true
     for each neighbor u {
         if !d[u] {
             visit(u)
         }
     }
     s.push(v)
}
void print_component(v) {
     cout << v
     d[v] = true
     for each neighbor u {
         if !d[u] {
            print_component(u)
         }
     }
}

----------------------------------------------------------------------
Connected Components (not strongly)

comp = 0
for each node v {
    d[v] = INF
}
for each node v {
    if d[v] == INF {
       comp++
       visit(v, comp)
    }
}
void visit(node v, int comp) {
    d[v] = comp
    for each neighbor u {
        if d[u] == INF {
           visit(u, comp)
        }
    }
}

After the algorithm is finished, comp with hold the number of
components. d[v] with hold the component index of v. So if you want to
know how many components are in component 1, loop through and count
the number of 1's. You could use this to find the maximum size
component with one loop (component hash).

----------------------------------------------------------------------
Prim's Algorithm (minimum spanning tree)

r = arbitrary start node

for each node v {
    d[v] = INF
    p[v] = INF
}
d[r] = 0
priority_queue q
set s
while !q.empty() {
    node v = q.extract_min()
    for each neighbor u {
        if !s.contains(u) && c[v][u] < d[u] {
           d[u] = c[v][u]
           p[u] = v
           q.push(u)
        }
    }
    s.insert(v)
}

The minimum spanning tree is the set of edges (u, p[u]) for all nodes
u except r, the arbitrary start node.

----------------------------------------------------------------------
Kruskal's Algorithm (minimum spanning tree)

set S
for each edge e = (u, v) in order of least weight {
    if S union e doesn't contain a cycle {
       S.insert(e)
    }
}

Cycles can be checked using Topological Sort. This algorithm could
be made a lot faster with a Union-Find data structure.

----------------------------------------------------------------------
Max-Flow/Min-Cut

The c[u][v] represents the residual network and is initially the same
as the original network. For each edge (u, v) in the original network
the flow is given by the capacity of the backward edge (v, u) in the
residual network. HOWEVER, if the reversed edge (v, u) also exists in
the original network, this will fail, you must store the original
capacities of each edge. Then the flow along an edge is the difference
between the initial and the residual capacity.

int max_flow() {
    result = 0
    while (true) 
        path_capacity = find_path()
        if path_capacity = 0 {
            break
        } else {
            result += path_capacity
        }
    }
    return result
}

int find_path() {
    for each node v {
        d[v] = false
        p[v] = INF
    }
    d[source] = true
    queue q
    q.push(source)
    bool done = false
    while !done && !q.empty() {
        node v = q.top()
        q.pop()
        for each neighbor u {
            if !d[u] && c[v][u] > 0 {
                d[u] = true
                p[u] = v
                q.push(u)
                if u == sink {
                    done = true
                    break
                }
            }
        }
    }
    v = sink
    path_cap = INF
    while p[v] != INF {
        u = p[v]
        path_cap = min(path_cap, c[u][v])
        v = u
    }
    v = sink
    while p[v] != INF {
          u = p[v]
          c[u][v] -= path_cap
          c[v][u] += path_cap
          v = u
    }
    if path_cap == INF {
        return 0
    } else {
        return path_cap
    }
}

----------------------------------------------------------------------
Eulerian Path/Cycle (use all edges)

A connected multigraph has an Euler circuit iff each of its vertices
has even degree. A connected multigraph has an Euler path but not an
Euler circuit iff it has exactly two vertices of odd degree.

Eulerian-Circuit(G) {
    C = arbitrary starting circuit
    H = G with edges of C removed
    while H has edges {
        S = circuit beginning and ending at a vertex in H that is also
            in C
        H = H with edges of S removed
        C = C with edges of S inserted at the appropriate vertex
    }
}

----------------------------------------------------------------------
Hamiltonian Path/Cycle (use all vertices)

Dirac's Theorem: If G is a simple graph with n vertices with n >= 3
such that the degree of every vertex in G is at least n/2, then G has
a Hamiltonian circuit.

Ore's Theorem: If G is a simple graph with n vertices with n >= 3 such
that deg(u) + deg(v) >= n for every pair of nonadjacent vertices u and
v in G, the G has a Hamiltonian circuit.

Solve this with Depth-First Search with pruning.

----------------------------------------------------------------------
Vertex Cover (cover edges with vertices)/Independent Set (largest set
of unconnected vertices)

Brute force, try all subsets.

----------------------------------------------------------------------
Maximal Matching

Use Max-Flow. Create a source with edges going to all nodes on one
side and create a sink with edges coming from all nodes on the other
side. Assign capacity 1 to all edges. Max-Flow value is the number of
matchings and edges with flow from one side to the other represent the
actual matchings.

----------------------------------------------------------------------
Coloring

Brute force. Depth-First Search with pruning. Assign the first node
color 1, recurse, choose between color 1 and 2 for node 2 recursing on
each option. At each level you only need to choose between using one
of the previously used colors (which you can do as long as there are
no conflicts), and creating a new color. Storing the current minimum
number of required colors allows you to prune subtrees that use too
many colors.

----------------------------------------------------------------------

Interval Scheduling

Greedy: intervals have start and end times and no weights

Initially let R be the set of all requests, and let A be empty
while R is not yet empty {
    Choose a request i in R that has the smallest finishing time
    Add request i to A
    Delete all requests from R that are not compatible with request i
}

Dynamic Programming: intervals have start and end times and weights

p[j] = largest index i < j such that intervals i and j are disjoint

Opt(j) {
    if j == 0 {
        return 0
    } else if M[j] is defined {
        return M[j]
    } else {
        define M[j] = max(v[j] + Opt(p[j]), Opt(j-1))
        return M[j]
    }
}

Brute Force: intervals do not have start and end times just weights
    Algorithm: try all subsets, pick best one

----------------------------------------------------------------------

Subset Sum

A[i][j] = 1 if there exists a subset of the elements 1 through i that
          sum to j
A[i][j] = 0 otherwise
A[i][j] = max(A[i-1,j], A[i-1,j-w[i]]) if i,j > 0
A[i][j] = 1 if j = 0
A[i][j] = 0 if i = 0 and j != 0

----------------------------------------------------------------------

Maximum Sum Substring

maximum = 0
total = 0
for each element e in sequence {
    total = max(total + e, 0)
    maximum = max(maximum, total)
}
return maximum

Other version:

maximum = 0
for i = 0 to A.size {
    if i == 0 || d[i-1] < 0 {
        d[i] = A[i]
    } else {
        d[i] = A[i] + d[i-1]
    }
    if i == 0 || d[i] > maximum {
        maximum = d[i]
    }
}
return maximum

----------------------------------------------------------------------

0-1 Knapsack

if w < w[i] then OPT(i,w) = OPT(i-1,w). Otherwise
OPT(i,w) = max(OPT(i-1,w),v[i]+OPT(i-1,w-w[i]))

----------------------------------------------------------------------

Making Change

Find the minimum number of coins needed to make a certain amount of
change given coins V[j] for j = 0 to n - 1.

MAKE-CHANGE(V[], s) {
    for i = 1 to s {
        d[i] = INF
    }
    for i = 1 to s {
        for j = 0 to V.size {
            if V[j] <= i && d[i-V[j]] + 1 < d[i] {
                d[i] = d[i-V[j]] + 1
            }
        }
    }
    return d[s]
}

Find the number of ways to make change n using coins 1 though m

int count(n, m)
    for j = 0 to m {
        table[0][j] = 1
    }
    for i from 0 to n {
        for j from 0 to m {
            table[i][j] = ((i - c[j] >= 0) ? table[i - c[j]][j] : 0) +
                          ((j - 1 >= 0) ? table[i][j - 1] : 0)
        }
    }
    return table[n][m]
}

----------------------------------------------------------------------

Edit Distance/Sequence Alignment

int editDistance(char s[1..m], char t[1..n]) {
    for i from 0 to m {
        d[i][0] = i
    }
    for j from 0 to n {
        d[0][j] = j
    }
    for j from 1 to n {
        for i from 1 to m {
            if s[i] = t[j] { 
                d[i][j] = d[i-1][j-1]
            } else {
                d[i][j] = min(d[i-1, j] + 1,  // deletion
                              d[i, j-1] + 1,  // insertion
                              d[i-1, j-1] + 1) // substitution
            }
        }
    }
    return d[m][n]
}

----------------------------------------------------------------------

Longest Increasing Subsequence

A = subsequence
B = sorted subsequence
longestCommonSubsequence(A, B)

----------------------------------------------------------------------

Longest Common Subsequence

for i = 0 to A.size {
    d[i][0] = 0
}
for i = 0 to B.size {
    d[0][i] = 0
}
for i = 1 to A.size {
    for j = 1 to B.size {
        if A[i-1] == B[j-1] {
            d[i][j] = d[i-1][j-1] + 1
        } else {
            d[i][j] = max(d[i][j-1], d[i-1][j])
        }
    }
}
recon(A.size, B.size)
void recon(int i, int j) {
    if i == 0 || j == 0 {
        return;
    }
    if A[i-1] == B[j-1] {
        recon(i-1, j-1)
        print(A[i-1])
    } else if d[i-1,j] > d[i,j-1] {
        recon(i-1, j)
    } else {
        recon(i, j-1)
    }
}

----------------------------------------------------------------------

Longest Common Substring

for i = 0 to A.size {
    d[i][0] = 0
}
for j = 0 to B.size {
    d[0][j] = 0
}
len = 0
answer = <0,0>
for i = 1 to A.size {
    for j = 1 to B.size {
        if A[i] != B[j] {
            d[i][j] = 0
        } else {
            d[i][j] = d[i-1][j-1] + 1
            if d[i][j] > len {
               len = d[i][j]
               answer = <i,j>
            }
        }
    }
}

----------------------------------------------------------------------

Partition Problem

Use Subset Sum algorithm. You are looking for a subset that sums to
half of the total weight of all of the elements.

----------------------------------------------------------------------

Bin Packing

The core algorithm is very much brute force
- We can improve by using dynamic programming
- We no longer need a lower bound on the sizes
- There are k different item sizes
- An input is of the form (n1 , . . . , nk )
- We want to calculate OPT(n1 , . . . , nk ), the optimal number
of bins to pack this input

- Consider an input (n1 , . . . , nk ) with n = sum(n sub j) items
- Determine set of k-tuples (subsets of the input) that can be
packed into a single bin
- That is, all tuples (q1 , . . . , qk ) for which OPT(q1 , . . . , qk ) = 1
and for which 0 <= q j <= n j for all j
- There are at most nk such tuples, each tuple can be checked
in linear time
- (Exercise: there are at most (n/k)k such tuples)
- Denote this set by Q

- For each k-tuple q in Q, we have OPT(q) = 1
- Calculate remaining values by using the recurrence
OPT (i1,...,ik) = 1 + min OPT (i1 - q1 , . . . , ik - qk )
for each q in Q
- Exercise: think about the order in which we can calculate
these values
- Each value takes O(nk ) time, so we can calculate all values
in O(n2k ) time
- This gives us in the end the value of OPT(n1 , . . . , nk )


----------------------------------------------------------------------

Matrix Chain Multiplication

MATRIX-CHAIN(R[], C[]) {
    for i = 0 to R.size {
        d[i][1] = 0
    }
    for j = 2 to N {
        for i = 0; i+j-1 < N; i++ {
            d[i][j] = d[i+1][j-1] + r[i]*c[i]*c[i+j-1]
            b[i][j] = 1
            for k = 2 to j-1 {
                if d[i][k] + d[i+k][j-k] + r[i]*c[i+k-1]*c[i+j-1] <
                   d[i][j] {
                    d[i][j] = d[i][k] + d[i+k][j-k] +
                              r[i]*c[i+k-1]*c[i+j-1]
                    b[i][j] = k
                }
            }
        }
    }
    return d[0][R.size]
}

----------------------------------------------------------------------

Subsets

int maxsubset = 1<<n;
for (int subset = 0; subset < maxsubset; subset++) {
    for (int i = 0; i < n; i++) {
        if (subset & (1<<i)) {
           // collect information about element i
        }
    }
    for (int i = 0; i < n; i++) {
        if (subset & (1<<i)) {
           for (int j = i+1; j < n; j++) {
               if (subset & (1<<j)) {
                  // do something with pair i, j
               }
           }
        }
    }
}

----------------------------------------------------------------------

Template

#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <utility>
#include <algorithm>
#include <iterator>
#include <sstream>
#include <iomanip>
#include <cctype>
#include <cmath>
using namespace std;

#define FEQ(A, B) (fabs((A) - (B)) < 1e-9)
const int INF = 1000000; // 1 million
const double PI = 3.141592653589793238
const double EPS = 1e-9;

int main() {
    freopen("file.in", "r", stdin);
    int K;
    cin >> K;
    for (int i = 0; i < K; i++) {
        // fill in here
        cout << "Data Set " << i+1 << ":\n";
        // output answer here
    }
}

----------------------------------------------------------------------

Priority Queue

#include <iostream>
#include <queue>
using namespace std;

struct Node {
    int x, y, value;
    bool operator<(const Node &b) const {
        return this->value < b.value;
    }
};

int main() {
    priority_queue<Node> q;
    Node a = {0,0,10}, b = {10,20,5}, c = {2,2,7};
    q.push(a); q.push(b); q.push(c);
    while (!q.empty()) {
        Node n = q.top();
        q.pop();
        cout << n.x << ' ' << n.y << ' ' << n.value << endl;
    }
}

// prints:
// 0 0 10
// 2 2 7
// 10 20 5

----------------------------------------------------------------------

Multimap

#include <iostream>
#include <map>
#include <utility>
using namespace std;

int main() {
    multimap<char,int> mult;
    multimap<char,int>::iterator it;
    pair<multimap<char,int>::iterator,multimap<char,int>::iterator> ret;
    mult.insert(make_pair('a',10));
    mult.insert(make_pair('b',20));
    mult.insert(make_pair('b',30));
    mult.insert(make_pair('b',40));
    mult.insert(make_pair('c',50));
    mult.insert(make_pair('c',60));
    mult.insert(make_pair('d',60));
    cout << "mult contains:\n";
    for (char ch = 'a'; ch <= 'd'; ch++) {
        cout << ch << " =>";
        ret = mult.equal_range(ch);
        for (it = ret.first; it != ret.second; ++it) {
            cout << " " << (*it).second;
        }
        cout << endl;
    }
}

----------------------------------------------------------------------

Multiset

#include <iostream>
#include <set>
using namespace std;

int main() {
    int myints[] = {10,73,12,22,73,73,12};
    multiset<int> mymultiset(myints, myints + 7);
    cout << "73 appears ";
    cout << (int)mymultiset.count(73);
    cout << " times in mymultiset." << endl;
}

----------------------------------------------------------------------

Bitset

#include <iostream>
#include <bitset>
using namespace std;

int main() {
    bitset<4> mybits;
    mybits[1] = 1; // 0010
    mybits[2] = mybits[1]; // 0110
    cout << "mybits: " << mybits << endl; 
}

count() - returns number of 1's
none() - returns true if no 1's
any() - return true if any 1's
flip(i) - flip ith bit
bitset<10> second (120ul); // initialize from unsigned long
bitset<10> third (string("01011")); // initialize from string

----------------------------------------------------------------------

Sort/Binary Search

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool myfunction (int i, int j) {
    return i < j;
}

int main() {
    int myints[] = {1,2,3,4,5,4,3,2,1};
    vector<int> v(myints, myints+9);
    sort (v.begin(), v.end());
    cout << "looking for a 3... ";
    if (binary_search (v.begin(), v.end(), 3)) {
        cout << "found!\n";
    } else {
        cout << "not found.\n";
    }
    sort(v.begin(), v.end(), myfunction);
    cout << "looking for a 6... ";
    if (binary_search (v.begin(), v.end(), 6, myfunction)) {
        cout << "found!\n";
    } else {
        cout << "not found.\n";
    }
}

// prints:
// looking for a 3... found!
// looking for a 6... non found.

BinarySearch(A[0..N-1], value, low, high) {
       if (high < low)
           return -1 // not found
       mid = low + ((high - low) / 2) 
       if (A[mid] > value)
           return BinarySearch(A, value, low, mid-1)
       else if (A[mid] < value)
           return BinarySearch(A, value, mid+1, high)
       else
           return mid // found
   }

----------------------------------------------------------------------

Set Algorithms

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int first[] = {5,10,15,20,25};
    int second[] = {50,40,30,20,10};
    vector<int> v;
    vector<int>::iterator it;
    sort(first, first+5);
    sort(second, second+5);
    it = set_union(first, first+5, second, second+5, back_inserter(v));
    cout << "union has " << int(it - v.begin()) << " elements.\n";
}

// prints:
// union has 8 elements

set_intersection, set_difference, and set_symmetric_difference work
similarly.

----------------------------------------------------------------------