Data Structures And Algorithms

Front 1

Stack

Back 1

FILO

O(1)

Front 2

Queue

Back 2

FIFO

O(1)

Front 3

Vector

Back 3

array

has rank

circular?

slow to change, fast to access

Front 4

List

Back 4

DLL or SLL

awareness of "before" and "after"

fast to manipulate, slow to access

Front 5

Sequences

Back 5

methods of List and vector, implementation can vary

Front 6

Tree implementation (vector)

Back 6

layers from top to bottom, children are 2xrank and + 1 for right child

Front 7

Euler tour

Back 7

general tour for traversing a tree

Front 8

priority queue

Back 8

sorted queue with rank or weight

total order relation

can return smallest key

Front 9

Heap

Back 9

parent < children

always balanced -> O(logn)

binary tree implementation or array

bottom up construction takes O(n) because of maximum path

Front 10

Selection Sort (for PQ)

Back 10

retrieves the smallest item from a sequence.

Runs in O(n^2)

Front 11

Insertion Sort (for PQ)

Back 11

places each item sortedly in the sequence

runs in O(n^2) but not always

Front 12

Heapsort

Back 12

implementing the sequence as a heap.

each insertion is logn, and retrieving is also logn. For n items, becomes nlogn

in place in an array shifting the "barrier" between heap and unsorted sequence

Front 13

Dictionary

Back 13

umbrella for sorted search methods

KEYS

has methods for key before and key after

Front 14

Lookup Table

Back 14

sorted array

with binary search: logn access

Front 15

Binary Search Trees

Back 15

left < parent < right

search is O(h)

insertion: trivial

removal: take left most node of right-subtree and replace (if has leaf node, just delete)

Front 16

AVL

Back 16

balanced tree

logn access

Front 17

AVL proof of height

Back 17

looking at number of nodes stored when balanced with respect to height.

n(h) > 2 * n(h-2) (always more nodes than this)

so logn

Front 18

AVL insertion

Back 18

insert in correct location

find z if unbalanced, y and z are children

determine abc, switch around

constant time

Front 19

AVL deletion

Back 19

delete: basic if leaf node, otherwise left most node of right subtree becomes node

z is first unbalanced, y and x are children of subtree with LARGER HEIGHT

logn steps worst case

Front 20

Merge Sort

Back 20

splitting into two parts, recursively sorting, then merging

Merging: smallest object of each, proceed, merge takes O(n1+n2)

total nlogn

Front 21

Sets (merging)

Back 21

smallest element from the front of both sorted parts, when one runs out, just let the other one finish

Front 22

QuickSort

Back 22

3 parts: less than pivot, pivot, greater than pivot

recursively sort

random pivot selection: expected runtime nlogn

worst is still n^2

Front 23

in place quicksort

Back 23

pivot and flipping elements over the pivot if smaller

Front 24

Bucket sort

Back 24

O(n + N)!!!

place all elements into buckets

then remove from buckets

Front 25

Radix Sort

Back 25

lexicographically sorting pairs

from back to front

runs O(d(n+N)) with d being the length or depth of sorting

Front 26

divide and conquer

Back 26

solving distinct sub-problems and then combining

Front 27

integer multiplication (D&C)

Back 27

splitting large and small orders

expanding the multiplication

using a substitution for the mixed part, then storing answers and O(n^1.585)

Front 28

Dynamic programming

Back 28

similar to DC bt more powerful

subproblems can overlap - store solutions

3 properties:

- must be able to break problem down

- optimal subproblems must give optimal solution

- overlapping is GOOD

Front 29

DP example change of coins

Back 29

building network from the bottom up

storing solutions and using them later

Front 30

Graph

Back 30

vertices and edges

directed

cycles

Front 31

Spanning tree

Back 31

of a connected, undirected graph is a subgraph with all vertecies but no cycles and is fully connected

Front 32

Graph important methods

Back 32

isAdjacent(v,w), adjacentVertices(v)

deleteVertex(v)

these will be compared frequently

Front 33

Structures

Back 33

Edge List

Adjacency List

Adjacency Matrix

Front 34

Edge List

Back 34

vertices are objects in list

edges are objects in container, link to vertices

runtime mostly O(E)

Front 35

Adjacency List

Back 35

builds on Edge list,

Vertex now contains container of edges to link to, and edges link to that container

runtime now dependent on deg(v) or minimum of deg(u),deg(v)

Front 36

Adjacency matrix

Back 36

builds on edge list,

edges are stored in a vertex matrix, each vertex has an index

null = no link, object = link present

areAdjacent no O(1), rest in n and space O(n^2)

Front 37

DFS BFS

Back 37

both take O(V + E) time

Front 38

DAG

Back 38

directed, acyclic graph

can find topological ordering

Front 39

topological ordering of DAG

Back 39

enqueue with in-degree 0

dequeue with 0, reduce all linked vertices in-degree and store its rank. Repeat with new vertices that are no 0

O(V+E)

Front 40

Strings algs

Back 40

Brute Force

BM - Last occurence function

KMP - Failure Function

Front 41

Boyer Moore

Back 41

scanning from back of pattern

last Occurence function for each letter in alphabet

jumpy by according m to align or entire length if not in pattern or 1 if neither

still O(mn)

Front 42

KMP

Back 42

Failure Function:

- length of prefix that is suffix of current position

i and j counter, j updated by F(j-1) if j > 0 otherwise j = j + 1

O(m + n)

Front 43

Trie

Back 43

standard -> compressed -> compact

use special character to deal with prefix

Front 44

standard trie

Back 44

O(n) space where n is the total length of all strings

height is longest string

finding string: O(dm) - note not dependent on n

Front 45

compact trie

Back 45

space is O(s) where s is the number of strings

Front 46

suffix trie

Back 46

all suffixes of a potential trie, compactable

pattern matching O(dm) with d being length of alphabet

Front 47

1D range tree

Back 47

findall in O(logn + s)

O(n) space

Front 48

2D range search

Back 48

auxiliary structures are subtrees root v sorted with y

Range search: O(log^2 n + s)

Space nlogn (getting worse)

Front 49

QuadTree

Back 49

region in quads, can be greatly impalanced

O(sqrt(n) + s) for 2D

Front 50

k-D tree

Back 50

point or region based. point is balanced, height logn

nearest neighbour is O(n) worst but O(logn) expected

Front 51

DFS / BFS running time

Back 51

O(V+E)

Front 52

DAG sorting

Back 52

O(V+E)

Front 53

k-D tree building time

Back 53

O(knlogn)