1.   (a)  Let f1 (n) = n4 /log n, f2 (n) = n9 +2n , and g1 (n) = (n+1)4 , g2 (n) = 2n + p2n. 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 ann-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.

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 +4cinstead? Justify your answer.

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

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

Section B

1.   (a)  Suppose that you are given four numbers a,b,c,d with a < band 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.

Find astable 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 2 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.