| abstract data type : |
A set of data values and associated operations that are precisely specified independent of any particular implementation. Also known as ADT. |
|
| acyclic graph : |
a graph that contains no cycles |
|
| adjacent edges : |
two distinct edges are said be adjacent if they have at least one vertex in common |
|
| adjacent vertices : |
two distinct vertices are said be adjacent if there is an edge connecting them |
|
| Algebra : |
A generalization of arithmetic in which symbols, usually letters of the alphabet, represent numbers or members of a specified set of numbers and are related by operations that hold for all numbers in the set. |
|
| algorithm : |
a step-by-step procedure for solving a problem or accomplishing some task |
|
| Analyzing Algorithm : |
In this, we determine the time it will take to solve a problem, also some time involve the memory or space required to solve a problem |
|
| Asymptotic analysis : |
The asymptotic analysis of an algorithm determines the running time. To perform the asymptotic analysis, we find the worst-case number of primitive operations executed as a function of the input size and express this function with asymptotic notation. |
|
| Asymptotic notation : |
It is a special kind of mathemaics. An important tool to analyze which algorithm is the best suited for the job |
|
| Asymptotically equal : |
Consider the following functions : • 4n2, • (8n2 + 2n - 3), • (n2/5 + n - 10 log n) • n(n - 3) are all asymptotically equivalent. Because the highest order term of n in all functions is n2. |
|
| Average case : |
Its an intermediate case in best and worst case which involves some probibilties of inputs. Average-case time is more difficult to compute; it is difficult to specify probability distribution on inputs. |
|
| bag : |
Definition: An unordered collection of values that may have duplicates. Formal Definition: As an abstract data type, a bag has a single query function, numberIn(v, B), which tells how many copies of an element are in the bag, and two modifier functions, add(v, B) and remove(v, B). These may be defined with axiomatic semantics as follows. new() returns a bag numberIn(v, new()) = 0 numberIn(v, add(v, B)) = 1 + numberIn(v, B) numberIn(v, add(u, B)) = numberIn(v, B) if v ≠ u remove(v, new()) = new() remove(v, add(v, B)) = B remove(v, add(u, B)) = add(u, remove(v, B)) if v ≠ u where B is a bag and u and v are elements. The predicate isEmpty(B) may be defined with the following additional axioms. isEmpty(new()) = true isEmpty(add(v, B)) = false Also known as multi-set. |
|
| Best case : |
A scenario in which cost (possible use of resources) of an algorithm is minimum to process an input sequence called best case. |
|
| Big-oh notation : |
the Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. More exactly, it is used to describe an asymptotic upper bound for the magnitude of a function in terms of another. |
|
| Close form expression : |
A non recursive form of an expression is called Closed Form Expressions used for Approximations of the recursive relations. |
|
| Compiler : |
A program that translates another program written in a high-level language into machine language so that it can be executed. |
|
| complete graph : |
a simple graph in which every pair of distinct vertices are adjacent |
|
| connectedness : |
describes a graph in which for any given vertex in the graph, all the other vertices are reachable from it |
|
| cycle (or circuit) : |
a path that begins and terminates in the same vertex |
|
| data structure : |
An organization of information, usually in memory, for better algorithm efficiency, such as queue, stack, linked list, heap, dictionary, and tree, or conceptual unity, such as the name and address of a person. It may include redundant information, such as length of the list or number of nodes in a sub tree. |
|
| decimal system : |
1. A number system based on units of 10. 2. A system of measurement in which all derived units are multiples of 10 of the fundamental units. |
|
| degree of a vertex : |
the number of edges incident to a given vertex |
|
| digraph (or directed graph) : |
a graph in which every edge is directed |
|
| distance : |
the length of a minimum path length from one specific vertex to another vertex. |
|
| Divide and Conquer Technique : |
The idea behind this technique is to take a problem on a large input, break the input into smaller pieces, solve the problem on each of the small pieces, and then combine the piecewise solutions into a global solution. It consist of three parts, Divide: the problem into a small number of pieces Conquer: solve each piece by applying divide and conquer to it recursively Combine: the pieces together into a global solution. |
|
| Dominated term : |
If there are two points p and q in a set, now p is said to be dominated term if and only if p.x <= q.x and p.y <= q.y. |
|
| Dominating term : |
If there are two points p and q in a set, now q is said to be dominating term if and only if p.x <= q.x and p.y <= q.y. |
|
|
| edge (or arc) : |
a connection made between two vertices in a graph |
|
| Efficient Algorithm : |
Efficient algorithms are those algorithm which take minimum resources w. r. t. time and storage to process a legal set of inputs. |
|
| elementary cycle : |
a cycle through a graph that does not visit any vertex more than once |
|
| elementary path : |
a path in which all the vertices are distinct |
|
| Factorial Time Algorithm : |
Factorial time algorithms are almost always impractical. The number of steps required to complete the algorithm becomes very large very quickly as the size of the input grows. |
|
| Function : |
A computation which takes some arguments or inputs and yields an output. Any particular input yields the same output every time. More formally, a mapping from each element in the domain to an element in the range. (2) A subroutine which returns a value. |
|
| Generic machine : |
It is an ideal machine which is independent of all complexities of hardware and software, used to check the performance of an algorithm, also called RAM. |
|
| graph : |
consists of a set of vertices and a set of edges |
|
| incident : |
an edge that joins two specified vertices is said to be incident to them |
|
| indegree : |
the number of edges terminating in a given node in a directed graph |
|
| inefficient algorithm : |
Inefficient algorithms are those algorithm which take maximum resources w. r. t. time and storage to process a legal set of inputs. |
|
| Input instance : |
A unique set of legal inputs is called an input instance. |
|
| isolated vertex : |
a vertex of degree zero (no edges going in or out of it) |
|
| Iteration Method to solve recurrence relation : |
In this method we simply continue to substitute back until we see a pattern of some sort. We then deduce a formula from the pattern. Once we discover a likely formula we prove that the formula actually solves the relation. |
|
| length : |
the number of edges appearing in the sequence of a path |
|
| loop (or sling) : |
where an edge joins a vertex to itself |
|
| Lower bound : |
It is the lower limit of growth rate that an algorith may have also, what is the best that can happen for a given data size. This is represented by Big-omega notation. |
|
| Maximal point : |
A pint p is said to be maximal if it is not dominated by any other point in the same set where p exist. |
|
| Merge sort : |
A divide and conquer technique based algorithm that combines several sorted (input) lists into a single sorted (output) list. It is an nlog n algorithm. |
|
| minimum path length : |
the path of minimum length between two vertices that are reachable from one another |
|
| mixed graph : |
a graph that consists of both directed and undirected edges |
|
| 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. |
|
| multigraph : |
a graph with multiple edges between the same vertices |
|
| null graph (or totally-disconnected graph) : |
a graph that contains only isolated vertices (a graph with no edges) |
|
| Omega notation : |
This notation is a mathematical notation used to describe the asymptotic behavior of functions . More exactly, it is used to describe an asymptotic lower bound only. |
|
| outdegree : |
the number of edges originating from a given vertex in a directed graph |
|
| parallel : |
where there is more than a single edge connecting two given vertices |
|
| parallel processing : |
A method of processing that can run only on a type of computer containing two or more processors running simultaneously. Parallel processing differs from multiprocessing in the way a task is distributed over the available processors. In multiprocessing, a process might be divided up into sequential blocks, with one processor managing access to a database, another analyzing the data, and a third handling graphical output to the screen. Programmers working with systems that perform parallel processing must find ways to divide a task so that it is more or less evenly distributed among the processors available |
|
| path : |
a sequence of edges that begins at an initial vertex and ends at a terminal vertex |
|
| Random access machine : |
A model of computation whose memory consists of an unbounded sequence of registers, each of which may hold an integer. In this model, arithmetic operations are allowed to compute the address of a memory register. |
|
| reachability : |
describes a relationship between two vertices in which one vertex is reachable from the other via a path |
|
| recurrence relation : |
Recurrence relation is a recursively defined function (an equation which is defined in terms of itself. ). Divide-and-conquer is an important design technique, and it naturally gives rise to recursive algorithms. Recurrence relation is used to express time complexity of a recursive algorithm. |
|
| Running Time : |
Time taken by an algorithm during execution called running time. |
|
| set : |
Definition: An unordered collection of values where each value occurs at most once. A group of elements with three properties: (1) all elements belong to a universe, (2) either each element is a member of the set or it is not, and (3) the elements are unordered. Formal Definition: As an abstract data type, a set has a single query function, isIn(v, S), which tells whether an element is a member of the set or not, and two modifier functions, add(v, S) and remove(v, S). These may be defined with axiomatic semantics as follows. new() returns a set isIn(v, new()) = false isIn(v, add(v, S)) = true isIn(v, add(u, S)) = isIn(v , S) if v ≠ u remove(v, new()) = new() remove(v, add(v, S)) = remove(v, S) remove(v, add(u, S)) = add(u, remove(v, S)) if v ≠ u where S is a set and u and v are elements. The predicate isEmpty(S) may be defined with the following additional axioms. isEmpty(new()) = true isEmpty(add(v, S)) = false Generalization (I am a kind of ...) |
|
| Sieve technique : |
It’s a divide and conquer based technique that applies to problems where we are interested in finding a single item from a larger set of n items. Like to fine kth element in a set.The sieve technique works in phases. |
|
| simple graph : |
a graph that contains no loops or parallel edges |
|
| simple path : |
a path in a directed graph in which all the edges are distinct |
|
| strongly-connected : |
describes the connectedness of a simple directed graph in which, for any two vertices, both vertices are reachable from the other |
|
| subgraph : |
if every edge of graph A is also an edge of graph B, then graph A is a subgraph of graph B |
|
| terminal vertex (or endpoint) : |
a vertex of degree one |
|
| total degree : |
the sum of the indegree and outdegree of a vertex |
|
| transport network : |
a connected, directed graph (with no self loops) that has only one vertex of indegree zero (the source), and one vertex of outdegree zero (the sink). Each edge is associated to a number which represents the limit to the rate of transportation of the product (called the capacity). |
|
| tree : |
a connected graph in which there is only one path connecting each pair of vertices |
|
| undirected graph : |
a graph in which every edge is undirected |
|
| unilaterally-connected : |
describes the connectedness of a simple directed graph in which, for any two vertices, at least one vertex is reachable from the other of the pair |
|
| Upper bound : |
It is the upper limit of growth rate that an algorith may have also, what is the worst that can happen for a given data size. This is represented by Big-oh Asumptotic notation. |
|
| vertex : |
a point or node in a graph |
|
| weakly-connected : |
describes the connectedness of a simple directed graph in which the direction of the edges is disregarded |
|
| weight : |
a number assigned to an edge |
|
| weighted graph : |
a connected graph in which a positive real number has been assigned to each edge |
|
| worst case : |
A scenario in which cost (possible use of resources) of an algorithm is maximum to process an input sequence called worst case |
|
