UNIVERSITY COLLEGE LONDON
Department of Mathematics
MATH0028- Combinatorial Optimization
2023 Main Summer Assessment Period
Duration: 3 hours (+ 30min upload window)
INSTRUCTIONS: (READ CAREFULLY!)
• All questions should be attempted. Marks obtained in all solutions will count.
• You may write your answers electronically or by hand. If you write your answer by hand, either take
a picture with your phone or scan them. You will be able to submit pdf or jpg files.
Tip: create a separate file for each question and name it using the question’s number, then you can
upload each file independently for each section. This will make the upload process a lot quicker.
• You are responsible for your images being legible. If they are not clearly legible, you will
receive no credit for your answer.
• Organize your work. Work that is scattered over the page, that has no clear order, that is messy
and illegible, might receive little credit.
• You may consult any books of your choice, any handouts and problem-set solutions distributed in
class, your own notes and problem sets, and any non-interactive publicly available Internet sources
(e.g. Wikipedia or the lecture notes of professors at other universities).
• The work you submit must be entirely your own. You must NOT copy material from anyone,
or discuss the questions with anyone, copy material from sources (unless you are quoting it with
attribution), make any posts on social media or e-mail, consult in any way with any other person,
or engage in any other form of academic misconduct.
Plagiarism, cheating, and collusion can have serious consequences, up to and including
loss of the degree.
If you have any issues or questions, contact math.ugexams@ucl.ac.uk.
Good luck!
MATH0028 Page 1 of 5
Question 1. (25 marks)
(a) Solve the following recurrence T (n) = 2T (n/2) + n log2 n + n, expressing your answer as
T (n) = Θ(f(n)) for some explicit function f(n). You may assume that n is a power of 2
and that T (1) = 1.
(15 marks)
(b) Suppose that we have two functions f, g : N→ N. Which of the following are true? Justify
your answers with a proof or counterexample.
(i) If f(n) = O(g(n)), then f(n) = O(n2g(n)).
(ii) If f(n) = Θ(g(n)), then (f(n) + g(n))2 = Θ(f(n)g(n)).
(10 marks)
MATH0028 Page 2 of 5
Question 2. (25 marks)
(a) Consider four job applicants a1, b1, c1, d1 applying to four firms a2, b2, c2, d2. The preferences
between the applicants and firms are given below.
1 2 3 4
a1 b2 c2 a2 d2
b1 c2 b2 d2 a2
c1 a2 d2 c2 b2
d1 d2 b2 a2 c2
1 2 3 4
a2 c1 b1 d1 a1
b2 a1 d1 c1 b1
c2 b1 c1 a1 d1
d2 d1 b1 a1 c1
Preferences of applicants a1, b1, c1, d1 Preferences of firms a2, b2, c2, d2
(i) Find a stable matching in this preference profile.
(ii) Is the stable matching you found in part (i) unique? Justify your answer by either
exhibiting another stable matching or proving that the one you found is unique.
(10 marks)
(b) In this question, your algorithms should run in the decimal model. You are allowed to use
standard results about running times of addition, subtraction, multiplication, division, and
comparison algorithms in this model.
Let SQUARE be the decision problem whose input is an n-digit positive integer x, with output
YES whenever x is a perfect square (i.e. when there exists some integer y with y2 = x).
(i) Write down an algorithm for solving SQUARE.
(ii) Show that SQUARE ∈ NP .
(15 marks)
MATH0028 Page 3 of 5
Question 3. (25 marks)
(a) In the following two questions you are asked to design a Turing machine whose input is a
binary string x1 . . . xn (i.e. with each xi ∈ {0, 1}). This means that at the start of the
computation entries 1, . . . , n on the tape contain elements of the string x1 . . . xn, while all
other entries contain the blank symbol “∗”. The r/w head should start at position 0 (i.e.
immediately to the left of x1). You do not need to justify that your Turing machines work
correctly in this question.
(i) Design a Turing machine whose input is a binary string x1 . . . xn, and which deletes the
first and last element i.e. it terminates with the tape containing x2 . . . xn−1 and with all
other entries blank.
(ii) Hence, or otherwise, design a Turing machine whose input is a binary string x1 . . . xn
with n odd, and whose output is YES whenever the middle element equals 1 i.e. when
x(n+1)/2 = 1. Show how your machine runs on input 101.
(15 marks)
(b) Your friend Max has £100 and wants to exchange this into dollars ($). Max’s bank deals with
pounds (£), dollars ($), euros (€), and yuan (¥), offering the following exchange rates for
converting currencies:
• $1→ £0.25 and £1→ $2
• $1→ €0.5 and €1→ $2
• $1→ ¥4 and ¥1→ $0.0625
• £1→ €2 and €1→ £0.5
• £1→ ¥8 and ¥1→ £0.0625
Max is wondering whether it is best to convert pounds £ directly to dollars $ (and end up with
100×2 = $200), or else whether it is better to convert it via some of the other currencies (e.g.
by converting pounds £ to yuan ¥ to dollars $, they would have 100× 8× 0.0625 = $50).
(i) By encoding this as a minimum cost path problem, or otherwise, determine the maximum
amount of dollars Max can obtain from £100. Give mathematical justification for your
answer being optimal.
(ii) Max tells you that the bank has opened the following line for converting between euro
and yuan “¥1→ €0.5 and €1 → ¥2”. How would your advice to Max change based
on this additional information?
(10 marks)
MATH0028 Page 4 of 5
Question 4. (25 marks)
(a) Suppose that the
(
5
2
)
= 10 edges of the complete graph K5 are given costs 1, . . . , 10 (i.e. so
that exactly one edge has cost i for each i ∈ {1, . . . , 10}). For each i, let ei be the edge with
cost i. Let T be a minimum cost spanning tree of K5 with this cost function. Which of the
edges e1, . . . , e10 are guaranteed to always be on T regardless of how the costs are arranged
around K5? Which of the edges e1, . . . , e10 are guaranteed to never be on T regardless of
how the costs are arranged around K5? Justify your answers.
(10 marks)
(b) In this question for a < b, we denote [a, b] := {a, a + 1, . . . , b}. For two disjoint sets
of integers A,B, define a bipartite graph G(A,B) with vertex set A ∪ B, and edge set
{ab : a ∈ A, b ∈ B, b 6≡ 0 (mod a)}. In other words, a ∈ A is joined to b ∈ B whenever b is
not divisible by a.
(i) Draw the graphs G([2, 4], [5, 7]) and G([2, 4], {8, 7, 16}). Find maximum matchings in
each of these graphs, and provide justification for them being maximum.
(ii) By finding a matching in G([2, n], [2n, 3n + 1]), or otherwise, show that for all n ≥ 2,
one can find distinct integers x2, . . . , xn ∈ [2n, 3n+ 1] such that for each i = 2, . . . , n,
we have xi not divisible by i.
(15 marks)
MATH0028 Page 5 of 5