Section A    Models of Computation

(Stefan Dantchev)

Question 1

(a)  Construct a Turing Machine that on input 0n , i.e.  n zeros, outputs the

number n in binary.

There is no need to give the precise transition function - you should explain how the machine works in plain English.  You may use multiple tapes in your machine.                                                                           [9 Marks]

(b)  Consider the problem of determining whether two Turing Machines A and

B  decide different  languages.   Prove that this  problem  is m-complete. [8 Marks]

(c)  Fix the tape language of a Turing Machine to be {0, 1, ⊔}. Let f (n) be the maximum number of steps that any Turing Machine with n states makes before it terminates when ran on the empty input. Are there computable functions g (n) and h(n) such that g (n) ≤ f (n) ≤ h(n) for every n? Justify your answers.   If h or g  exists,  provide a good  lower or  upper bound, respectively. The better bounds you give, the higher mark you will get.                                                                                          [8 Marks]

Question 2

(a)  Design a B¨uchi Automaton over the alphabet {0, 1, 2} that contains the

word  012  infinitely  often.    Briefly  explain  how your  automaton works. [7 Marks]

(b)  Let Σ be an alphabet consisting of at least two different symbols, and let

L be the following ω-language:

{w|w = uω  for some u ∈ Σ* }

Prove that L is not B¨uchi-recognisable.                                  [10 Marks]

(c)  Evaluate the Computation Tree Logic formula A(¬b U EXa) on all states of the model below and show all your work.        [8 Marks]

Section B    Algorithms and Complexity I

(Dani¨el Paulusma)

Question 3

(a)  Consider the fractional knapsack problem with weight limit W = 60 kilo-

grams and five items whose value vi  in euros and weight wi  in kilograms is given for 1 ≤ i ≤ 5 as follows:

Solve it using a greedy algorithm. Show all your work.             [8 Marks]

(b) The  triangle is the graph with vertices u,v,w  and edges uv , vw , wu.

A graph is triangle-free if G does not contain any triangle as a subgraph. Can the algorithm for computing a maximum matching in a bipartite graph that was discussed in the lecture be directly applied to work for triangle-free graphs? Justify your answer.                                                    [2 Marks]

(c)  Does there exist a graph whose vertex cover number is smaller than its matching number? Justify your answer.     [3 Marks]

(d)  Let c be a k-colouring of a graph G. That is, c is a mapping c : V (G) t {1, . . . ,k} such that c(u)    c(v) for every  pair of adjacent vertices u and v .  A colour class of c consists of all vertices of G that are mapped by c to a specific colour i.  We say that c is smart if the union of any two colour classes of c induces a cycle-free graph, that is a forest.   For example, if G is a cycle on four vertices, then G has no smart 2-colouring. Give a polynomial-time algorithm for deciding whether a cograph has a smart 3-colouring.       [12 Marks]

Section C    Algorithms and Complexity II

(Dr George Mertzios)

Question 4

(a) The output of Dijkstra’s algorithm is two arrays d and π, where d records

the distance from the source vertex to the other vertices and π records predecessors. Compute d and π when Dijkstra’s algorithm is performed on the weighted directed graph G represented by the adjacency matrix below, where the source vertex corresponds to the first row and first column of

(b) The weight of a cycle in an undirected graph with positive edge weights is

defined as the sum of the weights of the edges in the cycle.

Small Weight Cycle

Instance: an undirected graph G = (V,E) with positive weights on its edges, a path P in G, and a positive integer k .              Question: does G contain a cycle that includes all the edges of the path P and has weight at most k?

Large Weight Cycle

Instance: an undirected graph G = (V,E) with positive weights on its edges, a path P in G, and a positive integer k .              Question: does G contain a cycle that includes all the edges of the path P and has weight at least k?

i.  Provide a polynomial algorithm (without writing any pseudocode) and prove its correctness for Low Weight Cycle.       [8 Marks]