.121 15-20 Flashcards
What is big omega notation?
lower bound - T(n) ≥ M×f(n) for all n ≥ n₀
grows no slower than f(n) - ≥
find simplest so also big Ω of anything that grows slower
What is big theta notation?
tight bound - M1×f(n) ≤ T(n) ≤ M2×f(n) for all n ≥ n₀
combo of other 2 - grows no slower + no faster than f(n) - ==
How do you prove big theta?
prove big O and big omega
e.g. T(n) ∈ O(n) AND T(n) ∈ Ω(n) → we can say T(n) ∈ Θ(n)
How do you prove big omega?
replace anything that isn’t the dominant term with a 0 then add up to find M
find n0 by getting equal to the n term and dividing to get n alone
e.g. given T(n) = 3n + 4, f(n) = n
3n ≥ 3n (equal), n ≥ 0
3n + 4 ≥ 3n + 0 when n ≥ 0
M = 3 (given the 3n) and n0 = 0 therefore T(n) ∊ Ω(n)
How do you prove big O?
get n0 by collecting non-dominant terms + dividing them to get n alone
get M by multiplying non-dominant terms by the dominant term and adding them up
e.g. given T(n) = 3n + 4, f(n) = n
T(n) = 3n + 4 ≤ 3n + 4n so T(n) = 3n + 4 ≤ 7n
4 ≤ 4n → divide by 4 → 1 ≤ n
M=7 and n0=1 → T(n) ≤ 7n for all n ≥ 1 therefore T(n) ∊ O(n)
What is a recursive algorithm?
an algorithm which calls itself w/ smaller input values
obtains the result for the current input by applying simple operations to the returned smaller input
How do you find the recurrence relation for recursive algorithms?
find constant time complexity (no recursion) and write T(1) = T(n) of the one operation
(probs constant so can just write 1)
then do T(n) for prior constant + recursive call
How can we evaluate recursive time complexity?
- back substitution
- recursion tree
- master theorem
How does back substitution work?
replace recurrent relation w/ other equivalent options - e.g. T(n-1) + 1 = T(n-2) + 2 or T(n/2) + 1 = T(n/4) + 2
then find pattern of substitution - e.g. T(n-k) + k or T(n/2^k) + k
apply this pattern to T(1) to reach final theta notation
- e.g. if k = n -1 and T(n) = T(n-k) + k = T(1) + n -1 = 1 + n -1 = n therefore T(n) = n thus Θ(n)
What is sorting data useful for?
ranking data, more efficient searching (in general) + binary searching
How does a selection sort work?
find smallest value in input + extract it into new array
repeat till all items are in new array
How does an in-place selection sort work?
find smallest value in input + swap w/ 1st value of array
repeat till index is at end of array
(change 1st to next index as each item is added)
What does an in-place sort mean?
sorts the items within the array that was inputted instead of creating a new array to help save memory
O(1) space complexity!!
What do we need to analyse for sorts?
correctness + time complexity
What is the time complexity of a selection sort?
O(n^2) in all cases
How does an insertion sort work?
move elements from input to new array in list order
once added check if the element is > than items alr in list + move accordingly
How does an in-place insertion sort work?
compare values in the list order + swap accordingly
e.g. 1st > 2nd ? 2nd > 3rd? etc.
What is the time complexity of an insertion sort?
O(n^2) in all cases
How does a merge sort work?
recursively splits array into subarrays till there is just 1 item per array
then merges subarrays together by comparing the heads of each
Where does a merge sort split arrays?
(start index + end index + 1) /2
How does a quick sort work?
pick a pivot (point/index) to split the subarray at
sort so anything greater than the value of the pivot is behind it (swap any elements > pivot w/ one next to them and once you reach no swaps swap current index w/ pivot)
recursively solve subarrays then merge
What is the time complexity of a merge sort?
O(nlogn) in all cases
What is the time complexity of a quick sort?
O(nlogn) in best + avg case
but O(n^2) in worst case
Define a tree:
non-linear ADT that stores elements hierarchially as nodes connected by edges w/ NO cycles or loops
What are some uses of trees?
file directory structures, XML + HTML, compilers and collision detection
What are the relationships within a tree?
root = top node (no parents)
children = node w/ parents
leaf = node w/ no children
descendants/ancestors - relative of relative of
What is the height of a node?
no. of nodes of longest path from given node to some leaf
What is the depth of a node?
number of nodes from given node to root
What is the height of a tree?
height of its root/depth of its deepest nodes
What is the diameter/width of the tree?
no. of nodes on longest path between any 2 leaves
How many edges does a tree w/ n nodes have and why?
n-1 edges as n nodes each have 1 edge going to them other than root
What is a subtree?
taking a node + its descendants from a full tree
basically part of a tree
What is a k-ary tree?
tree that imposes a max no. of children to each node
e.g. binary = max 2
What is a balanced tree?
for any node, the height of its child subtrees differ by ≤ 1
What functions would a tree ADT class have?
void add (Object new, Object parent)
Tree find(Object val)
Tree remove(object n)
void move(Object n, Object parent)
What happens to the children of moved/removed nodes?
children become the children of that node’s parents instead
What is the significance of find() in tree ADT?
used to search for nodes + used in move and remove functions
What do tree traversal algorithms do?
used to enumerate all elements in a tree or decide in which way we look through a tree to find elements
How does pre-order traversal work?
dot to left
CLR
How does post-order traversal work?
dot to right
LRC
How does in-order traversal work?
dot below
LCR
What do pre-order, post-order + in-order traversal have in common?
all based on a depth-first search
so can be implemented non-recursively using a stack or recursively
How does breadth-first traversal work?
traverse tree from left to right at each level from the root using a queue
(where a level is like root then all of that roots children then all of there children etc.)
Give some examples of index systems:
DNS lookup
compiler
packet routing table
dictionary
What methods does a dictionary ADT inc.?
void insert (key k, value v)
void delete (key k)
value find (key k)
What are common implementations of a dictionary ADT?
sorted arrays, search trees + hashing
What is the difference between using sequential allocation or sorted arrays (dictionary ADT)?
sequential - insert = O(1), find + checking for duplicates = O(n)
sorted - find = O(logn), insertion + deletion = O(n) given sorting
What is a binary search tree?
binary tree where each node has a k,v pair + nodes are sorted by their keys
to be sorted, every nodes’ key must be ≥ all keys in its left subtree + strictly < than all keys in its right subtree
What functions does a BST ADT need?
delete() - any children will become children of their ancestor
insert()
find() - if smaller (go left), if bigger (go right)
Why do BSTs need to be balanced?
finding is very efficient on balanced trees but not degenerate/unbalanced
w/ random insertion order expected height h = O(log n) + worst case TC = O(h) aka O(log n) - but can use SBBSTs to ensure this height
What are the types of self-balancing search trees?
2-3 trees
AVL trees (SBBST)
red-black trees (builds upon 2-3 trees to represent 3-node as BT w/ red link)
B-trees (generalisation of 2-3 trees for more keys per node)
What are some self-balancing trees that are not height-balanced?
splay trees + treaps
- helpful for if you wanted tree to balance for common letter patterns rather than any letter sequence
What are the cons of 2-3 trees?
inconvenient to implement
-diff. node types
- multiple compares per node
- moving back up tree to split 4-nodes
What is a 2-3 tree?
2 node = 1 key, 2 children
3 node = 2 keys, 3 children
same find() function but more complex insert()
What is different about a 2-3 tree insert()?
to maintain perfect balance…
- a 2-node is transformed into a 3-node OR
- a 3-node is split into 3 2-nodes OR
- non-root 3-node w/ a 3/2-node parent transforms into a TEMP 4-node (split later)
What is a graph?
set of nodes + edges that capture relationships
What is a simple graph?
graph w/ no self-loops
How can graph edges be detailed?
may be directed (arrows) or undirected (every edge = bidirectional)
+ weighted (associated values on edge)
What is a hypergraph?
nodes + hyperedges to capture k-wise relationships ( k > 2)
rather than usual pairwise
What is a subgraph?
subset of nodes + edges of a graph
What is a spanning subgraph/tree?
spanning subgraph = formed from all nodes of the graph but only some edges
spanning tree = spanning subgraph + tree
minimal spanning tree = spanning tree w/ min. total sum of edge weights
What is a complementary graph?
same set of nodes + contains all the edges NOT in the other graph
Explain graph density:
measure from 0-1 that indicates how heavily connected its nodes are
What is a strongly/weakly connected graph?
undirected = strong - if path between any 2 vertices
directed = weak - undirected ver. is connected but directed is not
What methods would a graph ADT inc.?
addNode (Node n)
removeNode (Node n)
addEdge (Node n, Node m)
removeEdge (Node n, Node m)
isAdjacent (Node n, Node m)
getNeighbours (Node n)
What are the 2 diff. graph implementations?
list of lists or adjacency matrix
What are the complexities for graph list implementation?
N = nodes, E = edges
mem. = O(N+E)
TC = O(1) for addNode + O(N) for rest
What is an adjacency matrix?
2D array that can represent graphs
1 indicates edge between nodes, 0 doesn’t
symmetric for undir. so only need to modify 2 cells per edge
only modify 1 cell for dir. graphs
What are the complexities for graph adjacency matrix implementation?
N = nodes, E = edges
mem. = O(N^2)
TC = O(N^2) for add/removeNode + O(1) for rest
What are the ways to traverse a graph?
depth-first or breadth-first
How does depth-first graph traversal work?
using stack to push once visited + pop to backtrack
start from source then visit current node’s neighbours till hit an alr. visited
backtrack + continue
How does breadth-first graph traversal work?
using queue to enqueue then dequeue once fully visited
start at source + visit all nodes at distance 1, then 2, etc.
can form a BFS tree out of list of traversed edges to find shortest paths
Define path:
sequence of non-repeating nodes from node x to y
What are the 3 shortest path problems?
given a graph G = (V, E) + source node s…
shortest distances (to s) = distance from all nodes v ∈ V to s
shortest paths (to s) = for each node v ∈ V the shortest path from v to s
pathfinding (s to target) = shortest path from s to t
How to find shortest path for unweighted graphs?
path that inc. least no. of edges - find using BFS
What are the algorithms for solving shortest path problems?
Dijkstra’s
- extended to A*, Bellman-Ford + Floyd-Warshall
How do you find shortest distance using Dijkstra’s?
initialise visited[] to not + distToSource[] to 0 for source + infinity for rest
visit closest nodes to you then for all its neighbours if path is shorter than update it
do till all nodes = visited
How do you find shortest path using Dijkstra’s?
visited[] = not, distToSource[] = 0/infinity, prevNode[] = null
do the same as shortest distance +record prevNode accordingly
How do you compute pathfinding using Dijkstra’s?
set up arrays as per
visit closest unvisited nodes + return path + distance once you find target
path = prevNode[node], prevNode[prevNode[node], etc.
What is the TC of Dijkstra’s algorithm?
worst case = O(n^2)
can improve to O(m + n log n) if using better data structs. like priority queues/SBBST
When can we use A* algorithm?
have extra info (heuristic) on distances for some nodes to source
When can we use Bellman-Ford algorithm?
have edges w/ negative weights (but not cycles)
How does A* search work?
uses heuristics to guide the search
e.g. if weights represent actual travel distances then can approximate to straight line dist.
How does Bellman-Ford algorithm work?
compute (over)estimations of the distances from source → all other nodes which you iteratively improve on
improves all edges every iteration rather than picking 1 each time like Dijkstra’s
What is the worst case TC of the Bellman-Ford algorithm?
O(n ⋅ m)
What is a greedy algorithm?
solve your problem in stages + in each stage choose the locally optimal choice
fast (approximation) but can be incorrect/non-optimal
What is an algorithmic paradigm?
generic framework that underlies a class of algorithms
e.g. divide + conquer, greedy + recursion
What are some problems solved by greedy algorithms?
travelling salesman, shortest path + vertex 3-colouring
How does a greedy solution to the shortest path problem work?
same as Dijkstra’s
start at source + visit closest unvisited till all are visited
How does a greedy solution to the travelling salesman problem work?
repeatedly visit nearest node to current node + once all visited go back to origin
!shortest route but correct
How does a greedy solution to vertex 3-colouring work?
for i = 1 to V, choose for node v[i] the smallest colour that no neighbour has chosen yet
(CANNOT solve vertex 2-colouring though)
What are the greedy algorithms regarding minimum-weight spanning trees?
Kruskal’s + Prim’s algorithms
How does Kruskal’s algorithm work?
start w/ tree T = ∅, sort edges from lowest - highest weight
for i = 1 to [E], if edge e[i] doesn’t form a cycle when added to T then add it to T, or also T = T ∪ {e[i]}
Kruskal TC:
takes O(|E|log|V|) worst case TC
How does Prim’s algorithm work?
start w/ V[t] = v[1] and E[r] = ∅
while V[t] ≠ V, find min. weight edge {u, w} going from node in T to node outside T, add {u, w} to E[t], w/o loss of generality, u ∈ T, then add w to V[t]
Prim’s worst case TC:
O(|E| + |V| log|V|) - best implementation
O(|V|^2) or O(|E| log|V|) - easier implementation
