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.
