Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
MATH0028
All questions should be attempted. Marks obtained in all solutions will count.
Section A
1. (a) Solve the following recurrence: T (n) = 3T (n/4)+T (n/2)+n2. You may assume
that n is a power of 2, and that the initial value T (1) is positive. Express your
answer as T (n) = Θ(f(n)) for some suitable function f .
(b) Which of the following are true? Justify your answers
There is a function f with f(n) = O(n4 − 3n2) and f(n) = Ω(10n3).
If g(n) = Θ
(
210
√
log2 n
)
, then g(n) = O(n2).
2. In the following, justify your answers
(a) Let G be a bipartite graph with 8 vertices in total, having 4 vertices in each
part. If G has no perfect matching, then what is the most edges that G can
have?
(b) 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.
1 2 3 4 5
a1 a2 b2 e2 d2 c2
b1 b2 c2 d2 a2 e2
c1 c2 d2 a2 b2 e2
d1 a2 b2 e2 c2 d2
e1 b2 c2 e2 a2 b2
1 2 3 4 5
a2 b1 c1 d1 e1 a1
b2 c1 d1 e1 a1 b1
c2 d1 e1 a1 b1 c1
d2 a1 e1 d1 c1 b1
e2 a1 d1 b1 e1 c1
Preferences of applicants a1, b1, c1, d1, e1 Preferences of firms a2, b2, c2, d2, e2
Find a stable matching in this preference profile. Is there a stable matching in
which a1 gets paired with e2? What about a1 getting paired with a2?
(c) Let T be a tree in which every vertex has degree 1 or 2. Prove that T is a path.
3. Consider the decision problem SHORTCYCLE whose input is a directed graph G
on n vertices and whose output is YES whenever G has a cycle of length 6 n/2.
(a) Give a YES instance for the decision problem SHORTCYCLE. Give a NO in-
stance for the decision problem SHORTCYCLE.
(b) Give an algorithm for solving the decision problem SHORTCYCLE. Write down
a function so that the running time is O(f(n)).
(c) Is SHORTCYCLE in NP? Justify your answer.
MATH0028
4. (a) Consider the following graph with cost function as shown. Find a spanning tree
whose cost is as large as possible in this graph. Justify your answer.
(b) Consider the following digraph with capacities as shown. For the edge ag the
capacity is some unknown positive real number x. For each x > 0, find the
value of the maximum flow from a to k in the graph. Justify your answer.
(c) Give a Turing machine which tests for divisibility by 6. Show how your machine
runs on the input 366.