"Defined ITS 116"

Kind of Data structure

Definition of Stack

• A stack is a data structure that allows items to be added and removed from one end. That's why it's also described as a LIFO stack. Last In First Out. A stack can be directly compared to some real-life objects. For example, a stack of trays. Trays are only added and removed from the top. A stack of exercise books can also be used as another analogy. Students only take away or pass up exercise books from the top.

Definition of Dictionary

• An abstract data type storing items, or values. A value is accessed by an associated key. Basic operations are new, insert, find and delete.
  Formal Definition: The operations new(), insert(k, v, D), and find(k, D) may be defined with axiomatic semantics as follows.
  new() returns a dictionary
  find(k, insert(k, v, D)) = v
  find(k, insert(j, v, D)) = find(k, D) if k ≠ j

where k and j are keys, v is a value, and D is a dictionary.

Definition of Bag

• An unordered collection of values that may have duplicates.
  Formal Definition: 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.

Definition of Set

• 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.

Definition of Graph

• In computer science, a graph is a kind of data structure, specifically an abstract data type (ADT), that consists of a set of nodes (also called vertices) and a set of edges that establish relationships (connections) between the nodes. The graph ADT follows directly from the graph concept from mathematics.
  Informally, G=(V,E) consists of vertices, the elements of V, which are connected by edges, the elements of E. Formally, a graph, G, is defined as an ordered pair, G=(V,E), where V is a set (usually finite) and E is a set consisting of two element subsets of V.

Definition of Buffer

• In computing, a buffer is a region of memory used to temporarily hold data while it is being moved from one place to another. Typically, the data is stored in a buffer as it is retrieved from an input device (such as a keyboard) or just before it is sent to an output device (such as a printer). However, a buffer may be used when moving data between processes within a computer. This is comparable to buffers in telecommunication. Buffers can be implemented in either hardware or software, but the vast majority of buffers are implemented in software. Buffers are typically used when there is a difference between the rate at which data is received and the rate at which it can be processed, or in the case that these rates are variable, for example in a printer spooler.

Definition of Hash Table

• In computer science, a hash table, or a hash map, is a data structure that associates keys with values.
• The primary operation that hash functions support efficiently is a lookup: given a key (e.g., a person's name), find the corresponding value (e.g., that person's telephone number). It works by transforming the key using a hash function into a hash, a number that is used as an index in an array to locate the desired location ("bucket") where the values should be.
  In most cases the hash function is deliberately chosen to have pseudo-random properties, so that small changes of key gives a large and apparently random effect (although of course reproducible effect) on the hash returned. Because of this random effect in some cases the calculated index can be the same for two different keys (a "collision"); different hash table designs handle this issue in different ways.

Definition of Skip List

• A skip list is a probabilistic data structure, based on multiple parallel, sorted linked lists, with efficiency comparable to a binary search tree (order log n average time for most operations).
  Underlying the skip list is an augmentation of an ordered linked list with additional forward links, added in a randomized way with a geometric/negative binomial distribution [1], so that a search in the list may quickly skip parts of the list (hence the name). Insert, search and delete operations are performed in logarithmic randomized time.

Definition of Bitboard

• A bitboard, often used for boardgames such as chess, checkers and othello, is a specialization of the bitset data structure, where each bit represents a game position or state, designed for optimization of speed and/or memory or disk use in mass calculations. Bits in the same bitboard relate to each other in the rules of the game often forming a game position when taken together. Other bitboards are commonly used as masks to transform or answer queries about positions. The "game" may be any game-like system where information is tightly packed in a structured form with "rules" affecting how the individual units or pieces relate.

Definition of Priority Queue

A priority queue is an abstract data type in computer programming that supports the following three operations:

• InsertWithPriority: add an element to the queue with an associated priority
• GetNext: remove the element from the queue that has the highest priority, and return it (also known as "PopElement(Off)", or "GetMinimum")
  PeekAtNext (optional): look at the element with highest priority without removing it