Algorithmics Flashcards
Stack Operations
push
peak
pop
isEmpty
Queue Operations
enqueue
peek
dequeue
isEmpty
Priority Queues Additional Operations
insert (giving a priority)
findMin
deleteMin/removeMin - returns the lowest element
List Operation
add - shifts elements to make space
remove
set - replaces element at position
get
Set Operations
add
remove
contains
size
isEmpty
Map Operations
put
get
remove
size
Skip List
Data Structure
Hierarchies of linked lists which allow for binary search, allowing Θ(log(n)) search. Good for concurrent access compared to binary trees
Binary Tree
A tree (a graph with no cycles and no direction) where each node has at most 2 children
Binary Search Tree
A binary tree where every element in the left subtree is smaller and each element in the right subtree is larger for every parent
Successor
Binary Search Tree
The next smallest element. Found by:
1. If has right child move right once then left as far as possible
2. Otherwise go up left as far as possible then up right once
Deletion
Binary Search Tree with 2 children
Replace the element with it’s successor. Then remove the successor
Single rotation
Binary Search Tree
Move top element of larger subtree up and change middle subtree to old top element
Double Rotation
Binary Search Tree
Needed if large subtree is in the middle. First move large subtree to outside. Then do normal rotation
AVL trees
Binary search tree where all parents left and right subtrees differ by at most 1
AVL tree implemenation
Each node has a balance factor. If > |1| then do rotations on deepest section.
AVL additions
Iterate up tree changing balance factor (increase if on left). Stop when balancefactor > |1| or is 0.
AVL deletion
Requires updating of balance factors and rotations but may need repeated rotations. Worst case O(log(n))
Red-Black Trees
- Black Root
- Children of red nodes are black
- Number of blacks on route from root to any exposed node (<= 2 children) are the same for all routes
Complete Tree
Lowest level is all on the left and other levels are full.
Heap
A complete tree with every child being >= its parent (so root is smallest)
Adding to Heap
Add element to next space in tree and swap with parent until corrrect (percolate up)
removeMin
heap priority queue
- Pop root
- Replace it with last node in heap
- Swap with smallest child until fixed
Heap Array Implementation
Root stored at 0. Children of node at k are at 2k + 1 and 2k + 2
Heap Sort
Add all elements to a heap then take them off again. Worst case O(nlog(n)) as we need to do add/remove 2n times and add/remove are O(log(n))
B-tree
Balanced trees for keeping related data close together. Good for disk access time
M-way tree
Allow for nodes to have many children. Reduces the depth of trees greatly, reducing access time
B+ Tree
All data stored in leaves. Non leaf nodes store M/2 - M-1 keys with a key corresponding to a child (Can have an extra child if on left or right). All leaves have L/2 - L data entries. Each key corresponds to a subtree with the smallest value in that subtree being that key value. Leftmost subtree has no key for it.
Trie
Multiway tree for storing sets of words. All words end with $. Use lots of memory
Internal one-way branching
Trie
Edges between non-leaf nodes, can be removed by condensing
External one-way branchiong
Trie
Edges that reach the leaf nodes, can be removed by condensing
Suffix Tree
Trie of all suffixes of string, so all parts of string included. Good for finding if string in text
Content-addressable memory
Where we want to access data based on a linked objects contents (use hash table)
Turn Hash into address
Hash % tableSize
Hash Collision
Two objects map to same address
Seperate Chaining
Hashing
Make a linked list to store any hash collisions
Open Addressing
Finding a new space in the hash table to put hash collisions
Linear Probing
Hash collisions are moved to next available space. Can cause clustering making loading data slow
Loading Factor
hashing
Proportion of full entries in the table
Quadratic Probing
hashing
hash collisions are placed in next available space 1, 4, 9, … spaces away (i^2). Prevents clustering, may cause failure to place element when table not full
Double Hashing
hash collision are placed in next available space multiples of new hash address away (from a different hashing function). Table size should be prime to allow all spaces to be checked.
Element Removal when open addressing
Hash Table
Can be sone by replacing removed elements with dummy entry, counted as full for finding, but empty for placing
Union-Find
Groups elements together. Operations:
* union (A, B) - Combines the groups containing A and B together
* isConnected (A, B) - Checks if A and B are in the same group
* find (A) - Checks what group A is in
Dynamic Connectivity
Data Structures
A property of a data structure such that it stores objects where some of them are connected. These connections can change. A Union-Find has dynamic connectivity
Equivalence class properties
A relation on a set of elements such that it is:
* Reflexive - A ∼ A
* Symmetric - if A ∼ B then B ∼ A
* Transitive - if A ∼ B and B ∼ C then A ∼ C
A property of a union-find
Quick-Find
Uses a 1 to 1 array of elements and an array of ids (groups). Elements are in the same class (group) if their id is the same. Allows O(1) find
* isConnected (A, B) - checks if A and B have the same id
* find (A) - returns A’s id
* union (A, B) - changes id of all elements in group A to the id of group B
Quick-Union
Elements stored in trees. Parent of a tree is itself by default. The id of an element is it’s parent, so that’s what the array of ids stores. Bad as O(n) for all operations. Operations:
* find (A) - return the id of A’s root
* isConnected (A, B) - true if A and B’s roots are the same
* union (A, B) - Makes A’s root the child of B’s root
Weighted (Balanced) Quick-Union
Store an additional size[] array storing the number of elements in each tree. For union (A, B), make the root of the smaller tree the child of the root of the larger tree. Allows for O(log(n)) find and union when doing path compression
Path Compression
Quick-Union
Improvement to quick union where elements visited when finding a root have their id set to the root
Stability
Sorting Algorithm
Stable if the order of elements with the same value does not change
In-Place
Soting Algorithm
If memory used is O(1)
Insertion Sort Properties
It is stable and in-place. But O(n^2) worst case time complexity. Very good for small arrays
Selection Sort
Search for smallest element and swapped with the element in the first unsorted position
Selection Sort Properties
in-place but not stable as swaps can change order. O(n^2) time complexity in all cases. Performs few swaps
Loop Invariant
Algorithms
Property of a loop that helps show correctness. Must show:
* Initialisation - Be true before the first iteration
* Maintenance - Is true before loop, is true after
* Termination - Can be used to show that the algorithm is correct after the final loop
Merge Sort
Divide the array into two halves until 1 element arrays. Then Merge sorted arrays together until 1 array. stable, O(n) space and O(nlog(n)) time
Merge Sort Improvement
Can use insertion sort on small sub-arrays, due to it being fast on small arrays
Quicksort
Choose pivot and put smaller elements on left and larger elements on right. Repeatedly pick pivot until all elements been picked as pivot. not stable but in place, O(n^2) worst case but O(nlog(n)) average
Choosing pivot well
quicksort
- Choose randomly to avoid worst case (can be done by shuffling array at start)
- Choose median of first middle and last element
Quicksort improvement
Use insertion sort on the small arrays
Comparison-Based time complexity
Minimum omega(nlog(n)) due to minimum number of comparisons
Quicksort Partitioning
Algorithm for splitting elements lower and higher than pivot
Lomot Partitioning Scheme
Quicksort Partitioning
2 sections for higher and lower with each element sorted into one of them. O(n) time complexity
Hoare Partitioning Scheme
Quicksort Partitioning
2 Pointers at ends of array which move away from ends. If element at pointer not correct in relation to pivot, swapped with equivalent element at other pointer. Stop when pointers cross. Pointer that started at the right is partition point. O(n) time complexity
Knuth Shuffle
Quicksort
Starting from last element go back, swapping each element with random one in unshuffled section. O(n)
Multi-pivot Quicksort Benefits
Better performance due to rduced cache misses.
Radix Sort
Every element must be d characters, with k possible characters. Sort array by each character, starting from last using stable sort. Is Θ(d(n + k)) when using counting sort with d the number of digits and k the base
Counting Sort
Count the occurences of each element. Make the occurences into a cumulative counter. Loop backwards through the unordered array and place element in position as stated by cumulative array. Then decrease count by 1.
Counting Sort Properties
Stable but not in-place. time O(n + k) and space O(n + k) with k being base. Good when n > > k. if k > n then bad as have to make large structure
Adjacency Matrix
Graph
Represents a graph. A matrix with each node representing a row and column. Intersections between nodes have 1s if an edge is present and a 0 if not
Adjacenecy List
Graph
Represents a graph. Nodes are stored as a list with each connected nodes stored in that list
Euler Trail
Graph
Route through a graph where each edge is passed through once. Requires <= 2 odd-degree nodes
Euler Circuit
Graph
Euler trial with the end node being the starting node. Requires 0 odd-degree nodes
Euler Circuit Construction
Graph
- Travel along any adjacent unused edge
- Repeat step one until the start node for the loop is reached
- Mark the loop and move along it until there is an adjacent unused edge and go to step one. if the start is reached first (every edge used), the circuit is done
Minimum Spanning Tree
Graph
A subgraph that spans all nodes of the parent graph but minimises the weight of the edges crossed.
Kruskal’s Algorithm
Graph
Method for finding a minimum spanning tree. Contains a set of trees each step the safe edge with the lowest weight is added to the forest (set of trees)
Safe Edge
Graph
An edge that when added to a graph does not form a cycle, and would prevent a minimum spanning tree
Kruskal’s Implementation
Graph
All nodes stored as thier own tree initially in a union-find. When two subtrees connected a union is done on the subtrees. O(elog(e))
Prim’s Algorithm
Graph
Method for finding a minimum spanning tree. Contains a tree, each step the safe edge with the lowest weight connected to the tree is added to the tree
Prim’s Implementation
Graph
Two arrays for the connected nodes and the unconnected nodes. When node connected to the tree it is added to the connected nodes array O(elog(e))
Dijkstra’s
Graph
Method for finding the shortest route from a root node to every other node
Hamiltonian Path
Graph
A path that goes through each node exactly once
Dynamic Programming
The idea of combining smaller overlapping subproblems to solve a given problem. The subproblems are created recursively.
Dynamic Programming Steps
- Find a recursive algorithm to solve the problem
- Remove recalculation of subproblems using memoization/bottom-up
- Store the actual solution, not just the values
Memoization
Dynamic Programming
The storage of results to sub-problems to prevent their future calculation
Bottom-up
Dynamic Programming
The calculation of subproblems starting at the base case then working up to the full problem, replacing the recursive algorithm with an iterative one
P
Complexity Theory
Problems that can be solved in polynomial time
NP
Complexity Theory
Problems that can have solutions verified in polynomial time
NP to P relationship
Complexity Theory
P ⊆ NP As if a solution is found, that verifies it. Assume P ⊂ NP for our uses
NP-Hard
Complexity Theory
Problems in NP-Hard are at least as hard as all problems in NP
NP-Complete
Complexity Theory
Problems that are in NP-Hard and in NP. i.e. the hardest problems in NP
α-approximation algorithm
An algorithm that runs in polynomial time and produces a solution that is at most a factor of α of the original solution
Satisfiability
Algorithms
Gives a boolean formula in the structure A ∧ B ∧ C ∧ … where each letter is a clause containing A1 ∨ A2 ∨ A3 ∨ … Is there an assignement where the formular is true. It is NP-Complete. SAT if you reach an empty formula
DPLL Algorithm
Algorithms
Two rules
* If a clause has 1 variables, it must be true
* If a variable is pure (It’s negation does not appear), it can be set to true
Branch and Bound
Algorithms
When doing backtracking, instead of trying all possibilities, you can exclude certain routes that are impossible to provide a solution,
Local Search
Algorithms
Used in an optimisation problem. At each step changes to a neighboring output that goes in the wanted direction. A greedy strategy as gets stuck in local optima
Simulated Annealing
Algorithms
At each step randomly choose a new location. If better do it. If worse do it with a probability, increased if less bad and if higher temperature. Probability given by e^(−∆/T)
Chromosome
Genetic Algorithms
A representation of an individual
Gene
Genetic Algorithms
A position in a chromosome
Allele
Genetic Algorithms
A possible value for a gene
Steps
Genetic Algorithms
- Compute fitness of all individuals
- Keep some individuals, favouring higher fitness
- Mutate the individuals
- Crossover individuals to replace dead ones
