1.   (a) Let f1 (n) = n4 / log n, f2 (n) = n9 + 2n , and g1 (n) = (n + 1)4 , g2 (n) = 2n +,2n . Decide if fi (n) = O(gj (n)) and fi (n) = Ω(gj (n)) for every pair i, j .

(b)  Solve the following recurrence T (n) = T (n/8)+T (n/4)+T (n/2)+n2 , expressing

your answer as Θ(f (n)) for a suitable function f depending only on n.  You may assume that n is a power of 2.

(c) Describe an algorithm for determining if an n-digit positive integer a is divisible by  7.   Your algorithm should work in the decimal model and run in time O(nk ) for some integer k.  You may assume any facts about running times of multiplication, addition, subtraction, and comparison algorithms that you require.

2.  Consider the following digraph G.

5

 y

x

  2 

1

In all the following, justify your answers carefully.

(a) Thinking of the numbers on the edges as costs, find minimum cost paths from

x to all other vertices. Give your output as a feasible potential and predecessor map.

(b) Find a minimum cost path from x to y in G.

(c) Now thinking of the numbers on the edges as capacities, find a maximum flow from x to y in G.

(d) Find a minimum x-y cut in G.

(e) Find a maximum collection of edge-disjoint paths between x and y .

3.   (a) Let G be a graph with a cost function c such that the costs of all the edges are distinct. Prove that G has a unique minimum cost spanning tree. Give an example of a graph H and a cost function such that H has two minimum cost spanning trees which are edge-disjoint — meaning that each edge of H is in at most one of the trees.

(b) Let G = (V, E) be a graph with a cost function c : E 二 N on its edges. Let T

be a minimum cost spanning tree for the cost function c.  Is it true that T is also a minimum cost spanning tree if we used the cost function c2 + 4c instead? Justify your answer.

(c)  Consider the following graph G and cost function on its edges

  y 

Find a minimum cost spanning tree on G.  Does G contain a minimum cost spanning tree which contains the edge xy? Justify your answers.

1.   (a)  Suppose that you are given four numbers a, b, c, d with a < b and c < d. Design an algorithm to sort these numbers into increasing order using 3 comparisons. Present your solution as a height 3 decision tree. Show that it is impossible to solve this task using just two comparisons.

(b) Design a Turing Machine which works on the alphabet {*, 1, 2} which moves

right along the tape until it sees a 2, then erases everything to the right of this 2 (by writing “ *”s) until it sees another 2, and then halts.  Run your Turing Machine on the input “ . . . , *, 1, 2, 1, 1, 1, 2, 1, * . . . ” (with the machine starting on the underlined position), describing the state of the machine at each step.

(c)  Consider five job applicants a1 , b1 , c1 , d1 , e1 applying to five firms a2 , b2 , c2 , d2 , e2 . The preferences between the applicants and firms are given below.

Preferences of applicants a1 , b1 , c1 , d1 , e1

Preferences of firms a2 , b2 , c2 , d2 , e2

Find a stable matching of applicants to firms. Is the matching a1 b2 , b1 a2 , c1 c2 , d1 e2 , e1 d2 stable? Justify your answers.

2. We say that a graph G is k-colourable if there is a function c : V (G) 二 {1, . . . , k} such that c(u)  c(v) for every edge uv e E(G).

(a)  Show that a graph G is 2-colourable if, and only if, it contains no odd length

cycle.

(b)  Consider the decision problem  “k-COLOURABLE” which takes an n-vertex

graph as an input and checks whether it is k-colourable. Describe an algorithm for the task 3-COLOURABLE. Write down an explicit function f so that the running time of your algorithm is O(f (n)) (you do not need to prove that your answer is correct, only write down a function f).

(c)  Show that 3-COLOURABLE is in Np .

(d)  Show that 2-COLOURABLE is in p .