Breadth-First-Search & Depth-First-Search

1. Breadth-First-Search
BFS(G){
for (each vertex u in V[G] - {s}) {
color[u] = WHITE;
d[u] = ∞;
Pi[u] = NULL;
}
color[s] = GRAY;
d[s] = 0;
Pi[s] = NULL;
ENQUEUE(Q, s);

While (!Q.empty()){
u = DEQUEUE(Q);
for (each vertex v in adj[u]){
color[v] = GRAY;
Pi[v] = u;
d[v] = d[u] + 1;
ENQUEUE(Q, v);
}
color[u] = BLACK;
}
}

2. Depth-First-Search
DFS(G){
for (each vertex u in V[G]){
color[u] = WHITE;
Pi[u] = NULL;
}
time = 0;
for (each vertex u in V[G]){
if (color[u] == WHITE)
DFS-VISIT(u);
}
}

DFS-VISIT(u){
color[u] = GRAY;
time ++;
d[u] = time;
for (each vertex v in adj[u]){
if (color[v] == WHITE){
Pi[v] = u;
DFS-VISIT(v);
}
}
time++;
f[u] = time;
color[u] = BLACK;
}

B-Tree

1. Find key k in Tree T:
B-TREE-SEARCH(x, k){
int i = 1;
while (i <= n[x] && k > keyi[x] )
i++;
if (i <= n[x] && k == keyi[x]) return (x, i); else{ if (leaf[x])
return NIL;
else
return (ci[x], k);
}
}

2. Insert a node in Tree T;
3. Delete a node in Tree T;

Binary Search Tree

1. Search an element in Tree T:
1)Recursive Method:
TREE-SEARCH(root[T], k){
x = root[T];
if (x == NIL || key[x] == k)
return x;
else{
if (k < key[x])
return TREE-SEARCH(left[x], k);
else
return TREE-SEARCH(right[x], k);
}
}
2)Iterative Method:
ITERATIVE-TREE-SEARCH(root[T], k){
x = root[T];
while (x != NIL && key[x] != k){
if (k < key[x])
x = left[x];
else
x = right[x];
}
return x;
}

2. Find the minimal element in Tree T:
TREE-MINIMUM(root[T]){
x = root[T];
while ( left[x] != NIL)
x = left[x];
return x;
}

3. Find the maximal element in Tree T:
TREE-MAXIMAL(root[T]){
x = root[T];
while (right[x] != NIL)
x = right[x];
return x;
}

4. Find the successor of element x in Tree T:
TREE-SUCCESSOR(x){
if (right[x] != NIL)
return TREE-MINMIAL(right[x]);
else{
y = p[x];
while (y != NIL && x = right[y]){
x = y;
y = p[y];
}
return y;
}
}

Team radio transmissions

zz from bbc

In the interest of transparency, full transcripts of the Team radio comms from the Chinese GP have now been made available. Selected quotes.

BMW: "Robert, can you get a close look at that Toyota diffuser?"
Kubica: "How about I bring some of it back with me?"

Kimi: "How many Hamiltons are there? That's the fourth one that's gone past me!"

Williams: "Kazuki. Be careful, the track's really wet now."
Nakajima: "It's okay, I'm not using the track!"

BMW: "Robert, there seems to be a problem with your nose."
Kubica: "Why does everyone have to talk about my nose?"

Ferrari: "Well, as we're not running KERS, at least we won't have any electrical problems!"
Massa: "&$%!!*$!"

McLaren: "Lewis, we're not sure about that last overtaking manoeuvre ... let Kimi past ... let Kimi past!"
Hamilton: "I already have ... several times!"

QUICK-SORT

Input: A(p, r)

QUICK-SORT(A, p, r){
if (p < r){
q = PARTITION(A, p, r);
QUICK-SORT(A, p, q-1);
QUICK-SORT(A, q+1, r);
}
}

Subroutine:
PARTITION(A, p, r){
i = p -1;
x = A[r];
for (j = p; j <= r-1; j++){
if (A[j] <= x){
i++;
exchange(A[i], A[j]);
}
}
exchange(A[i+1], A[r]);
return i+1;
}

Features:
1. T(n) = O(nlgn) ~ O(n2)
2. Sort in place

HEAP-SORT

Input: A[]

Main Algorithm:
HEAP-SORt(A)
{
BUILD-MAX-HEAP(A);
for (int i = length[A]; i >=1; i--)
{
exchange(A[1], A[i]);
heap-size[A]--;
MAX-HEAPIFY(A, 1);
}
}

Subroutines:
BUILD-MAX-HEAP(A)
{
heap-size[A] = length[A];
for (int i = [heap-size[A]/2]; i >= 0; i--)
MAX-HEAPIFY(A, i);
}

MAX-HEAPIFY(A, i)
{
l = 2i;
r = 2i +1;
if (l <= heap-size[A] && A[l] > A[i])
largest = l;
else
largest = i;
if (r <= heap-size[A] && A[r] > A[largest])
largest = r;
if (largest != r)
{
exchange(A[i], A[largest]);
MAX-HEAPIFY(A, largest);
}
}

Bubble Sort

Input: A[]

for (i = 1; i <= length[A]; i++)
    {
         for (j = length[A]; j >=i; j--)
           {
              if (A[j] < A[j-1])
                   Exchange (A[j], A[j -1]);
           }
     }

Features:
1. Stable