Alg 2 Flashcards
Meaning of f(n) ∈ O(g(n))
f grows no faster than g
Meaning of f(n) ∈ o(g(n))
f grows strictly slower than g
Meaning of f(n) ∈ Ω(g(n))
f grows no slower than g
Meaning of f(n) ∈ ω(g(n))
f grows strictly faster than g
Meaning of f(n) ∈ Θ(g(n))
f grows at roughly the same rate as g
Formal definition of f(n) ∈ Θ(g(n))
There exist c > 0, C > 0 and n0 > 0 such that for all n ≥ n0, we have cg(n) ≤ f(n) ≤ Cg(n).
Does big O satisfy transitivity?
Yes. if f(n) ∈ O(g(n)) and g(n) ∈ O(h(n)), then f(n) ∈ O(h(n))
Does big O respect addition?
Yes. if f(n) ∈ O(h(n)) and g(n) ∈ O(h(n)), then f(n) + g(n) ∈ O(h(n))
Does big O respect scalar multiplication?
Yes. if f(n) ∈ O(g(n)), then for all constants A > 0, A*f(n) ∈ O(g(n))
Does big O respect multiplication of functions?
No. if f(n) ∈ O(h(n)) and g(n) ∈ O(h(n)), then f(n)·g(n) = O(h(n)) isn’t always true.
Does big O respect squaring?
Yes. if f(n) ∈ O(g(n)), then f(n)2 ∈ O(g(n)2)
Does big O respect expenonentation?
No. if f(n) ∈ O(g(n)), then 2f(n) ∈ O(2g(n)) isn’t always true.
Interval Scheduling
A request is a pair of integers, the start and finish time.
A set of requests is compatible if none of them overlap.
Greedy algorithm: keep choosing compatible interval with earliest finish time. O(nlogn)
Graph Terminology
Two graphs are equal if their vertices and edges are identical.
Two graphs are isomorphic if there exists a mapping between their vertices. (They are the same graph but relabelled)
A subgraph is induced if all edges that connect the sub-vertices in the original graph are also included in the subgraph.
A component of a graph is a maximally connected induced subgraph. E.g. if a graph consists of two triangles, each of those triangles is a separate component.
Euler Walks
A walk is a sequence of connected edges
An euler walk is a walk using each edge exactly once
A path is a walk with no repeated vertices.
A graph cannot have a walk if the number of vertices with an odd degree is not 0 or 2.
Digraphs
G is strongly connected if for all pairs of vertices u,v there is a path from u-v AND v-u.
G is weakly connected if for all pairs of vertices u,v there is a path from u-v OR v-u
Strong components are components that are strongly connected.
Weak components are components that are weakly connected.
In-neighbourhood of a vertex (D-) is the number of incoming edges.
Out-neighbourhood of a vertex (D+) is the number of outgoing edges.
Digraph Walks
A digraph cannot have an euler walk if it is not weakly connected.
It cannot have an euler walk with the same start/end point if it is not strongly connected.
Ways of representing matrices?
Adjacency Matrix - Row represents starting vertex, column is ending.
Adjacency List - Each vertex has a list of the other vertices it is connected to.
Adjacency Matrix Runtimes/space
Adjacency List Runtimes/space
Adjacency List vs Matrix
Depth-First Search Algorithm
Pick an unvisited vertex, repeat from that vertex recursively until no unseen vertices from current vertex, then backstep until there is an unseen.
Depth-First Search Trees
If x and y are adjacent in the original graph, one will be the ancestor of the other in the DFS tree.
Depth-First Search Invariant and Time
When helper is called, if explorer[i] = 1 then V_i is in the component.
Breadth-First Search Algorithm
Visit all unvisited vertices adjacent to the subgraph of visited vertices. Repeat until all visited.
Breadth-First Search Time Analysis
Bipartite lemma?
G is bipartite if and only if it has no odd-length cycle.
What is an augmenting path?
In a graph with a matching, an augmenting path is a path that alternates between edges in the matching (a matching edge) and edges outside the matching (non-matching edge). It also start & ends with a non-matching edge
What does the Switch function do? (matchings)
If P is an augmenting path for M,
Switch(M, P) returns a new path, where every edge that was matching is now non-matching and vice-versa. Two additional edges are added to either end as non-matching.
What is an auxiliary digraph? (matchings)
A bipartite graph with sections (A,B) where all matching edges are directed B to A and all non-matching edges are directed A to B.
D(G, M) where the graph is G and the matching is M.
Lemma for if a path is augmenting.
If and only if it is also a path from the non-matching vertices of A to the non-matching vertices of B in the auxiliary digraph.
Algorithm to find maximal matching?
Find a bipartition (A,B) of G. Initialise M <- []
loop:
Form the graph D(G, M)
Set P to be a path from UnA to UnB in D(G,M) if exists:
Otherwise, break
Update M <- Switch(M, P)
return M
Invariant of the algorithm to find maximal matching?
At the start of the ith loop iteration, M is a matching with i-1 edges. M can have at most |V|/2 edges in total, so it outputs a matching with no augmenXting paths.
Maximal matching algorithm runtime?
O(|E||V|)
Berge’s lemma?
M has no augmenting paths => M is maximal.
Prim’s Algorithm
Keep adding the edge with lowest weight that connects a disconnected vertex to the existing tree.
Implemented as BFS with a priority queue.
O(|E| log |E|)
Kruskal’s Algorithm
Keep adding any edge in the graph with the lowest weight so long as it isn’t connecting two already existing vertices.
O(|E| log |E|)
