Description
Problem 1.1: minimum spanning trees (3 points)
We have introduced Kruskal’s algorithm for constructing random spanning trees (maze solutions).
Edges are selected randomly and added to the spanning tree as long as the nodes connected
by the edges belong to different equivalence classes. The original algorithm solves a slightly
more difficult problem: Given a graph G = (V, N) and a cost function c that indicates the cost of
including the edge e ∈ N in the spanning tree, calculate the spanning tree S = (V, E) such that
C =
P
e∈E
c(e) is minimal (also called a minimum spanning tree). Kruskal’s algorithm solves this
problem by selecting in each step an edge that joins two equivalence classes and has the minimum
cost of all edges still available.
You are given the graph G = (V, N) with
V = {a, b, c, d, e, f}
N = {(a, b),(a, e),(a, f),(b, c),(b, f),(c, d),(c, f),(d, e),(d, f),(e, f)}
and the cost function c defined by the following table:
edge e: (a, b) (a, e) (a, f) (b, c) (b, f) (c, d) (c, f) (d, e) (d, f) (e, f)
cost c(e): 10 9 8 7 6 5 4 3 2 1
Construct a minimal spanning tree S(V, E) using Kruskal’s algorithm. For each step, write down
the set of equivalence classes A and the edges in E. What is the overall cost C of the resulting
spanning tree? You start with:
E = {} initialization, C = 0
A = {{a}, {b}, {c}, {d}, {e}, {f}}
E = . . . step 1, C = . . .
A = . . .
E = . . . step 2, C = . . .
A = . . .
. . .
Problem 1.2: boyer moore algorithm (2+2+2 = 6 points)
You have designed a simple robot that can turn left (L), turn right (R), move one step forward
(F), and pause (P) for short time. The robot is programmed by a sequence of robot instructions.
For example, the sequence FFLFLFRFRFFLFRF will direct the robot through the maze shown
on the slides discussing maze generation algorithms. Using the Boyer Moore algorithm, we can
determine whether a robot program contains certain movement sequences.
Let Σ = {L, R, F, P} be an alphabet and t ∈ Σ
∗ be a text of length n describing a program for the
robot. Let p ∈ Σ
∗ be a pattern of length m. We are looking for the first occurrence of p in t.
Consider the text t = F F LF LF RF RF F LF RF and the pattern p = F F LF R.
a) Execute the naive string search algorithm. Show all alignments and indicate comparisons performed by writing uppercase characters and comparisons skipped by writing lowercase characters. How many alignments are used? How many comparisons are done?
b) Execute the Boyer-Moore string search algorithm with the bad character rule only. How many
alignments are used? How many comparisons are done?
c) Calculate the lookup table for the bad character rule that indicates the number of alignments
that can be skipped if a comparison does not match.
Problem 1.3: big O notation (1+1 = 2 points)
a) Sort the functions
f1(n) = 1
2
n log n
f2(n) = n
2
f3(n) = √
n3
f4(n) = n
n
f5(n) = 100n
2 + 10n
3
f6(n) = 2 log n
f7(n) = (n
2
)
2
f8(n) = log log n
in increasing order concerning their big O membership. (It is sufficient to provide the correct
order.)
b) Given the functions f, g, h : N → N, show that the following transitivity property holds: If
f ∈ O(g) and g ∈ O(h), then f ∈ O(h).
