Data Structures

Front 1

Stack

Back 1

A collection of objects that are inserted and removed according to the LIFO principle

Front 2

Queue

Back 2

A collection of objects that are inserted and removed according to the FIFO principle

Front 3

Amortized Analysis

Back 3

To answer the question, "If the algorithm is run several times, what is the average time per run, given the worst possible sequence of runs?"

Front 4

Tree

Back 4

An abstract data type that stores elements hierarchically

Front 5

Binary Tree

Back 5

An ordered tree whose nodes have at most two children

Front 6

Proper Binary Tree

Back 6

A binary tree with either zero or two children

Front 7

Priority Queue

Back 7

An abstract data type for storing a collection of elements that supports arbitrary element insertion but removal of elements is based on priority

Front 8

Entry

Back 8

A key-value pair

Front 9

Heap

Back 9

An efficient realization of a priority queue allowing insertion removal in logarithmic time

Front 10

Complete Binary Tree

Back 10

A binary tree in which every level except perhaps the last is full, and the nodes are as far left as possible

Front 11

Map

Back 11

A collection of key-value pairs, where each key is unique

Front 12

Sentinel

Back 12

Returned value when no key equal to k is found, many times null is used

Front 13

Hash Table

Back 13

Map implementation consisting of a bucket array and a hash function, good if you have an idea of maximum size

Front 14

Hash Function

Back 14

Maps each key k in our map to an integer

Front 15

Collision

Back 15

When two or more keys are mapped to the same hash value

Front 16

Compression Function

Back 16

Maps the hash code to an integer within range

Front 17

(int) ((i >> 32) + (int) i)

Back 17

Summing components hash code, best used for base types such as long and double

Front 18

Polynomial Hash Codes

Back 18

Hash code that takes order into consideration, avoiding "pots" vs "stop" collisions, and is used as the default Java Implementation for strings

Front 19

Cyclic Shift Hash Code

Back 19

Variant of Polynomial hash code, where a is replaced by a partial sum

Front 20

i mod N

Back 20

Division method compression function (integer i to size of bucket array N)

Front 21

((ai+b) mod p) mod N

Back 21

MAD compression function

Front 22

Ordered Search Table

Back 22

Map implementation that stores the map's entries in an array list in increasing order of keys, guaranteed worst time

Front 23

Separate Chaining

Back 23

Collision handling scheme where all entries hashed to i are stored together using a list based map

Front 24

Linear Probing

Back 24

Collision handling scheme where while bucket i is full, it is placed in the i+1 bucket

Front 25

Search Tree

Back 25

Trees that can be used to implement a map

Front 26

Binary Search Tree

Back 26

Binary tree where nodes in the left subtree are equal to k, and nodes in the right subtree are greater than k

Front 27

AVL Tree

Back 27

Binary tree for which the heights of the children of any internal node differ at most by 1

Front 28

Quick Sort

Back 28

A divide and conquer algorithm with the hard work, comparison, done in the divide stage. Easily done in-place

Front 29

Spanning Sub-Graph

Back 29

Sub-graph that contains all the vertices

Front 30

Spanning Tree

Back 30

Spanning sub-graph that is also a tree

Front 31

Forest

Back 31

Graph with no cycles

Front 32

Connected Graph

Back 32

Graph with all pairs of vertices connected by at least one path

Front 33

Tree

Back 33

A connected forest

Front 34

Connected Component

Back 34

The maximal connected sub-graph of a unconnected graph