ICS - Sheet 1 - Solved

Introduction to Computer Science
(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 = Pe∈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 = FFLFLFRFRFFLFRF and the pattern p = FFLFR.

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

 

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