1(a) Decide which of the following statements is true or false, by proving it or by giving a counterexample:  (i) f(n) = Ω(nlog n) implies f(n) = Ω(n2 ) and (ii) g (n) = O(ep log n) implies g (n) = Θ(n/log n).

1(b) Let T(V, E) be a rooted tree in which every vertex has degree at most 3.  Assume the longest simple path starting at the root has h edges. Show that T has at most 3h  leaves.

1(c) Solve the recurrence T(n)  =  T(n/2) + 2T(n/8) + n3 .   You  may assume that n is a power of 2.   Is this  recurrence covered by the general theorem?

2(a) Show that if a graph G(V, E) has two distinct spanning trees, then |E| ≥ |V | .  Is it true that if G has three distinct spanning trees, then |E| ≥ |V | +1?

2(b) Let G(V, E) be a graph with cost function c  : E  一 R and T a minimum cost spanning tree. Assume c(e) > 0 for all e e E.  Does it follow that T is a minimum cost spanning tree in G for the cost function c2 (e)?

2(c) In the network G(V, E) the vertices are s,a,b,c,d,e,t with s the source and t the sink.  The arcs and their capacities are given by u(sa) = 3, u(sc) = 2, u(se) = 3, u(ab) = 4, u(ba) = 2, u(ac) = 1, u(ce) = 4, u(bt) = 3, u(db) = 2, u(dt) = 1, u(ed) = 1, u(et) = 2.  We define the flow x : E 一 R by x = 1 on every arc except x(ce) = 2.  Is this flow feasible?  What is the total flow fx?  Find a maximal s - t flow and a minimal s - t cut in this network.

3(a) Explain how the shortest augmenting path algorithm works.  State the two lemmas needed for its validation.  Show how they imply that the complexity of the algorithm is O(mn3 ).

3(b) Let G be a bipartite graph with bipartition classes P and Q. Assume G has  16 vertices of degree 5, the rest of the vertices have degree 8.   All vertices with degree 8 are in Q. How many vertices can G have?

3(c) Let G(V, E) be a bipartite graph with bipartition classes P and Q. Assume that degp = a for every p 2 P and degq = b for every q 2 Q and a ≥ b.  Show that G contains a matching of size  |P| .  Does it also contain a matching of size |Q|?

4(a) Find a girl-optimal and stable matching when the girls are G = {1, 2, 3, 4}, the boys are B = {a,b,c, d} and the preference lists are

L1  = (a,b,c, d), L2  = (c,a,d, b), L3  = (a,d,b, c), L4  = (d,a,c, b),

La  = (2, 3, 4, 1), Lb  = (2, 3, 4, 1), Lc  = (3, 1, 4, 2), Ld  = (1, 2, 4, 3). Is the girl-optimal stable matching unique?

4(b) Assume that in an instance of the stable matching problem, girl g 2 G is the first on the preference list of a boy b 2 B, and b is also the first on g ’s preference list.  Show that there is a stable matching where g and b form a couple. Is this true in every stable matching?

4(c) Show that every positive integer n can be written in the form

n = a0  + a131 + a232 + ... + ak 3k

where each ai   e  {0, 1, 2} and ak     0.   Devise and algorithm whose input is n in decimal and its output is the numbers a0 , a1 ,..., ak .  What is the complexity of the algorithm?

5(a) Describe informally the Turing machine that computes the remain- der modulo 8 of a positive integer n which is given as a binary string s.  Give also the first two moves formally.

5(b) Show that the Decision Problem:  SAT is polynomial time reducible to the Decision Problem: IndepSet.

5(c) A Hamilton path in a directed graph G(V, E) is a simple directed path containing all vertices.  The input to the Decision Problem:  HamPath is a digraph G(V, E) and the answer is YES if G contains a Hamilton path. Show that HamPath is in the class ⅥP.   Show  also  that  HamCycle  p HamPath. Is the Decision Problem: HamPath NP-complete?