Once again I feel myself being draw to take that damn test. I am a software professional. This means I do about .001% computer science. Computer Science is math. It has nothing to do with computers except that it maybe explains what a computer would theoretically be able to do if it were infinitely big.

So I am going to try to use the blog as my notes for reviewing. One issue that comes up time and time again is combinations. Combinations are based on permutations. If you have n distinct items, they can be ordered in in n! ways. For the non math people, n! is n times n-1 times n-2 … times 1. 0! is defined as 1, as they claim there is only one way to order zero items…suspect, but it keeps the algorithms easy.

If you want to figure out how many permutations of length m you can make out of n items, where n>m, you have n (n-1)(n-2)…(n-m+1). This is equal to n!/(n-m)!

Combinations are like permutations, but order does not matter. Basically, a combination is a subset. If you have three items, and you want a subset of two items, you can take {1,2} {2,3} or {1,3}. This is called n choose m, where n is the number of items in the set, and m is the number of items in the subset. The formula for this is n!/(n-m)!m!. This makes sense as you take the formula for permutations and divide out the number of redundant combinations of length m.

One place where combinations are useful is in graph theory. There are many comparable problems in graph theory which can all be converted into each other. One of these is the clique problem. A clique is a completely connected subgraph.

META Comment: This version of WordPress as a blogging tool does not make it easy to draw pictures.

The clique problem is to determine if there is a clique of size m in a graph whose number of nodes is n, n>m. A brute force algorithm iterates through all subsets of nodes of size m and checks to see if them make a clique. Testing for a clique is not computationally intensive, but generating all of the subsets is O(n choose m).