Algorithms That Interest Me

Numerical:

• Euclid’s algorithms

The algorithm rests on two observations:

If b|a then gcd(a, b) = b. No number (b, in particular) can have a divisor greater than itself (considering non-negative integers).

If a = bt + r, for integers t and r, then gcd(a, b) = gcd(b, r).

Every common divisor of a and b also divides r, so gcd(a, b) divides r. And since gcd(a, b)|b, it is a common divisor of b and r, giving gcd(a, b) ≤ gcd(b, r). The reverse holds as well, because every divisor of b and r also divides a.

// recursive
public int gcd(int a, int b) {
  if (b == 0){
    return a;
  }
  else{
    return gcd(b, a % b);
  }
}

// iterative
public int gcd(int a, int b) {
  while (b != 0) {
    int temp = q;
    q = p % q;
    p = temp;
  }
  return p;
}

• Gaussian elimination

Gaussian elimination is one of the oldest and most widely used algorithms for solving linear systems of equations. Liu Hui described it explicitly in 263 CE while presenting solutions in the famous Chinese text Jiuzhang suanshu (The Nine Chapters on the Mathematical Art), though mathematicians likely discovered it much earlier. The name “Gaussian elimination” arose after Gauss used it to predict celestial object locations with his newly discovered method of least squares. The approach: apply row operations to transform the original system into an upper triangular system, then back-substitute. One common pivot strategy selects the row with the largest absolute-value pivot element and swaps it before each pivot step, regardless of whether a zero pivot appears. This partial pivoting strategy fixes the zero-pivot problem and dramatically improves numerical stability.

{% highlight java %} public double[] gaussianElimination(double[][] A, double [] b) { int N = b.length;

for (int p = 0; p < N; p++) {
  //find pivot row
  int max = p;
  for (int i = p + 1; i < N; i++) {
    if (Math.abs(A[i][p]) > Math.abs(A[max][p])) {
      max = i;
    }
  }

  //swap
  double[] temp = A[p];
  A[p] = A[max];
  A[max] = temp;

  double t = b[p];
  b[p] = b[max];
  b[max] = t;

  // singular or nearly singular
  if (Math.abs(A[p][p]) <= le-10) {
    throw new RuntimeException("Matrix is singular or nearly signular");
  }

  // pivot within A and b
  for (int i = p + 1; i < N; i++) {
    double alpha = A[i][p] / A[p][p];
    b[i] -= alpha * b[p];
    for (int j = p; j < N; j++) {
      A[i][j] -= alpha * A[p][j];
    }
  }
}

// back substitution
double[] x = new double[N];
for (int i = N - 1; i >= 0; i--) {
  double sum = 0.0;
  for (int j = i + 1; j < N; j++) {
    sum += A[i][j] * x[j];
  }
  x[i] = (b[i] - sum) / A[i][i];
}
return x;

}

{% endhighlight %}

• Fourier-Motzkin elimination
  {% highlight java %}{% endhighlight %}
• Fast Fourier Transform
  {% highlight java %}{% endhighlight %}

Data structures:

• Binary trees
  {% highlight java %}{% endhighlight %}
• Hash tables
  {% highlight java %}{% endhighlight %}
• Binary decision diagrams
  {% highlight java %}{% endhighlight %}
• Disjoint sets
  {% highlight java %}{% endhighlight %}
• Trie
  {% highlight java %}{% endhighlight %}
• Priority queue
  {% highlight java %}{% endhighlight %}

Sorting & searching arrays:

• Bubblesort
  {% highlight java %}{% endhighlight %}
• Quicksort
  {% highlight java %}{% endhighlight %}
• Heapsort – mostly useful because building a heap is a really handy way of making a priority queue
  {% highlight java %}{% endhighlight %}
• Binary search
  {% highlight java %}{% endhighlight %}

Tree search:

• Breadth first search
  {% highlight java %}{% endhighlight %}
• Depth first search
  {% highlight java %}{% endhighlight %}

Graphs:

• Dijkstra’s algorithm
  {% highlight java %}{% endhighlight %}
• Prim’s algorithm
  {% highlight java %}{% endhighlight %}
• Ford-Fulkerson
  {% highlight java %}{% endhighlight %}
• A*
  {% highlight java %}{% endhighlight %}

Automata and parsing:

• Finite automata
  {% highlight java %}{% endhighlight %}

• Thompson’s construction for creating a nondeterministic finite automaton from a regular expression
  {% highlight java %}{% endhighlight %}

• The powerset construction for determinising a finite automaton
  {% highlight java %}{% endhighlight %}

• Pushdown automata and context-free languages
  {% highlight java %}{% endhighlight %}

• Recursive descent parsing for LL(k) languages LR parsing for LR(k) languages
  {% highlight java %}{% endhighlight %}

Numerical optimization:

• Simplex
  {% highlight java %}{% endhighlight %}
• Hill climbing algorithms
  {% highlight java %}{% endhighlight %}
• Newton’s method
  {% highlight java %}{% endhighlight %}

Combinatorial optimization:

• The Hungarian algorithm for solving the assignment problem
  {% highlight java %}{% endhighlight %}
• Boolean satisfiability – an NP-complete problem
  {% highlight java %}{% endhighlight %}
• DPLL – used to solve SAT
  {% highlight java %}{% endhighlight %}
• QBF – a PSPACE complete problem
  {% highlight java %}{% endhighlight %}

Graphics:

• Rasterisation
  {% highlight java %}{% endhighlight %}
• Ray tracing
  {% highlight java %}{% endhighlight %}

Compilers:

• Hindley-Milner type inference
  {% highlight java %}{% endhighlight %}
• Register colouring
  {% highlight java %}{% endhighlight %}

Machine learning:

• Back propagation for neural networks
  {% highlight java %}{% endhighlight %}
• Expectation maximization algorithm
  {% highlight java %}{% endhighlight %}
• Naive Bayes
  {% highlight java %}{% endhighlight %}
• Support vector machines
  {% highlight java %}{% endhighlight %}
• Random forests
  {% highlight java %}{% endhighlight %}

Cryptography:

• Diffie-Hellman key exchange
  {% highlight java %}{% endhighlight %}
• DES
  {% highlight java %}{% endhighlight %}
• Block cipher modes of operation – most important is CBC imho
  {% highlight java %}{% endhighlight %}
• RSA)
  {% highlight java %}{% endhighlight %}

Miscellaneous:

• Graham scan for finding convex hulls
  {% highlight java %}{% endhighlight %}
• Quine-McCluskey algorithm for logic minimization
  {% highlight java %}{% endhighlight %}