| Contributions by Kirk Kimmel |
| Abstract Data Type |
| A mathematically specified collection of data-storing entities with operations to create, access, change, etc. instances. |
|
| ANSI |
| American National Standards Institute.
|
|
| Big-O Notation |
| A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items.
Informally saying some equation f(n) = O(g(n)) means it is less than some constant multiple of g(n). More
formally it means there are positive constants c and k, such that 0 f(n) cg(n) for all n k. The values of c and k must be fixed for the function f and must not depend on n. |
|
| Complete Binary Tree |
| A binary tree in which all leaf nodes are at level n or n-1, and all leaves at level n are towards the left. |
|
| Cut Vertex |
| A vertex whose deletion along with incident edges breaks up the remaining graph into two or more disconnected pieces. |
|
| Doom |
| Doom is a game that is a landmark for the first person shooter game genre. Wolfenstein3D was the first FPS game but Doom took this idea to the next level. With unique monsters, dark levels, motivating music and the monster noises designed to give you nightmares for weeks the game is a classic. There were 4 dooms released. Ultimate Doom, Doom ][, Doom: TNT, and Doom: Plutonia.
The sucess of these games has spawned off many first person shooters and has made the market what it is today. These games were developed by ID software. Other titles made by ID include Quake 1, Quake 2 and the new Quake 3: Arena. |
|
| Dual Linear Program |
| Every linear program has a corresponding linear program called the dual. It is maxy {b · y | ATy c and y 0 }. For any solution x to the original linear program and any solution y to the dual we have c · x (AT y)T x = yT(Ax) y · b. For optimal x and y, equality holds. For a problem formulated as an integer linear program, a solution to the dual of a relaxation of the program can serve
as witness. |
|
| Duke Nukem 3D |
| Duke Nukem 3D was a game designed by 3d Realms. It uses portals and sectors (similar to Doom) in order to give the illusion of 3d space using a 2d mapping system. The mapping system and level designer are called Build. In addition, the Build Engine was used in other games such as Blood. At the time of release the Build engine was eclipsed by the Quake engine developed by ID software. Duke Nukem 3d was still a successful game due to the nature of the main character and the interactive enviroment. |
|
| Euler Cycle |
| A path through a graph which starts and ends at the same vertex and includes every edge exactly once. Also known as an Eulerian path, Euler tour, etc. |
|
| Fibonacci Numbers |
| A sequence of numbers such that each number is the sum of the preceding two. The first seven numbers are 1, 1, 2, 3, 5, 8, and 13. |
|
| Kolmogorov Complexity |
| The minimum number of bits into which a string can be compressed without losing information. This is defined with respect to a fixed, but universal decompression scheme, given by a universal Turing machine. |
|
| Kripke Structure |
| A finite state machine, whose states are labeled with boolean variables and whose next state is chosen nondeterministically.
It may be extended with fairness constraints. |
|
| Lattice |
| A point lattice generated by taking integer linear combinations of a set of basis vectors. |
|
| Lexicographical Order |
| Alphabetical or ``dictionary'' order. |
|
| Markov Chain |
| A weighted graph in which all weights are nonnegative and the total weight of outgoing edges is positive. |
|
| Matched Vertex |
| A vertex on an matched edge in a matching, or, one which has been matched. |
|
| Median |
| The value which has an equal number of values greater and less than it. For an even number of values, it is the mean of the two middle values. |
|
| Model of Computation |
| A formal, abstract definition of a computer. Using a model one can more easily analyze the intrinsic execution time or memory space of an algorithm while ignoring many implementation issues. There are many models of computation which differ in computing power (that is, some models can perform computations impossible for other models) and the cost of various operations. |
|
| NIST |
| The United States National Institute of Standards and Technology. |
|
| Sieve of Eratosthenes |
| An algorithm to find all prime numbers up to a certain N. Begin with an (unmarked) array of integers from 2 to N. The first unmarked integer, 2, is the first prime. Mark every multiple of this prime. Repeatedly take the next unmarked integer as the next prime
and mark every multiple of the prime. |
|
Unite 2010
