CRC

In case you ever wondered how CRC worked (or how to use what you learned in Polynomials, Rings and Finite Fields), Cyclic Redundancy Check gives a short description of the math behind CRC as well as how to implement it as an algorithm.

Dancing Links

One of my co-workers forwarded me a copy of Dancing Links by Donald Knuth. In the paper, Knuth describes a backtracking algorithm, DLX, for solving exact cover problems using a doubly-linked-list type data structure. As the algorithm recursively searches for possible solutions, the links in the lists that represent the problem "dance" as they are updated from previous candidate solutions to reflect the candidate solution that is currently under consideration.

What is the exact cover problem? Given a set of elements U and a collection S of subsets of U, an exact cover C of U is a subset of S so that each element of U appears in exactly one of the subsets in C.

For example, suppose U = { 1, 2, 3, 4, 5 } and S = { S₁ = ( 1, 5 ), S₂ = ( 1, 2, 4 ), S₃ = ( 2, 3, 5 ), S₄ = ( 2, 4 ), S₅ = ( 1, 4 ), S₆ = ( 3 ), S₇ = ( 4 ) }. Then an exact cover of U is { S₁, S₄, S₆ } since together these three sets have all of the elements U = { 1, 2, 3, 4, 5 } and no elements appears in more than one of S₁, S₄, S₆. Similarly, { S₃, S₅ } is another exact cover. On the other hand, { S₁, S₃, S₇ } is not an exact cover because 3 appears in both S₁ and S₃. Likewise, { S₂, S₆ } is not an exact cover because neither S₂ nor S₆ contains 5.

Suppose you are given a chessboard (an 8 x 8 grid) and 32 dominos (2 x 1 rectangles), which have squares of the same size as the chessboard. Can you place the dominos on the chessboard so that each square of the chessboard is cover? Yes; and it should be straightforward to do! (e.g. Make a row of four dominos that are horizontal. That will cover one of the ranks of the chessboard. Simply repeat this seven more times). Now, what happens if I give you 31 dominos and cut away the top left (a8) and bottom right (h1) squares of the chessboard (so it has 30 white and 32 black squares). Can you cover this modified chessboard with your 31 dominos?

If the domino and chessboard example still sounds too contrived then consider how you would write a computer program that can solve Su Doku problems. [Hint: Dancing Links!]

Inversions

Given a sequence x₁, x₂, ... x_n, we say that the pair 1 &le i < j &le n is an inversion if x_i > x_j.

Now, given a sequence sequence S = x₁, x₂, ... x_n, how efficently can you count the total number of inversions in S?

For example, if S = 1, 5, 4, 3 then S has 3 inversions - the pairs (5, 4), (5, 3), and (4, 3).

The straightforward algorithm is the compare all pairs of elements in S, which has a O(n²) runtime.

A better algorithm is to modify the merge sort algorithm to count the inversions that it undoes while sorting S. This yields an O(nlogn) algorithm.

Is O(nlogn) the best possible? That is, is counting inversions also &Omega(nlogn)? (This is true for (comparision-based) sorting, but one does not necessarily need to sort to S to count the total number of inversions).