MATH0028 Exam 2022

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

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

1

2

2

2

2

2

1

2

2

2

2

2

1

2

2

2

2

2

1

2

2

2

2

2

1

2

2

2

2

2

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

 

1

2

3

4

5

2

1

1

1

1

1

2

1

1

1

1

1

2

1

1

1

1

1

2

1

1

1

1

1

2

1

1

1

1

1

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 s 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.

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.

3

2

3             4

3             3

1

k

4

2

4

g

l

4                           3

3

(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.


2023-04-14