Over View - Summary IT PDF

Preview

Summary

Summary for comp2521...

Description

COMP 2521 Overview - By DueApe Trees A tree is a widely used abstract data type (ADT)—or data structure implementing this ADT—that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes. Some structures are: AVL Tree, Binary Search Tree, 2-3-4 Tree, Splay tree

Graph A graph is an abstract data type that is meant to implement the graph and hypergraph concepts from mathematics. A graph data structure consists of a finite (and possibly mutable) set of ordered pairs, called edges or arcs, of certain entities called nodes or vertices. Some graphic operation algorithms are: BFS(Breadth-first search), DFS (Depth-first search)

Hashing A hash function is any function that can be used to map data of arbitrary size to fixed-size values. The values returned by a hash function are called hash values, hash codes, digests, or simply hashes.

Heaps A heap is a specialized tree-based data structure which is essentially an almost complete tree that satisfies the heap property: in a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C. The node at the "top" of the heap (with no parents) is called the root node.

Generic ADTs Abstract Data type (ADT) is a type (or class) for objects whose behaviour is defined by a set of value and a set of operations. The definition of ADT only mentions what operations are to be performed but not how these operations will be implemented. It does not specify how data will be organized in memory and what algorithms will be used for implementing the operations. It is called “abstract” because it gives an implementation-independent view. The process of providing only the essentials and hiding the details is known as abstraction.

Sorting Algorithms A Sorting Algorithm is used to rearrange a given array or list elements according to a comparison operator on the elements. The comparison operator is used to decide the new order of element in the respective data structure. Famous algorithms are: Selection sort, Insertion sort, Merge sort, Quick sort, Heap sort, Shell sort

Text Processing Algorithms Algorithms used for text processing like substring search, famous algorithms are: Boyer–Moore algorithm, Knuth–Morris–Pratt algorithm 1...