Unit 2: Analysis of Algorithms and Graphs

Question 1

3 Common measures for the efficiency of algorithms

Answer 1

• Run-time
• Memory usage
• Problem-specific parameters (e.g. slow memory access, network usage).

Question 2

Random Access Machine

Answer 2

• There is exactly one CPU
• All data is in main memory
• All memory accesses require the same amount of time.

Question 3

4 Atomic operations

Answer 3

• Assignments: a←b
• Arithmetic operations: b ⏺ c with ⏺ ∈ { +, -, x, /, mod, ... }
• Logical operations: ∧, ∨, ¬, . . . .
• Comparison operations: a b with ∈ {<, ≤, =, 6=, >, ≥}.

Question 4

Run-time of an algorithm

Answer 4

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.

Question 5

Definition of Θ(g(n))

Answer 5

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 that
c₁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.

Question 6

Further asymptotic notation: Θ, O, Ω

Answer 6

• Θ 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.

Question 7

Definition of O(g(n)) :

Answer 7

O(g(n)) = { f(n) | there exist constants 0 ≤ c and n₀ such that
f(n) ≤ cg(n) for all n ≥ n₀}

Question 8

Definition of Ω(g(n))

Answer 8

Ω(g(n)) = {f(n) | there exist constants 0 ≤ c and n₀ such that
cg(n) ≤ f(n) for all n ≥ n₀}

Question 9

2 Properties of Θ

Answer 9

• cf(n) ∈ Θ(f(n))
• f(n) + g(n) ∈ max( Θ(f(n)), Θ(g(n)))

Question 10

Properties of Θ, O, Ω: “defining smaller order terms”

Answer 10

max( Θ(f(n)), Θ(g(n))) =
* Θ(f(n)) if g(n) ∈ O(f(n))
* Θ(g(n)) otherwise

Question 11

Dominance between functions

Answer 11

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

Question 12

Define:

Undirected Graphs

Answer 12

G = (V, E)
* V is the set of vertices
* E is the set of edges between pairs of vertices.

Question 13

Define:

Adjacency & Neighbours

Answer 13

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.

Question 14

Define:

Incident edge

Answer 14

Let e={v, u} be an edge in E, then
- v and e are incident

Question 15

Define:

Vertex degree

Answer 15

The number of edges incident to v.

Question 16

Define:

Multi-edge

Answer 16

More than one edge between the same two vertices.

Question 17

Define:

Loop

Answer 17

An edge between a vertex and itself.

Question 18

Define:

Simple graph

Answer 18

An undirected graph without multi-edges and loops.

Question 19

Define

Path

Answer 19

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 pair
vᵢ, vᵢ₊₁ is joined by an edge in E.

The length of a path is k − 1.

Question 20

Define

Cycle

Answer 20

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.

Question 21

Define

Path

Answer 21

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ᵢ₊₁.

Question 22

Define

Trees

Answer 22

An undirected graph is a tree, if it is connected and cycle-free (i. e., does not contain a cycle).

Question 23

Define

Rooted tree

a.k.a. arborescence

Answer 23

Obtained from a tree by choosing an arbitrary vertex r as the root and
directing all edges away from r.

Question 24

s-t connectivity problem

Answer 24

Is there a path between two given vertices s and t?

Question 25

s-t shortest paths

Answer 25

The length of a shortest path between s and t (i.e, the distance between s and t)?

Question 26

Define

Connectivity of an undirected graph

Answer 26

An undirected graph is connected if there is a path between every pair of nodes in the graph.

Question 27

Define

Disconnected graph

Answer 27

If the graph contains a pair of nodes without a path between them, the graph is not connected.

Question 28

Define

Subgraph

Answer 28

A graph G₁ = (V₁, E₁) is a subgraph of a graph G₂ = (V₂, E₂), if
V₁ ⊆ V₂ and E₁ ⊆ E₂.

Question 29

Define

Connected Component

Answer 29

A maximal connected subgraph of a graph is called a connected component.

A disconnected graph is the disjoint union of its connected components.

Question 30

Define

Strong connectivity

of nodes

Answer 30

Two nodes u and v are strongly connected if there is a path from u to v and vice versa.

Question 31

Define

Strong connectivity

of a directed graph

Answer 31

A directed graph is strongly connected if every pair of nodes is strongly connected.

Question 32

Define

Weak connectivity

of a directed graph

Answer 32

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.

Question 33

Define

Directed acyclic graph
(DAG)

Answer 33

A DAG is a directed graph with no directed cycles.

Question 34

Define

Topological ordering

of a directed graph

Answer 34

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ⱼ).

Question 35

Algorithm Run-time: Atomic Operations

Which operations are ignored / disregarded?

Answer 35

• Index calculations
• Type of operands
• Size of operands

Question 36

2 Examples of algorithms with constant growth Θ(1)

Answer 36

• Addition of two numbers (of constant size)
• Access to the ith element of an array of size n.

Question 37

Example of Algorithms that run in Logarithmic Time O(log n)

Answer 37

• Binary Search

Question 38

Binary search

Answer 38

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

Question 39

Example of linear growth algorithm O(n)

Answer 39

• Search for a maximum in an unsorted array.
• Merge two sorted lists

Question 40

An example of an algorithm with superlinear growth O(n log n)

Answer 40

• Mergesort

Question 41

An example of an algorithm with quadratic growth O(n²)

Answer 41

Find the closest pair of points in a list of point pairs.

Question 42

An example of an algorithm with cubic growth O(n³)

Answer 42

Disjoint sets

Let S₁, …, Sₙ be n subsets of {1…, n}.

Is there a pair of disjoint sets?

Question 43

Induced subgraph

Answer 43

(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₁.