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?
s-t shortest paths
The length of a shortest path between s and t (i.e, the distance between s and t)?
Define
Connectivity of an undirected graph
An undirected graph is connected if there is a path between every pair of nodes in the graph.
Define
Disconnected graph
If the graph contains a pair of nodes without a path between them, the graph is not connected.
Define
Subgraph
A graph G₁ = (V₁, E₁) is a subgraph of a graph G₂ = (V₂, E₂), ifV₁ ⊆ V₂ and E₁ ⊆ E₂.
Define
Connected Component
A maximal connected subgraph of a graph is called a connected component.
A disconnected graph is the disjoint union of its connected components.
Define
Strong connectivity
of nodes
Two nodes u and v are strongly connected if there is a path from u to v and vice versa.
Define
Strong connectivity
of a directed graph
A directed graph is strongly connected if every pair of nodes is strongly connected.
Define
Weak connectivity
of a directed graph
A directed graph is called weakly connected if the underlying undirected graph, i.e., the undirected graph that one obtains by ignoring the direction of edges, is connected.
Define
Directed acyclic graph
(DAG)
A DAG is a directed graph with no directed cycles.
Define
Topological ordering
of a directed graph
A topological ordering of a directed graph G = (V, E) is a linear order of its nodes, denoted by v₁, v₂, ..., vₙ, such that i < j for every arc (vᵢ, vⱼ).
Algorithm Run-time: Atomic Operations
Which operations are ignored / disregarded?
- Index calculations
- Type of operands
- Size of operands
2 Examples of algorithms with constant growth Θ(1)
- Addition of two numbers (of constant size)
- Access to the
ith element of an array of size n.
Example of Algorithms that run in Logarithmic Time O(log n)
- Binary Search
Binary search
input: an increasingly sorted array A. And a value V.
calculate the center index s of A;
if A[s] = V then:
> print “found value”
else if V < A[s] then
> apply binary search to the subarray left of s;
else
> apply binary search to the subarray right of s
Example of linear growth algorithm O(n)
- Search for a maximum in an unsorted array.
- Merge two sorted lists
An example of an algorithm with superlinear growth O(n log n)
- Mergesort
An example of an algorithm with quadratic growth O(n²)
Find the closest pair of points in a list of point pairs.
An example of an algorithm with cubic growth O(n³)
Disjoint sets
Let S₁, …, Sₙ be n subsets of {1…, n}.
Is there a pair of disjoint sets?
Induced subgraph
(V₁, E₁) is an induced subgraph of (V₂, E₂) if it is a graph where V₁⊆V₂ and E₁ contains all edges of E₂ which are subsets of V₁.
