Home>>Resources

Glossary |
---|

Algorithm: Algorithm is a sequence of Finite and unambiguous computational steps that transform the input into the correct output effectively |

Algorithm Complexity: It can be represented in a number of ways. It is to give the idea about the resources required to run an algorithm. Most of the time the resources are time and space. |

Apriori Analysis: Analysis done at the stage of algorithms is called apriori analysis. |

Array: Array is a data structure containing similar data and elements are stored in contiguous memory locations. |

Assembly Language: It is the intermediary between the machine language and High Level language. It consists of English Macros. It is easier then machine language but difficult then high level language. |

Asymptotic Analysis: Asymptotic analysis means studying the behavior of the function when nà infinity or very large. |

Average Case Complexity: Average-case running times are calculated by first arriving at an understanding of the average nature of the input, and then performing a running-time analysis of the algorithm for this configuration. |

Big-Oh Notation: f(n) = O(g(n)) if there are positive constants c and n0 such that f(n) ≥ cg(n) for all n ≥ n0 and c>0 This notation is known as Big-Oh notation. |

Big-Omega Notation: f(n) = Ω(g(n)) if there are positive constants c and n0 such that f(n) ≥ cg(n) for all n ≥ n0. This notation is known as Big-Omega notation. |

Big-Theta Notation: f(n) = θ(g(n)) if there are positive constants c1, c2 and n0 such that c1g(n) ≤ f(n) ≤ c2g(n), for all n ≥ n0. This notation is known as Big-Theta notation |

Binary Search Tree: A binary search tree (BST) is a binary tree that has a key associated with each of its nodes.The keys in the left subtree of a node are smaller than or equal to the key in the node and the keys in the right subtree of a node are greater than or equal to the key in the node. |

Cache Memory: It can be internal or external cache memory. Internal cache memory is within the CPU while external cache memory is outside the CPU. L1 is internal cache and L2/L3 are external cache memory units. It is faster than RAM but size is smaller then RAM. Usually it ranges from 4 MB in home PCs to 128 MB in high end servers. |

Code Tuning: Code tuning is Used to write better code. It Needs better understanding of the programming language and its compiler. It Is equivalent of code optimization at Higher Language Level. |

Computer: A Computer is an electronic device, which takes some input from an input device, processes the input to some useful information, stores the information & sends the output to an output device. |

Data Structure: Data structure is a way to store and organize data in order to facilitate access and modifications |

Empirical: First write a program implementing the algorithm and run the program with inputs of varying size and composition. Draw the results as a graph. This type of analysis is called empirical analysis of the algorithm. |

External Node: node without children is called external node. |

Giga Byte: Consisting of 2^{30} bytes of memory or 1024 MB of Memory |

High Level Language: These are English like languages in which it is very easy to program. Very large amount of code can also be easily handled by these languages. These are very easy to understand and debug. |

Input Device: The most common input device of a typical computer is keyboard. The other input devices are mouse, joystick, scanner, magnetic ink character reader, voice input systems, digital cameras, light pen, and touch screen etc. |

Internal Node: node with at least one child in called internal node. |

Kilo Byte: Consisting of 2 |

Link List: Link list is a concrete data structure consisting of a sequence of nodes. Each node stores element and link to the next node. There may be a header link and trailer link. |

Macro Analysis: It deals with selective instructions which are dominant & costliest. Selection of right instructions is very important. |

Max-Heap : A max heap is a complete binary tree such that for each node, the key value in the node is greater than or equal to the value in its children. |

Mega Byte: Consisting of 2^{20} bytes of memory or 1024 KB of Memory |

Memory Hierarchy: It refers to the various levels of memory devices available for processing of data. These range from high speed registers in the CPU at one side to the external memory devices like CD, DVD on the other side. |

Micro Analysis: To count each and every operation of the program is called micro analysis. It is detailed, takes more time and is complex and tedious. |

Output Device: The most common output device of a typical computer is Monitor. Other output devices are printer, television, speakers, multimedia projector etc. |

Posterior Analysis: Any analysis done after writing the program in a specific language is called posterior analysis. |

Queue: It is a data structure of type first in first out. Insertions and deletions follow the first-in first-out scheme. Insertions are at the rear of the queue and removals are at the front of the queue. |

Siblings: Children of the same parent are called siblings. |

Sparse Matrix: A matrix is sparse if a large number of its elements are 0 or empty. |

Stack: It is a data structure of type Last in First out, in and out only from one end, other end is closed. |

Storage Device: Storage devices are those devices that store data for later use. Most common devices are floppy, CD, hard disk, magnetic tape, magnetic drum and DVD etc. |

Sub Tree: Tree consisting of a node and its descendants is called sub tree. |

Tera Byte: Consisting of 2^{40} bytes of memory or 1024 GB of Memory |

Tree: In computers, a tree is an abstract model of a hierarchical structure. A tree consists of nodes with a parent-child relation. |

Worst Case Complexity: It is the maximum time an algorithm will take on a given input size. |