A to Z Computer Algorithms and Data Structures Definition
Adaptive Sort: A sorting algorithm that can take advantage of existing order in the input, reducing its requirements for computational resources as a function of the disorder in the input.
Backtracking: Backtracking is a type of algorithm that is a refinement of brute force search. In backtracking, multiple solutions can be eliminated without being explicitly examined, by using specific properties of the problem.
Clique : A clique in a graph is a set of pairwise adjacent vertices, or in other words, an induced subgraph which is a complete graph. In the graph at the right, vertices 1, 2 and 5 form a clique, because each has an edge to all the others.
Deterministic Algorithm: Deterministic algorithm is an algorithm which, in informal terms, behaves predictably. Given a particular input, it will always produce the same output, and the underlying machine will always pass through the same sequence of states. Deterministic algorithms are by far the most studied and familiar kind of algorithm, as well as one of the most practical, since they can be run on real machines efficiently.
Edge Coloring: edge coloring is one type of the graph coloring problem. A coloring of a graph’s edges assigns a “color” to each edge of the graph. The objective is to color the graph’s edges so that no vertex has two edges leaving it that have the same “color” and to use as few colors as possible. For example, the figure to the side shows a proper edge coloring, where no two edges out of the same vertex share the same color. In this example, the graph required three different colors, and could not be colored properly in any fewer.
Finite State Machine: A finite state machine (FSM) or finite state automaton (plural: automata) or simply a state machine, is a model of behavior composed of a finite number of states, transitions between those states, and actions. A finite state machine is an abstract model of a machine with a primitive internal memory.
Greedy Algorithms: Greedy algorithms are simple and straightforward. They are shortsighted in their approach in the sense that they take decisions on the basis of information at hand without worrying about the effect these decisions may have in the future. They are easy to invent, easy to implement and most of the time quite efficient. Many problems cannot be solved correctly by greedy approach. Greedy algorithms are used to solve optimization problems.
Heap : A heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key(A) ? key(B). This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max heap. (Alternatively, if the comparison is reversed, the smallest element is always in the root node, which results in a min heap.)
Independent Set: an independent set or stable set is a set of vertices in a graph no two of which are adjacent. That is, it is a set V of vertices such that for every two vertices in V, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in V. The size of an independent set is the number of vertices it contains.
Johnson’s Algorithm: Johnson’s algorithm is a way to find shortest paths between all pairs of vertices in a sparse directed graph. It allows some of the edge weights to be negative numbers, but no negative-weight cycles may exist.
Karnaugh Map: Karnaugh map, also known as a Veitch diagram (KV-map or K-map for short), is a tool to facilitate the simplification of Boolean algebra IC expressions. The Karnaugh map reduces the need for extensive calculations by taking advantage of human pattern-recognition and permitting the rapid identification and elimination of potential race hazards.
Linear probing: Linear probing is a scheme in computer programming for resolving hash collisions of values of hash functions by sequentially searching the hash table for a free location. This is accomplished using two values - one as a starting value and one as an interval between successive values in modular arithmetic. The second value, which is the same for all keys and known as the stepsize, is repeatedly added to the starting value until a free space is found, or the entire table is traversed.
Master Theorem: Master theorem, which is a specific case of the Akra-Bazzi theorem, provides a cookbook solution in asymptotic terms for recurrence relations of types that occur in practice. It was popularized by the canonical algorithms textbook Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, which introduces and proves it in sections 4.3 and 4.4, respectively. Nevertheless, not all recurrence relations can be solved with the use of the master theorem.
Non-Deterministic Algorithm: A non-deterministic algorithm is an algorithm with one or more choice points where multiple different continuations are possible, without any specification of which one will be taken.
Open Addressing: Open addressing, or closed hashing, is a method of collision resolution in hash tables. With this method a hash collision is resolved by probing, or searching through alternate locations in the array (the probe sequence) until either the target record is found, or an unused array slot is found, which indicates that there is no such key in the table. [1] Well known probe sequences include:
Polynomial Time: polynomial time refers to the computation time of a problem where the run time, m(n), is no greater than a polynomial function of the problem size, n. Written mathematically using big O notation, this states that m(n) = O(nk) where k is some constant that may depend on the problem. For example, the quicksort sorting algorithm on n integers performs at most An2 operations for some constant A. Thus it runs in time O(n2) and is a polynomial time algorithm.
Quadtree : A quadtree is a tree data structure in which each internal node has up to four children. Quadtrees are most often used to partition a two dimensional space by recursively subdividing it into four quadrants or regions. The regions may be square or rectangular, or may have arbitrary shapes. This data structure was named a quadtree by Raphael Finkel and J.L. Bentley in 1974.
Recursive Tree: A recursive tree is a non-planar labeled rooted tree. A size-n recursive tree is labeled by distinct integers 1, 2, …, n, where the labels are strictly increasing starting at the root labeled 1. Recursive trees are non-planar, which means that the children of a particular node are not ordered.
Simulated annealing: Simulated annealing (SA) is a generic probabilistic meta-algorithm for the global optimization problem, namely locating a good approximation to the global optimum of a given function in a large search space. It is often used when the search space is discrete (e.g., all tours that visit a given set of cities). For certain problems, simulated annealing may be more effective than exhaustive enumeration — provided that the goal is merely to find an acceptably good solution in a fixed amount of time, rather than the best possible solution.
Traveling Salesman Problem : The traveling salesman problem (TSP) in operations research is a problem in discrete or combinatorial optimization. It is a prominent illustration of a class of problems in computational complexity theory which are classified as NP-hard. The problem is given a number of cities and the costs of traveling from any city to any other city, what is the least-cost round-trip route that visits each city exactly once and then returns to the starting city?
Undecidable Problem : An undecidable problem is a problem whose language is not a recursive set. More informally, such problems cannot be solved in general by computers; see decidability.
Venn Diagram: Venn diagrams or set diagrams are diagrams, that show the logical relations of classes, a collection of sets (groups of things). Venn diagrams are invented around 1880 by John Venn, and nowadays used in many fields, including set theory, probability, logic, statistics, and computer science.
weighted Graph: A weighted graph associates a label (weight) with every edge in the graph. Weights are usually real numbers. They may be restricted to rational numbers or integers. Certain algorithms require further restrictions on weights, for instance, the Dijkstra algorithm works properly only for positive weights.
XOR: The logical operation exclusive disjunction, also called exclusive or (symbolized XOR or EOR), is a type of logical disjunction on two operands that results in a value of “true” if and only if exactly one of the operands has a value of “true”.
Yule–Simon distribution: In probability and statistics, the Yule–Simon distribution is a discrete probability distribution named after Udny Yule and Herbert Simon. Simon originally called it the Yule distribution.
The probability mass function of the Yule–Simon (?) distribution is
for integer and real ? > 0, where B is the beta function. Equivalently the pmf can be written in terms of the falling factorial as
where ? is the gamma function. Thus, if ? is an integer,
The probability mass function f has the property that for sufficiently large k we have
This means that the tail of the Yule–Simon distribution is a realization of
Zipf’s Law: f(k;?) can be used to model, for example, the relative frequency of the kth most frequent word in a large collection of text, which according to Zipf’s law is inversely proportional to a (typically small) power of k.
August 16th, 2008 at 3:26 pm
Useful post.
August 17th, 2008 at 8:50 pm
Interesting list, stumbled
August 18th, 2008 at 2:10 pm
Good post, stumbled!
August 18th, 2008 at 4:42 pm
Now if you will consider what was the nature of the government of Darius, you will find it similar to the kingdom of the Turk, and therefore it was only necessary for Alexander, first to overthrow him in the field, and then to take the country from him. After which victory, Darius being killed, the state remained secure to Alexander, for the above reasons. And if his successors had been united they would have enjoyed it securely and at their ease, for there were no tumults raised in the kingdom except those they provoked themselves.