Solutions to resit exam paper MATH0028, 2019

1(a) Let f(n) and g (n) be positive functions.   Give  the  definition of f(n) = Ω(g (n)).  Decide if the following statements are true or false and jus- tify your answer:  (i) f(n)+ g (n) = Θ(min{f(n), g (n)}), (ii) f(n) = O(g (n)) implies g (n) = Ω(f(n)).

Answer: We say that f(n) = Ω(g (n)) if there are constants c > 0 and n0  such that for all n ≥ n0 , f(n) > cg(n).  (i) is false:  let f(n) = 1 when n is even, and f(n) = n when n is odd, and let g (n) = 1 when n is odd, and g (n) = n when nis even. Thenf(n)+g (n) = n+1 while min{f(n), g (n)} = 1. But (ii) is true as f(n) = O(g (n)) means that there are numbers c > 0 and n0 such that 0 < f(n) < cg(n) for all n > n0 , and so indeed g (n) > c-1 f(n) > 0 for n > n0 .

1(b) What is the input and the output of a sorting algorithm?  What is the size of the input in the arithmetic model?  State and prove the theorem on the lower bound for the running time of comparison sorting algorithms.

Answer:  The INPUT is a sequence a1 , a2 ,..., an   of natural  (or real) numbers. The OUTPUT is the same sequence in increasing order. The size of the input in the arithmetic model is just n. Theorem: The running time of every comparison sorting algorithm is Ω(nlog n). Proof. In the decision tree corresponding to the given comparison algorithm every node (except for the leaves) represents a comparison of two elements of the input.  The work of the algorithm, on a given input, is given by a path P from the roof to a leaf, and the sequence of comparisons the algorithm carries out is represented by the sequence of nodes on P.  P ends with a leaf that represents the output permutation. Thus the decision tree has to have at least n! leaves as distinct permutations correspond to distinct leaves. The running time is the length, h, of the longest path from root to leaf in the decision tree, which is the same as the height of the tree.  We use the fact that a binary tree of height h has at most 2h   leaves.   Then n!    2h   implying  that the running time, T(n) = h ≥ log2 (n!) = Ω(nlog n).

1(c) Show that the solution to the recursion T(n) = 3T(n/3) + 2n is O(nlog n).

Answer: We show that T(n)  c1nlog n + c2n by induction which gives T(n) = 3T(n/3)+2n  3[c1n/3log n/3+c2n/3]+2n = c1nlog n−c1nlog 3+ c2n + 2n which is at most c1nlog n + c2n if 2n − c1nlog 3    0.   The last condition holds if c1   ≥ 2/log 3.  The case n =  1 implies that T(1)   c2 . Alternatively, Case 2 of the general theorem for recursions applies here with a = b = 3, D = 1 and f(n) = n = Θ(n), giving the same result.

2(a) Give the definition of a subgraph and of a spanning subgraph of a graph G. Show that if a tree T has at least two vertices, then it has at least two leaves.

Answer:  The graph H  is a subgraph of the graph G by definition if V (H) 军 V (G) and E(H) 军 E(G). A subgraph is spanning i↵ V (H) = V (G). For the proof of the statement, consider the longest simple path P in the tree. P goes through vertices v0 , v1 ,...,vk  in this order; here k ≥ 1 as T has at least two vertices. Claim: v0  and vk  are leaves. If v0 , say, were connected to vertex u  v1 , then u cannot be on P as a tree contains no cycle, and then u, v0 ,...,vk   would be a simple path longer than P, contrary to our assumption.

2(b) State the Minimum Spanning Tree problem. Explain how Kruskal’s algorithm works. Show that any Minimum Spanning Tree problem can be reduced to another one (on the same graph) with positive costs only.

Answer: The INPUT is a connected graph G(V, E) and a cost function c : E 一 R. The OUTPUT is a spanning tree G having minimum cost, where the cost of a tree T  is c(T) =Pe2E(T) c(e). Kruskal’s algorithm grows a spanning forest H(V, F). The starting forest is H(V, Q). On each iteration add to H a least cost edge e  F so that H + e remains a forest. For the reduction define the new cost of arc e as c* (e) = c(e) + K for all e E E(G), where K isso large that the new cost function c*  is nonnegative, for instance K  = 1 + max{-c(e) : e  E  E(G)}  will do.  For a spanning tree T  of G, c* (T) = c(T) + (n - 1)K, where n = |V (G)|. Thus minimum cost spanning trees for the old and new problem coincide.

2(c) Give the definition of a feasible potential on a digraph G with cost function c and root r  E V (G). Describe how Ford’s algorithm works, and state the justification theorem for it.

Answer:  A feasible potential is a function y : V 一 R satisfying yr  = 0 and yv +c(vu) ≥ yu  for every arc vu E A. In Ford’s algorithm, initially yr  = 0 and p(r) = 0 and yv  = 钝 and p(v) = -1 for all v E V (G) di↵erent from r , where p is the predecessor function. An arc vu is incorrect if yv +c(vu) < yu. Ford’s algorithm: as long as there is an incorrect arc vu, correct it by setting yu  = yv  + c(vu) and p(u) = v. Justification Theorem. If there is no negative cost directed cycle, then at every stage of Ford’s algorithm (1) if yv    钝, then yv  is the cost of a simple r - v dipath, (2) if p(v)  -1, then p defines a simple r - v dipath of cost at most yv .

3(a)  Give the definition of a feasible flow in a digraph G(V, E) with specified source r and sink s and capacity u : E 一 R. Assume x1  and x2  are feasible flows. Show that x  condition is x1 + x2  a feasible flow?

Answer:  A flow in a digraph G(V, E) is a function x : E 一  R that satisfies the conservation law at every v e  V / {r, s}:  Pz:zv=E x(zv) = Pw:vw=E x(vw). It is feasible if 0  x(e)  u(e) for every e e E.

For an internal node v the netflow of x at v is just half of the sum of the netflows of x1  and x2  at v, so it equals zero. Thus x is a flow, again. It is feasible if it satisfies the capacity constraints, that is, if 0  x(e)  u(e) for every arc e in the network. Here 0  x(e) is satisfied as x1 (e), x2 (e) ≥ 0. Also, x1 (e), x2 (e)  u(e) for every arc e e E sox(e)  u(e) as well. Similarly, 2x = x1  + x2  is always a flow, and it is feasible i↵ x1 (e) + x2 (e)  u(e) for every e e E, as the other conditions are automatically satisfied.

3(b) Give the definition of an x-augmenting and of an x-incrementing path in a network. State and prove the Max-Flow Min-Cut theorem.

Answer:   Given a feasible flow x, an undirected r - s path P is x- augmenting if x(e) < u(e) on forward arcs and x(e) > 0 on backward arcs. Such a path between rand some v e V is called an x-incrementing r-v path. Max-Flow Min-Cut theorem: If there is a feasible r - s flow of maximum value fx , then fx  = min{u(δ(R)) : δ(R) is an r - s cut}. Proof. Let x be a flow of maximum value. Then there is no x-augmenting path because if there were one, say P, then changing x(e) to x(e) + ↵ on forward arcs and to x(e) - ↵ on backward arcs in P (for small enough ↵ > 0) would result in anew feasible flow with total flow larger than fx. Define R as thesetv e V for which there is an x-incrementing r - v path. Then r e R and s e R. Moreover, vw e δ(R) implies that x(vw) = u(vw) and vw e δ(R) implies that x(vw) = 0. Thus indeed fx  = x(δ(R)) - x(δ(R)) = u(δ(R)).

3(c) Let G be a bipartite graph with bipartition classes P and Q. State K¨onig’s theorem on the existence of a matching of size |P| in G. Show further that if G is k-regular and k ≥ 1 then |P| = |Q| .

Answer:  K¨onig’s theorem states the following. There is a matching of size |P|  in G i↵ |N(A)|  ≥  |A|  for every A 军  P. Here N(A) is the set of vertices v e V / A such that there is a e A with va e E.

The last statement follows by counting the number of edges, |E|, in two ways: the number of edges leaving P is k|P| = |E|, and the number of edges leaving Q is k|Q| = |E|, and k|P| = k|Q| implies |P| = |Q| as k  0.

4(a) Give an algorithm that decides whether a connected graph is bipar- tite or not.

Answer: Starting with a vertex r 2 V determine the shortest path from r  to v  for all v   2 V.  Colour v  Red if the length of the shortest r  − v path is even. Colour it Blue otherwise.  Claim: G  is bipartite i↵ there is no monochromatic edge. The proof is easy: if there is no such edge, then the Red and Blue vertices form a bipartition of G. If there is such an edge, e = pq , say, then G contains an odd cycle, namely the shortest path from r to u and to v plus the edge e. Observe finally that a bipartite graph contains no odd cycle.

4(b) State the Stable Matching problem. Use the Gale-Shapley algorithm to find a stable matching when the set of girls is G = {1, 2, 3}, the set of boys is B = {a,b, c}, the preference lists are L1  = (c,a, b), L2  = (c,b,a), L3  = (a,b, c) for girls and La  = (2, 1, 3), Lb  = (3, 1, 2), Lc  = (3, 2, 1) for boys.

Answer:  The INPUT is a set of girls, G, and a set of boys, B  with |G| = |B| = n, and for each g 2 G a preference list of the boys, and for each b 2 B, a preference list of the girls. The OUTPUT is a Stable matching, that is, a pairing (g1 , b1 ), . . . , (gn, bn ) with every girl and boy appearing exactly once which is stable in the sense that for no gi  and bj  with i  j , gi  prefers bj  to bi  and bj  prefers gi  to gj . Using the Gale-Shapley algorithm one gets the stable matching (1, a), (2, c), (3, b).

4(c) Describe Karatsuba’s algorithm for the multiplication of two positive integers given as binary strings. Write down the recursion for the running time of the algorithm.

Answer: The INPUT is positive integers a and b, and the OUTPUT is ab. Assume a and b are given as binary strings of length n: a = a1 ...an  and b = b1 ... bn. We assume n is even n = 2k (which only changes the input size by 1 at most). Write a = A12k +A2 and similarly b = B12k +B2. Clearly A1  = a1 ...ak  and A2  = ak+1  ... an  in binary, and similarly for B1 , B2 . Karatsuba’s method computes C1  = A1 B1 , C2  = A2 B2  and C3  = (A1 +A2 )(B1 +B2 ) and C4  = C3 − C1 − C2. Now ab = A1 B122k +(A1 B2 +A2 B1 )2k +A2 B2  = C122k + C42k + C2. Here multiplications by 2n  and 2k   are appending n or k zeros to the string C1  and C4 , each at most n operations. There are 3 multiplications of k  digit numbers, which is 3T(k) operations, and a few additions of at most 2n  digit numbers that take O(n) operations.  We get the recursion T(n) = 3T(n/2) + O(n), whose solution is T(n)  O(nlog23) ⇡ O(n1.595 ).