Grant: Discovery Grants Program - Individual

An algorithm is a step-by-step solution to a problem, explicit enough to be translated into a computer program. The time taken to solve a problem on a given computer depends upon the size of the problem and the efficiency of the algorithm. For example, it takes longer to look for a word in a large dictionary than in a small one, but for a given size of dictionary it takes longer by searching through the dictionary from beginning to end than by using the more efficient algorithm anyone would use. Combinatorial algorithms do things like combining and arranging objects in various ways and counting all the objects of a given type and size, either by constructing them all or by finding a formula for calculating the number of objects of that type as a function of its size. An illustrative example: which is the faster algorithm for counting the number of ways of arranging n objects, constructing all the n!=1x2x...xn arrangements or calculating the product 1x2x...xn? If the objects are strings of letters like 00, 01, 10, 11, it may be possible to arrange them in such an order that each one differs from the next one by a small number of letters (00,01,11,10). Such an arrangement is called a Gray code. The challenge: given a Gray code, design an algorithm that transforms each string into the next one in a small amount of time no matter how long the string is. A graph consists of points and lines, with each line joining a pair of points. Not every graph can be drawn on a piece of paper so that the lines don't cross each other (try drawing five points and joining every point to every other point with no lines crossing). The challenge: design an algorithm that calculates the number of graphs with n points and m lines that can be drawn in this way in less time than it takes to construct all the graphs and test whether they can be drawn.