title: Data Structures Notes author: Haroon Ghori

geometry: margin=1in
Wrapper Classes

java primative types

int
double
char
float
long
byte
boolean
Wrapper Classes
int => Integer
double => Double
char => Character
...
Wrapper classes are instantiable classes that correspond to primitive data types.
Autobox - primitive types can be automatically be converted to wrapper classes when needed.

Generics

Creates a "generic" methods and classes that work with unspecified data types.
Generic method header

public static <T> <returnType> methodName(T thing)

Generic class header

public class myDoubleGen<T1, T2>

Implementing Generics
You cannot implement an array of generics directly
T[] ra = new T[n] (not allowed)
T[] ra = (T[]) new Object[n] (allowed)
Any type <T> can fit into a generic type so long as it's an instantiate class (eg Wrapper Class)
we must use <T> = Integer instead of <T> = int

Java Collections Framework

Collection - an object that groups multiple elements in a single unit

typically data items that form a "natural" group
Collections Framework - a unified architecture for representing and manipulating collections.
List<T> extends Collection<T>
for manipulating a sequence of values
adds positional operations for indexing into a Collection
al elements occupy a numbered position
positions of N elements go from 0 to N-1 methods
 get(where)
indexOf(item)
set(where, item)
add(where, item)
remove(where)
Set<T> extends Collection<T>
Unordered, unique "set" of values
SortedSet<T> extends Set<T> introduces ordering
Queue<T> extends Collection<T>
usually "first in first out" (FIFO) but could be priority queue
adds to end, removes and "peeks" at beginning methods
push()
peek()
pop()
A deque is a double ended queue
Collection<T>
int size()
void clear()
boolean isEmpty()
boolean contains(T o)
boolean add(T)
Map<K,V> (maps are not collections)
stores key/value pairs
each pair is an entry (nested class)
K is the key, V is the value
key must be unique
key could be paired with a collection which includes multiple values
Implementations
List<T>
ArrayList<T>
LinkedList<T>
Set<T>
SortedSet<T>
TreeSet<T>
Map<K, V>
HashMap<K,V>
TreeMap<K,V>
LinkedMap<K,V>

Abstract Data Types

Data type - a collection of values and the operations that can be applied to them
Interface
Gives you a list of operations (method headers) that can be performed on a data type, but doesn't define what they do /
how they work. Tells the programmer how the user can interact with the object, but leaves the definitions to the
programmer.
Implementation
Defines the methods (interactions) in the interface.
Equivalence Relation
A relation ~ over a set S is a set of pairs of items from S
Note '~' represents a relation
 write x~y to indicate that {x,y} exists in ~
A relation ~ over a set S is an equivalence relation if it is
reflexive
for al x E S, x~x
symmetric for all x,y E S, xy implies yx
transitive
for all x,y,z E S, xy and yz implies x~z
An equivalence relation ~ over the set S partitions S into disjoint (non overlapping) subsets
two elements in the same subsets are considered equivalent with respect to ~
Dynamic Equivalence Problem
Sometimes we need to modify the equivalence relation as we go, changing the partition
the formerly disjointed sets get combined
Given n equivalence relation over S and two items from S, how can we determine if the elements are equivalent.

Bag

Basically a Set (from the java collections framework) but duplicates are allowed.
Order doesn't matter
Size doesn't matter
Operations
create
add
clear
size
isEmpty
remove
list
contains
Unlike sets Bags do not have union, intersection, and setDifference methods

Partition

a collection of disjoint subsets

begins with every element in its own subset
the subsets are then repeatedly joined via a union operator
Simplify names
let N be the number of items in a structure
then we assume that the names of the items in our structure are {0, N-1}
A Structure with a Quick Union Method
to start each item is in it's own set named with its own name
use an array to store names of sets
position i holds the name of the set that contains item i
performing find(x)
return array
takes O(1) time
constant time
very fast
performing union(a, b)
find(a) to learn i, the name of 'a's set
find(b) to learn j, the name of 'b's set
Go through the array and replace all 'j's with 'i's
O(N) time
A Structure with a Quick Union Method
 Use a tree to represent each set with the root being the name of the set
one "top" element is called the root with related elements branching "below"
elements with no branches are called leaves
each node keeps track of it's parent
tree is represented by an array where array[i] gives the parent of item i -array[0] = -1 since root has no parent
performing find(x)
check arrray
if array == -1
return x
else
check array[array ]
repeat until we find the root (name) of the set
performing union(a, b)
find(a) to find the root of a
find(b) to find the root of b
set a[b] to b
the b is the parent of a
use union-by-size
set the root value for b to be -size(b).
then search for any negative number instead of -1 when performing find(x)
then always attatch the smaller tree to the larger toree to keep trees small.
then no tree can have depth greater than log(N)
use path compression
when performing find(x) set all nodes between x and the root to point to the root. Compresses all paths such that
find(x) becomes much faster

Iterators

An object that allows us to access each element in a collection in turn. Interfaces

Iterator
Iterable
Defines a collection that is iterable
Iteratiors do not neccesarily operate in order. They just garuntee that every element in the iteration will be selected.
An iterator's remove() method is optional. Calling it might result in an UnspportedOperationException
Modifying a collection while an iterator is in use can cause problems.
When detected will throw a ConccurrentModificationException. Happens often when remove() is called.

Linked List

Collection with discontinuous memory allocation

capacity is not fixed
each element "points" to the next element in the list (Singly linked list)
thus each element (called a node) must have a data part and a next part
the final node's next part points to null
the pointer to the beginning of the list is called the head pointer
the pointer to the end of the list is called the tail pointer
each element points to the next and previous element in the list (Doubly linked list)
stores twice the ammount of data, but very useful

Stack

Last In First Out (LIFO) structure. User has no access to inner elements
Modifications to stack only occur at the end (called the top)
Operations
void push(T items)
adds an item to the top of the stack
T pop()
removes the top item
T peek()
returns the top item
int size()
returns the stack's size
boolean isEmpty()
returns whether or not the stack is empty

Queue

First In First Out (FIFO) structure. User only has access to first element and can only add to the end.
Operations
void enquee()
adds to the end of the queue
T dequeue()
removes from the front of the queue
T front()
returns the first element
int size()
returns the size of the queue
boolean isEmpty()
returns whether or not the queue is empty
Deque
Similar to queue, but the user can add or remove from the beginning or end
Operations
void addFront(item)
adds to the front of the deque
void addBack(item)
adds to the back of the deque
T removeFront()
removes from the front of the deque
T removeBack()
remmoves from the back of the deque

Hash Table

Collection in which items are stored in a table

Location of a particular item is determined by a "hash function" instead of position relative to rest of the data
if a hash function maps two items to the same location we call this a hash colision.
ideally a hash function will provide O(1) access time
Java has built in Hash Functions for general classes (String, Integer, etc), but sometimes it is useful to write your own functions.
typically we create a table of size 'm' with indices [0, m-1].
then if x = Hash(item) we reduce x % m such that it will fit in the table
Collision Resolution
Seperate chaining
use seperate linked list for each bucket
Open adressing strategies
items don't always get added to their ideal location
 Linear Probing
find index = Hash(x) % M
check if index is empty
if index is empty, add item to index
if index is not empty
for K = 0, 1, ... M-1 if (index + K) % M is empty insert item in (index + k) and end loop
For this strategy to be eficient the table needs to have a lot of empty space. (M > what we really "need"). Then
theoretically there will be empty spaces where collision-items can be added close to their "actual" space (as per the
Hash function) which maximizes search efficiency.
Search(item)
Find index = Hash(item)
check index
if Table(index) = item return
else
for k = 0, 1, M-1 if Table(index + k) == item, return else if Table(index + k != null), keep searching else if
Table(index + k == null), return

Trees

node, root, internal, external (no children = leaf)

parent, child, sibling, ancestors, descendents

edge, path

Edge is a link between two nodes

Path is the set of edges between two nodes. The path length is the number of edges between two noeds

depth of node

root=0, 1+depth(parent),

height of node

leaf=0, 1+max child height

ordered tree:

children of a node are ordered, ie, book TOC

Tree Algorithms

compute depth of node

compute height of node (two methods)
traversals
breadth-first
depth-first
preorder
postorder
int size()
O(1)
boolean isEmpty()
O(1)
Iterable<E> breadthFirst()
Iterable<E> preOrder()
Iterable<E> postOrder()
Binary Trees

every node has at most 2 children (called left & right usually)
depth-first traversals:
Pre-Order
Check root, then left subtree, then right subtree
Post-Order
Check left subtree, then right subtree then root
In-Order
Check left subtree, then root, then right subtree

Binary Tree Properties

Every node has at most 2 children

assume n nodes, height h:
h<n
log n <= h because n <= 2^(h+1) - 1 = sum (i=0,h) 2^i
nodes at depth i <= 2^i
Proper Binary Tree
All nodes have 0 or 2 children
Complete Binary Tree
Full from top to bottom, left to right
h <= log(N)
Balanced Binary Tree
difference in height of left and right subtrees is at most 1

Binary Tree Implementations - Recursive Linked Structure: - Bnode has T data, Bnode parent, Bnode left, Bnode right - Ranked
Sequence Representation: - Use array, waste slot at index 0 - Root goes into index 1 - Left child of node at i is at index 2i - Right child
of node at i is at index 2i+1 - Parent of node at i is at index i/2 (integer division)

Binary Search Tree

A binary tree where items are placed into the tree based on their value.
Algorithms
Find K

def find(k, root):

if (root == null):
return false
if (k == [Link]):
return true
else if (k < [Link]):
return find(k, [Link])
else:
return find(k, [Link])

Insert K
 def insert(k, root):
if (root == null):
return new Node(k)
if (k < [Link]):
[Link] = insert(k, [Link])
else:
[Link] = insert(k, [Link])

Remove K

def remove(k, root):

if (k < [Link]):
[Link] = remove(k, [Link])
else if (k > [Link]):
[Link] = remove(k, [Link])
else:
if ([Link]): #leaf
return null
else if ([Link] != null && [Link] == null): #only right child
return [Link]
else if ([Link] == null && [Link] != null): #only left child
return [Link]
else:
curr = findMin([Link])
#delete minimum on the right
[Link] = [Link]([Link], [Link])
[Link] = [Link]
return root

Example: arithmetic expression evaluation

Consider this arithmetic expression: (1+2) * -6 - 2 * (14/5)
This binary tree represents it and can be used to compute the result:

-
/ \
* *
/ \ / \
+ - 2 /
/ \ \ / \
1 2 6 14 5

in-order traversal for fully parenthesized in-fix form: \((((1+2)*(-6))-(2*(14/5)))\)

pre-order traversal generates pre-fix notation: - * + 1 2 - 6 * 2 / 14 5
post-order traversal generates post-fix notation: 1 2 + 6 - * 2 14 5 / * -

AVL Tree

An AVL tree is a binary search tree which must maintain the Height Balance Property
The absolute value of the difference between the heights of any node's children must be less than or equal to one.
insert, search operations are O(log N)
Algorithms
 insert
insert item as in binary search tree
starting with new node, go up to update heights
if find a node that has become unbalanced
do restructure to rebalance
rebalance reduces height of subtree by 1, so no need to propagate up
O(log n)
remove
start as with binary search tree
ancestor of deleted node (not replaced node) may become unbalanced
go up from deleted node to find first unbalanced
do rotation - may reduce the height of the subtree
propagate/check upward to root!
O(log n)
balance
Check root
If left-left imbalance, do right rotation
If right-right imbalance, do left rotation
If left-right imbalance, do left then right rotation
If right-left imbalance, do right then left rotation

Priority Queue

A data structure, similar to a queue which gets objects with maximum priority.
Entry object: (key, value) pair, keys must be comparable
main methods:
insert(entry)
removeMin()
min() (get)
Hash table: fast inserts depending on collisions
Good if there are lots of different priorities
Balanced binary search tree
Operations are log(N)
(circular) ordered array
O(N) to insert
O(1) for findMin and deleteMin
Unordered array
O(1) to insert
O(N) for findMin, deleteMin
Note that ordered/unordered arrays could be linked lists too
Heap
complete binary tree:
 N nodes, height log N
full except for rightmost last level
last node corresponds to level numbering
order property:
every node key (priority) <= it's childrens' keys (priorities)
Implimentations
Ranked Sequence array rep of complete binary tree
level numbering:
f(v) = 1 if root
left child = 2f(parent(v))
right child = 2f(parent(v)) + 1
root, parent, leftChild, rightChild, isInternal, isExternal, isRoot
iterator methods for elements, positions, children
worst case array size = N
Algorithms
Insert Algorithm - add next leaf node according to next open spot - bubble value up based on priority.
Time Complexity
Add O(1)
Bubble Up O(log(N))
FindMin
Algorithm
get root value
Time Complexity
O(1)
DeleteMin
Algorithm
returns root
moves last leaf value to root
bubble root value down based on priority
Time Complexity
remove root O(1)
find last
Array O(1)
Tree O(log(N))
Bubble Down O(log(N))
Bubble Up (minimum heap)
Algorithm

def bubbleUp(index): #based on array implimentation

if (index <= 1): #at root
return;
val = [Link](index)
parent = [Link](index / 2)
#if value has lower priority than parent, swap
if (val < parent):
[Link](index / 2, val)
[Link](index, parent)
bubbleUp(index / 2)
return;

Time Complexity
 O(log(N))
Bubble Down (minimum heap)
Algorithm

def bubbleDown(index) #based on array implimentation

if (2 * index > [Link]): #at a leaf
return
val = [Link](index)
childIndex = [Link](index)
if (childIndex < 1)
return
child = [Link](childIndex);
#swap if value has higher priority than child, swap
if (val > child):
[Link](index, child)
[Link](childIndex, val)
bubbleDown(childIndex)
return

Time Complexity
O(log(N))
Bottom Up Build
Algorithm
Put all values in array
Starting at height h - 1 check each value and bubble down if neccesary
Go to next level and repeat until the root has been reached
Time Complexity
O(N)
Top Down Build (Standard Build)
Algorithm
Create empty heap
Add values one by one, bubble up as needed
Time Complexity
O(Nlog(N))

Graph

Terminology
N vertices (nodes) connected by M edges (lines)
Degree of vertex is number of incident edges
Adjacent vertices u and v (edge (u, v) exists) are called neighbors
directed
edges that go in one direction (from u to v, but not v to u)
undirected
edges taht go in both directions (from u to v and v to u)
Path from u to v is a sequence of edges starting at u that take you to v, with no repeated edges (path length = number of edges
on it)
Cycle in a graph: a path of length at least 1 whose first and last vertices are the same
Connected graph G: there is a path in G from every vertex to every other vertex
Acyclic graph
A graph with no cycles
Tree
 An acyclic connected graph
Forest
A disjoint set of trees
Subgraph of G
Subset of graph G’s edges (and associated vertices)
Spanning tree of a connected graph G
A subgraph that contains all of G’s vertices and is a single tree
Implimentations of Graph
Edge List
List of ordered pair edges (u, v)
Adjascency List
A linked structure containing the vectors, linked to its neighbors Example

[A] -> E -> F

[B] -> A -> N
[C] -> M -> P
...
[Z] -> B -> C

Adjascency Matrix
Two dimensional boolean or integer array of indicating when there's an edge between vectors u and v Example

A B C .. Z
A
B
C
...
Z

Algorithms
Traversals and Searhes
Breadth-first
Approximates level-order tree traversal
Move one level further away from starting vertex during each round
Depth-first
Generalization of pre-order tree traversal
Find longest path from start that you can without repeating vertices, then backtrack as needed to try di↵erent
long paths until you reach all vertices
Topological Sort
Goal: order the vertices of a directed, acyclic graph in some sequence so that for each edge (u, v) in the graph, vertex u
appears earlier in list than vertex v
Note that a vertex's indegree is the number of edges leading to the vertex
a vertex's outdegre is the number of edges leading away from the vertex Algorithm def topologicalSort():
Collection collection = new List() while (![Link]): v = findVertexInDegreeZero() if (v == null): return
#graph must have cycle, so abort [Link](v) [Link](v)
Shortest Path Problems
Single Source, Unweighted Graph (Breadth First Search)
 def unweightedBestPath(start):
for (v in graph):
dist[v] = infinity
prev[v] = null
dist[start] = 0
prev[start] = -1
//Perform a breadth-first traversal to process nodes
[Link](start)
while queue is not empty
x = [Link]()
For (each v in neighbors(x) && prev[v] == null):
dist[v] = dist[x]+1
prev[v] = x
[Link](v)

Time Complexity
O(V + E)
Single Source, Weighted Graph (Dijkstra's Algorithm) = ```Python def weightedBestPath(start): for each v in graph:
dist[v] 1 prev[v] null found[v] false dist[start] = 0 prev[start] = -1 for i in range (0, V): x =
getUnfoundVertexWithMinDistance() found = true for each v in neighbors(x): if (dist + weight[(x, v)] < dist[v]):
dist[v] = dist + weight[(x, v)] prev[v] = x

- Time Complexity
- O(N^2)

All Sources Graph

Run single source path algorithm V times
Time Complexity
O(N^3)
Minimum Spanning Tree
Find the tree that connects all vertices in the graph with the least total cost.
Prim's Algorithm
Similar to Dijkstra's algorithm. Starts at a source vector and finds the minimum cost path to each other
vector
 def prim(start):
Graph newGraph = new Graph()
for each v in graph:
dist[v] = infinity
prev[v] = null
found[v] = false
dist[start] = 0
prev[start] = -1
for i in range (0, V):
x = getUnfoundVertexWithMinDistance()
found[x] = true
[Link](x)
for each v in neighbors(x):
if (weight[(x, v)] < dist[v]):
dist[v] = weight[(x, v)]
prev[v] = x

Time Complexity
O(N^2) or O(Mlog(N))
M is the number of edges, N is the number of vertices
Kruskal's Algorithm
Finds the smallest edge and adds to the tree if adding that edge doesn't create a cycle.
Algorithm

def kruskal():
Graph newGraph = new Graph()
Heap heap = new Heap() #minHeap
for each edge in graph:
[Link](edge)
while (![Link]):
e = [Link]()
if ():
[Link](e)

Time Complexity
O(Mlog(N))
M is the number of edges, N is the number of vertices

Skip List

series of ordered levels, each a doubly linked list with sentinels

L0 has all the elements
Li has on average 2^(log n - i) elements = n/2^i
Lh (top level) has sentinels
each entry has collection of links to go across and down
good choice in practice for sets, maps, dictionaries
search & update methods are O(log n) expected time (probabilistic analysis)
uses randomization
Operations
find K
start at top leftmost position (-inf)
 while pos != null
skip forward to largest key <= K
move down 1 position
insert K
do (skip)search to find position in L0
insert K in L0
flip coin to decide if insert K in next level
keep flipping and inserting up until no
remove K
do search (find) to find position in L0
remove from each level as you search downward

Example

Lh: s e
L3: s 17 42 e
L2: s 17 31 42 55 e
L1: s 12 17 31 38 42 44 55 e
L0: s 12 17 20 31 38 39 42 44 50 55 e

Treap

Each key is given a random priority and inserted as in a binary search tree (not balanced. The nodes are rotated so that the priorities
form a (max)heap
The idea is to use random priorities to roughly rebalance tree
Operations
find K
do standard binary tree search ignoring priorities
insert K
generate random priority for key K
binary search where the new leaf for K belongs (BST on keys)
while new node has higher priority than parent, rotate nodes
delete K
if K is at leaf node, just remove
if K has one child, replace with child
if K has two children, do like BST remove and then fix heap property:
swap K node with key order successor, rotate to restore heap
alternative: find K, change priority to -1, rotate down to leaf then remove

Splay Tree

These are an alternative Binary Search Tree implementation of a map, dictionary or set where elements are moved up to the root each
time they are accessed so that their next access is faster. This is still a binary search tree, but not necessarily balanced.
Splaying
rotations after every operation (including find) to move accessed node to root:
zig (if accessed node is child of root)
zig-zag (like double AVL rotation (LR or RL))
zig-zig (2 single rotations: parent-grandparent first, then child-parent)
continue splaying upwards until the splayed node is the root
which node to splay:
find: found node or leaf where search ends (if not found)
insert: inserted node
 remove: parent of actual leaf node that gets removed
complexity
O(d) to splay node at depth d
worst case O(h) for any operation (splay leaf)
M operations cost O(M log N) time
amortized cost of each operation is O(log n), some better, some worse

B Tree

m-ary search tree (m=2 gives us a binary search tree)

tree is always balanced!
each node holds up to m-1 values
for each internal node: ceil(m/2) <= # children <= m
the values in the nodes are ordered and direct search to a child
height is O(log N) with base m (constant of m within log base 2)
as values are inserted, nodes are split as necessary in a process that recurses up to the root if necessary
this is how balance is maintained
useful for disk accesses instead of putting all data in memory:
for large m, each node is stored on a block of memory
do binary search to find a value in a node, or direct to child
each block access (as you go to the next level) is a disk access
there are at most O(log N) disc accesses

Algorithmic Time Complexity

Counting the number of basic operations

Not neccesarily exact
Big-O notation isused to describe the upper bound of time complexity
Gives an idea of how quickly/efficiently a method will run.
Measuring run times
single assignments, operations, input/output constant
statemtnts in sequence
sum of statement times
decision statemeents
max of its parts + conditions (test boolean) execution time
loop
maximum number of iterations multiplied by the sum of body statements + condition execution time
nested lops can be very complicated
method call
sum of all statements in method body
Big O, Big Omega, and Big Theta

Let T(N) represent the worst case running time of an algorithm with input size N.

by default we measure the worst case scenario

Big O: T(N) ~ O(f(N)) if there exists a 'c' and an 'n' such that T(N) <= cf(N) for all N >= n.

Upper bound function of worst case runtime. Note: We use '~' to represent "is an element of".
There are a large number of functions that can bound any given method. We then use the smallest possible function
which satisfies the Big O conditions

Big Omega: T(N) ~ Omega(g(N) if there exists c, n such that T(N) >= cg(N) for all N >= n.

Lower bound function of worst case runtime

 All functions have a g(N) of c (constant time)

Big Theta: T(N) ~ Theta(h(N)) if and only iff T(N) ~ O(h(N)) and T(N) ~ Omega(N)). Sandwhich theorem: cf(N) and cg(N) are of
the same type, but c and n can differ. Upper bounded by cf(N) and lower bounded by cg(N). THerefore we can use Theta(N) to
describe a range of worst case runtimes.

Example Linear Search algorithm

for (int i = 0; i<N; i++){

if (a[i] == value) {
return i;
}
}
return -1

Analysis

initializing i = 1 operation
Worst case N iterations
inside loop body = 1 operation
array access = 1 operation
iterate i = 2 operations (because i = i+1)
check condition i<N = 1 operation
Last condition (i<N) check = 1 operation
return = 1 operation

Then \(T(N) = 5N + 3\) and for all \(N >= n\) \(T(N) <= cN\) for \(c = 4\) and \(n = 3\) Therefore \(T(N) ~ O(N)\) \(T(N) >= cN\) for \(c = 3\)
and \(n = 1\) Therefore \(T(N) ~ Omega(N)\) Therefore \(T(N) ~ Theta(N)\)
Standard T(N) Functions (in order of efficiency)
c
constant time
log log log ... log(N)
multi log time
log(N)
logarithmic time
(log(N))^2
log squared time
(log(N))^k
log k time
N
linear time
Nlog(N)
linearithmic time (or just Nlog(N) time)
N^2
qadratic time
N^3
cubic time
c^N
exponential time

Sorting
Insertion Sort
for each value, move left as far as it needs to go
repeat for each position i from 2 to N
Time Complexity
O(N^2)

6 5 3 1 8 7 2 4
5 6 3 1 8 7 2 4
3 5 6 1 8 7 2 4
1 3 5 6 8 7 2 4
1 3 5 6 7 8 2 4
1 2 3 5 6 8 7 4
1 2 3 4 5 6 7 8

Bubble Sort
from left to right, compare adjacent values, swap if out of order
repeat N-1 times or until no changes
largest values bubble to the end
Time Complexity
O(N^2)

6 5 3 1 8 7 2 4
5 3 1 6 7 2 4 8
3 1 5 6 2 4 7 8
1 3 5 2 4 6 7 8
1 3 2 4 5 6 7 8
1 2 3 4 5 6 7 8

Selection Sort
mimimum based: find smallest value and swap into position
repeat for each position i from 1 to N-1
smallest values are placed into the correct positions
Time Complexity
O(N^2)

6 5 3 1 8 7 2 4
1 6 5 3 8 7 2 4
1 2 6 5 3 8 7 4
1 2 3 6 5 8 7 4
1 2 3 4 6 5 8 7
1 2 3 4 5 6 8 7
1 2 3 4 5 6 7 8

Merge Sort
Split array recursively by half until each array has length of 1
Merge and sort the arrays
Time Complexity
O(Nlog(N))
 6 5 3 1 8 7 2 4
6 5 3 1 8 7 2 4
6 5 3 1 8 7 2 4
6 5 3 1 8 7 2 4
5 6 1 3 7 8 2 4
1 3 5 6 2 4 7 8
1 2 3 4 5 6 7 8

Quick Sort
Pick pivot element
Median of three: median of first, middle, last
Swap pivot to last position
Work from both ends to make swaps
Iterate from both sides
If left[i] > pivot and right[j] < pivot, swap them
Every element left is <, every element right is >=
When ends join, put pivot element at union spot, then recurse
Time Complexity:
worst case O(N^2) if subsection only shrinks by 1 each time
best case O(N log N) (divide problem in half each time)
randomized version - get expected O(N log N) time
in practice: faster than mergesort, better space

20 13 7 71 31 10 5 50 17
median of: 20, 31, 17 -> 20 pivot
17 13 7 71 31 10 5 50 |20
17 13 7 5 31 10 71 50 |20
17 13 7 5 10 31 71 50 |20
17 13 7 5 10 |20| 71 50 31
first pass done, recurse on each partition
17 13 7 5 10 20 71 50 31
left median of 3: 17, 7, 10 => 10
right median of 3: 71, 31, 50 => 50
5 13 7 17 |10 |20| 71 31 |50
5 7 13 17 |10 |20| 31 71 |50
5 7 |10| 17 13 |20| 31 |50| 71
Left, left median of 3: 5, 7
left, right median of 3: 17, 13
5 7 10 13 17 20 31 50 71

Bucket Sort
Add all values to an HashTable with M buckets
Then remove in order
Time Complexity
O(N + M)
 6 5 3 1 8 7 2 4
[1] -> 1
[2] -> 2
[3] -> 3
[4] -> 4
[5] -> 5
[6] -> 6
[7] -> 7
[8] -> 8
1 2 3 4 5 6 7 8

Heap Sort
Build a heap (bottom up or top down)
Remove items from heap one by one
Time Complexity
O(N log N)
Radix Sort
Used to sort items using multiple paramaters
For example string containing letters and numbers (ie 3A33B5) can be sorted in order by comparing each value.
Start with rightmost dimension and create HashTable based on possible values
for integer 0 - 9
for character unicode range
Add values to HashTable (hashOne) based on current dimension values
Create new HashTable (hashTwo) based on new dimensions
Remove values from hashOne and add to hashTwo
Repeat until all dimensions have been checked
Time Complexity
O(d(M + N))

Text Processing

Strings are usually encoded as arrays of characters, each represented by a certain number of bits
Then we must decide the bit combinations to store each character
Fixed Length
Fixed length encoding scheme give each character a fixed number of bits
For an alphabet of 26 characters and 1 space we would need at least 27 possible combinations. This can be achieved
using characters with a fixed bit length of 5 because 24 < 27 < 25 Example A = 00000 B = 00001 C = 00010 ...
Unicode - 8 bits/character
This type of scheme may result in a creating more bits than neccesary
Variable-length encoding scheme:
Use character frequencies to make specialized encoding,
more frequent characters have shorter codes.
issue is knowing when one character stops and the next starts in a bit stream
"prefix code": no encoding is a prefix of any other encoding
Huffman Encoding Scheme
use variable length encodings for characters in text based on frequency
shorter codes for more frequent characters
no code can be a prefix of another (for decoding purpose)
called "prefix code"
binary tree to represent the code
left is 0, right is 1
 characters stored at leaves => prefix code guarantee
frequences stored in nodes
path from root to leaf gives encoding for that character
create by repeatedly merging min frequency trees into larger one
O(N) to read file (compute frequencies) and then encode
construct optimal code in O(C log C) time w/heap PQ
need to put encoding table in result file for decoding
Example

24
/ \
10 14
/ \ / \
4 6 6 8
/ \ / \ / \ / \
2 2 3 3 3 3 4 4
a r e t / \ sp / \ / \
1 2 2 2 2 2
! u /\ /\ /\ /\
W l o v D S c s

a 000
r 001
e 010
t 011
! 1000
u 1001
sp 101
W 11000
l 11001
o 11010
v 11011
D 11100
S 11101
c 11110
s 11111

Tries - more generalized approach

trees for storing strings (the actual text to be searched)
used for pattern matching & prefix matching
especially good for actual word matching
 Example - consider this passage: She sells seashells by the
seashore and he makes mounds of mud in the mountains.

a b h i m o s t
| | | | / | \ | / \ |
n y e n a o u f e h h
| | | | / \ | |
d k u d a l e e
| | | |
e n s l
| / \ / |
s d t h s
| | / \
s a e o
ins lls re (compressed for brevity)

General approach:
let S be set of strings from alphabet A s.t. none is prefix of another
trie nodes labelled with characters from A (except root)
path from root to external node forms a string in text
order children according to alphabet
properties for S strings in C size alphabet with M chars total in text
internal node has <= C children
has S external nodes
height = length of longest string
#nodes is O(M)
construction takes O(CM)
search for pattern size N takes O(CN)
compressed trie (Patricia trie)
combine nodes with single children that form chain
store substring indices of where each chain occurs in the original passage instead of all the characters at nodes
(so only need to store 2 integers instead of multiple characters)
nodes is O(S)

JUnit Testing

Tags
@Before
Tags a method that will run before each test
@BeforeClass
Tags a method that runs once at the beginning of the test class
@Test
Tags a test
@After
Tags a method that will run after each test
@AfterClass
Tags a method that runs once at the end of the test class
Import Statements
 import static [Link];
import static [Link];
import static [Link];
import static [Link];
import static [Link];
import static [Link];
import static [Link];
import static [Link];
import [Link];
import [Link];
import [Link];

Compile and Run

javac -cp <junit file name>.jar;. <class>.java

java -cp <junit file name>.jar; <hamcrest jar file>.jar [Link] <class>

Replace ; with : for OSX and Linux