Parallel Bubblesort
In order for me to give back your midterms, please form a line and sort yourselves in alphabetical order, from A to Z.
There is traditionally a strong correlation between the midterm grades and the number of daily problems attempted:
daily: 0, sum: 134, count: 3, avg: 44.67
daily: 1, sum: 0, count: 2, avg: 0.00
daily: 2, sum: 63, count: 1, avg: 63.00
daily: 3, sum: 194, count: 3, avg: 64.67
daily: 4, sum: 335, count: 5, avg: 67.00
daily: 5, sum: 489, count: 8, avg: 61.12
daily: 6, sum: 381, count: 6, avg: 63.50
daily: 7, sum: 432, count: 6, avg: 72.00
daily: 8, sum: 217, count: 3, avg: 72.33
daily: 9, sum: 293, count: 4, avg: 73.25
Combinatorial Search
We have seen how clever algorithms can reduce sorting from 
to 
.
However, the stakes are even higher for combinatorially explosive problems:
The Traveling Salesman Problem
There is no known polynomial time algorithm
(ie. 
for some fixed k) for this problem, so
search-based algorithms are the only way to go if you need an optional solution.
But I want to use a Supercomputer
Moving to a faster computer can only buy you a relatively small improvement:
to
.
This is a speedup of 340 times on n=4096 and revolutionized the
field of image processing.
to O(n).
This is a speedup of 4000 times on n=4096.
Can Eight Pieces Cover a Chess Board?
Consider the 8 main pieces in chess (king, queen, two rooks, two bishops, two knights). Can they be positioned on a chessboard so every square is threatened?
Of course, this is not an important problem, but we will use it as an example of how to attack a combinatorial search problem.
How many positions to test?
Picking a square for each piece gives us the bound:
Anything much larger than 
is unreasonable to search on a modest
computer in a modest amount of time.
However, we can exploit symmetry to save work. With reflections along horizontal, vertical, and diagonal axis, the queen can go in only 10 non-equivallent positions.
Even better, we can restrict the white bishop to 16 spots and the queen to 16, while being certain that we get all distinct configurations.
Backtracking
Backtracking is a systematic way to go through all the possible configurations of a search space.
In the general case, we assume our solution is a vector
where each element 
is selected from a
finite ordered set 
,
We build from a partial solution of length k
and try to extend it by adding another
element.
After extending it, we will test whether what we have so far is still
possible as a partial solution.
If it is still a candidate solution, great.
If not, we delete 
and try the next element from 
:
Compute
, the set of candidate first elements of v.
k = 1
While k > 0 do
While
do (*advance*)
if (
) is solution, print!
k = k + 1
compute
k = k - 1 (*backtrack*)
Recursive Backtracking
Recursion can be used for elegant and easy implementation of backtracking.
Backtrack(a, k)
if a is a solution, print(a)
else {
k = k +1
compute
while
Backtrack(a, k)
}
Backtracking can easily be used to iterate through all subsets or permutations of a set.
Backtracking ensures correctness by enumerating all possibilities.
For backtracking to be efficient, we must prune the search space.
Constructing all Subsets
How many subsets are there of an n-element set?
To construct all 
subsets, set up an array/vector of n cells,
where the value of is either true or false, signifying whether the
ith item is or is not in the subset.
To use the notation of the general backtrack algorithm,
, and v is a solution whenever 
.
What order will this generate the subsets of 
?
Constructing all Permutations
How many permutations are there of an n-element set?
To construct all n! permutations, set up an array/vector of n cells,
where the value of is an integer from 1 to n which has not
appeared thus far in the vector, corresponding to
the ith element of the permutation.
To use the notation of the general backtrack algorithm,
, and v is a solution whenever .
The n-Queens Problem
The first use of pruning to deal with the combinatorial explosion was by the king who rewarded the fellow who discovered chess!
In the eight Queens, we prune whenever one queen threatens another. Listen To Part 11-11
Covering the Chess Board
In covering the chess board, we prune whenever we find there is a square which we cannot cover given the initial configuration!
Specifically, each piece can threaten a certain maximum number of squares (queen 27, king 8, rook 14, etc.) Whenever the number of unthreated squares exceeds the sum of the maximum number of coverage remaining in unplaced squares, we can prune.
As implemented by a graduate student project,
this backtrack search eliminates 
of the search space,
when the pieces are ordered by decreasing mobility.
With precomputing the list of possible moves, this program could search 1,000 positions per second. But this is too slow!
Although we might further speed the program by an order of magnitude, we need to prune more nodes!
By using a more clever algorithm, we eventually were able to prove no solution existed, in less than one day's worth of computing.
You too can fight the combinatorial explosion!
The Backtracking Contest: Bandwidth
The bandwidth problem takes as input a graph G, with n vertices and m edges (ie. pairs of vertices). The goal is to find a permutation of the vertices on the line which minimizes the maximum length of any edge.
The problem is NP-complete, meaning that it is exceedingly unlikely that you will be able to find an algorithm with polynomial worst-case running time. It remains NP-complete even for restricted classes of trees.
Since the goal of the problem is to find a permutation, a backtracking
program which iterates through all the n! possible permutations and
computes the length of the longest edge for each
gives an easy 
algorithm.
But the goal of this assignment is to find as practically good an algorithm
as possible.
Rules of the Game
Producing Efficient Programs
When in doubt, keep it simple, stupid (KISS).