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