Unit 2: Analysis of Algorithms and Graphs Flashcards
3 Common measures for the efficiency of algorithms
- Run-time
- Memory usage
- Problem-specific parameters (e.g. slow memory access, network usage).
Random Access Machine
- There is exactly one CPU
- All data is in main memory
- All memory accesses require the same amount of time.
4 Atomic operations
- Assignments:
a←b - Arithmetic operations:
b ⏺ cwith⏺ ∈ { +, -, x, /, mod, ... } - Logical operations:
∧,∨,¬, . . . . - Comparison operations:
a bwith∈ {<, ≤, =, 6=, >, ≥}.
Run-time of an algorithm
Run-time:
- Is the number of atomic operations executed by the algorithm.
- For simplicity, the run-time T(n) is usually described as a function T of the input size n.
Definition of Θ(g(n))
For a given (non-negative) function g(n) we denote by Θ(g(n)) the set of functions:
Θ(g(n)) = { f(n) | there exist constants 0 < c₁ ≤ c₂ and n₀ such thatc₁g(n) ≤ f(n) ≤ c₂g(n) for all n ≥ n₀}
Intuition: f(n) ∈ Θ(g(n)) if f(n) can be “sandwiched” between c₁g(n) and c₂g(n),
for sufficiently large n.
Further asymptotic notation: Θ, O, Ω
-
Θexpresses tight upper and lower bounds on f(n). -
O(“big-Oh”) expresses an upper bound (e.g. when talking about worst-case run-time). -
Ωexpresses a lower bound.
Definition of O(g(n)) :
O(g(n)) = { f(n) | there exist constants 0 ≤ c and n₀ such thatf(n) ≤ cg(n) for all n ≥ n₀}
Definition of Ω(g(n))
Ω(g(n)) = {f(n) | there exist constants 0 ≤ c and n₀ such thatcg(n) ≤ f(n) for all n ≥ n₀}
2 Properties of Θ
-
cf(n)∈Θ(f(n)) -
f(n) + g(n)∈ max(Θ(f(n)),Θ(g(n)))
Properties of Θ, O, Ω: “defining smaller order terms”
max( Θ(f(n)), Θ(g(n))) =
* Θ(f(n)) if g(n) ∈ O(f(n))
* Θ(g(n)) otherwise
Dominance between functions
f(n) is dominated by g(n), if f(n) = O(g(n)) but not g(n) = O(f(n)).
g(n) dominates f(n), if lim_{n→∞}f(n)/g(n) = 0
Define:
Undirected Graphs
G = (V, E)
* V is the set of vertices
* E is the set of edges between pairs of vertices.
Define:
Adjacency & Neighbours
Let e={v, u} be an edge in E, then
- v and u are adjacent.
- v is a neighbour of v and u is a neighbour of v.
Define:
Incident edge
Let e={v, u} be an edge in E, then
- v and e are incident
Define:
Vertex degree
The number of edges incident to v.
Define:
Multi-edge
More than one edge between the same two vertices.
Define:
Loop
An edge between a vertex and itself.
Define:
Simple graph
An undirected graph without multi-edges and loops.
Define
Path
A path in an undirected graph G = (V, E) is a sequence (v₁, v₂, . . . , vₖ₋₁, vₖ), k ≥ 1, of vertices with the property that each consecutive pairvᵢ, vᵢ₊₁ is joined by an edge in E.
The length of a path is k − 1.
Define
Cycle
A cycle is a path (v₁, v₂, . . . , vₖ₋₁, vₖ) for which {v₁, vₖ} is an edge too,k ≥ 3.
The length of this cycle is k.
Define
Path
A path in a digraph G = (V, E) is a sequence (v₁, v₂, . . . , vₖ₋₁, vₖ),k ≥ 1, of vertices with the property that every consecutive pair vᵢ, vᵢ₊₁ is connected by a directed arc from vᵢ to vᵢ₊₁.
Define
Trees
An undirected graph is a tree, if it is connected and cycle-free (i. e., does not contain a cycle).
Define
Rooted tree
a.k.a. arborescence
Obtained from a tree by choosing an arbitrary vertex r as the root and
directing all edges away from r.
s-t connectivity problem
Is there a path between two given vertices s and t?
