FUCK Flashcards
What is ln(e^n) and e^ln(n) =
n
Log Rules
Product: loga(xy) = loga(x) + loga(y)
Quotient: loga(x/y) = loga(x) - loga(y)
Power: loga(x^y) = yloga(x)
Quick Sort
Divides problem into two parts. Pick a pivot to split elements left and right if smaller or larger
Merge Sort
Divides until length 1 merges and sorts list recombining them
Big O Equation
G(n) less than or equal to c * f(n)
Big Omega Equation
G(n) greater than or equal to c * f(n)
Theta Equation
G is in Big O(f) and Big Omega(f)
Small o Equation
Lim
G(n) / f(n) = 0
N -> Infinity
Small Omega Equation
Lim
F(n) / g(n) = 0
N -> Infinity
Interpretation
Big O - G does not grow sig faster than f
Big Omega - G does not grow sig slower than f
Theta - G grows as fast as f
Small o - g grows sig slower than f
Small omega - g grows sig faster than f
Graph Definition
Undirected graph consists of vertex set and edge set where every edge connects two vertices referred to as nodes
Edge Definition
An edge connects two vertices, each vertex being an endpoint
Walk
Sequence of edges and vertices and every edge has both endpoints. If first vertex = last vertex the walk is closed
Trail
A trail is a walk where all edges are distinct
Path
A walk in which all vertices are distinct
Circuit
A closed trail
Cycle
A circuit where only the first and last vertex are equal
What is an inner node
Any node with children
Height of a tree
Length of longest path to from root to any leaf
Depth of a node
Length of path to its root
Height of a node
Length of longest downward path to a leaf from that node
Level of a tree
Level starts from 0 at root and increases for each level of children
Tree Definition
A cycle free connected graph
Depth first search
Searches “deeper” in the graph when possible exploring subtrees on the right first
Breadth first search
Explores all in the same level
Binary Search Tree
Stores keys in the vertices, key stored must be greater than every key in left sub and smaller than every key in right sub
Insert function
Search for key, if not found keep going till vertex found with no children add left or right accordingly
Delete function
If a key is a leaf, remove, if a single child remove by connecting subtree with parent.
If has sibling replace by smallest vertex in subtree and attach other subtree to parent
Is member search function
Start at root, if root = done
If smaller go left or else go right
Repeat till key is found or return null
AVL Tree
When every vertex of a binary tree is height balanced
Collision in AVL Tree
Two keys mapped to same position
Hashing
Use an unsorted array larger than number of keys. Use hash function to map key to the array
Load Factor
Alpha = num of keys / size of hash table
Probing
Checking if hash table position is free
Chaining
All keys mapped to same position sorted in a linked list
Linear Probing Search
Try to map k
If position free, element not in table
If contains k, search successful
If contains different key check every next position
Linear Probing Delete
Search for key and mark key as deleted
Linear Probing Insert
Try to map k
If position free insert k
If contains k stop
If contains different key try for every next position
Linear Probing A/D
A: No external data needed, cache friendly
D: Access time bad for alpha > 0.7, new hash table must be created if full and insert all keys, keys should not or rarely be deleted
Quadratic Probing
Similar to linear probing but different hash function: h(k,i) = h(k) +x mod n
X goes up in squares, +1 -1 +4 etc.
Access time bad for alpha > 0.8
Between LP and chaining for cache
Double Hashing
Like linear but uses second hash function
h(k,i) = ( h(k) + i*h’(k) )mod n
Access time bad for alpha > 0.8
Between QP and chain for cache
Adjacency List
Every vertex has a list if vertices to which it is adjacent to
[1][] [3][] [4][]
For sparse graph
Adjacency Matrix
Makes matrix for all nodes with 1 for an edge, 0 otherwise
For dense graph
Incidence List
One list for every vertex listing all incidents
Linked List
Keeps references to head and tail
A queue
Fifo structure
Enqueue: Add to Tail
Dequeue: Remove from head
A Stack
Lifo structure
Push: Add to head
Pop: Remove from head
Peek: Access head element w/o removing
Hierholzer
Start at some vertex, go through graph till reaching root. Start second circuit for incident edge to starting vertex using only unused edges. Combine for euler circuit
Euler Circuit
Every edge visited exactly once in a circuit, vertices can be repeated. Makes graph Eulerian
Every vertex needs even degree
Euler Trail
Like Circuit but does not have end return to root. Makes graph semi eulerian
A forest
A graph that has no cycles but is not necessarily connected
Spanning Subgraph
Contains all vertices of original graph but does not have to be connected, no edges can be added that do not already exist
Kruskal’s Algorithm
Start with empty set
Add next edge of minimal weight from graph to set without making cycles
Stop once connected graph is reached
Requires dynamic partition
Dynamic Partition
Makeset() creates one element set
Find() returns subset containing element
Union() constructs union of disjoint subsets
Prim’s Algorithm
Pick arbitrary vertex as start
Select edge of minimum weight from neighbour not already connected
Repeat until every vertex in tree
Requires Priority Queue
Priority queue
Extractmin - returns smallest element
Insert - inserts element
isEmpty - checks if data structure is empty
Iterative improvement
Starts with feasible solution and improves over iterations
Dynamic Programming
Subproblems are not independant solving every subproblem and storing answer in a table or array, no recomputing
Coin row problem
Row of n coins, find max money not picking up adjacent coins
Divide row into two, f(n, n+2, etc.) and f(n+1, n+3 etc.)
See which totals more
Robot coin problem
Coins placed in n*m board robot in upper left cell has to collect as much money as possible one step at a time
Make matrix showing current value and take max from left or above to pick a value to take precedent
Dijkstra’s Algorithm
Start from s Keep data structure with all vertices not added Add new vertex with minimal distance Update v with distance and predecessor Cant use negative weights
Bellman Ford
For negative edge weights but not as fast as dijkstra
Has distances and predecessors
If distance to starting vertex + edge weight is smaller than distance to destination vertex
Single pair
Shortest path between pair of vertices
Single source
All shortest paths from source to other vertices
Single destination
All shortest paths ending to some vertex from all other vertices
All pairs
Shortest path between every pair of vertices
Tree rebalance simple rotation
If parent unbalanced, Child becomes new root. Child's right sub becomes parent's left sub. Parent becomes child on right. Child's left sub remains the same
Simple if outer subtree taller
Tree rebalance double rotation
If parent unbalanced Child's child becomes root of parent C1 becomes left sub of c2 C2 right sub becomes parent left sub C2 becomes new root
Double if inner subtree taller
Amortised Analysis
Analyzing an algorithm’s complexity or how much of a resource, or time/memory it takez to execute as sometimes worst case is too extreme
