Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CS260: Algorithms
Coursework 1
Submit a PDF file (with A4 size pages) to Tabula.
Your work must be at most 2 pages of size A4 (portrait) long, with blank margins at least 2cm
wide all around, typeset using a 11-point font (or larger) or handwritten with letters of at least 4mm
in height. At the top of every page, please put (1) the page number and (2) the total number of
pages in your submission. (Example: page 1/2.) Only the first 2 pages will be marked.
A sample solution of the coursework will be available on Moodle on 3 November in the afternoon.
Therefore, work submitted after Wedensday 3 November 2021 at 12 noon will NOT be
accepted. Fill a Mitigating Circumstances form on Tabula if you are not able to submit on time.
Advice on writing down your solutions
When presenting algorithms, you may use high-level pseudocode or “structured English” similar
to those used in the sample solutions, in the textbook, or in the lecture materials. If your pseudocode
is more than a few lines, it is also advised to provide brief algorithm summaries that highlight the
key ideas and concepts behind the design of your algorithms. If you need to use standard algorithms
(those covered in lecture materials or in the predecessor module CS126), do not reproduce them,
and instead please refer to them clearly.
Whenever you present an algorithm that you are asked to design, justify its correctness and
analyze its asymptotic running time. Your arguments should be logically coherent, use rigor-
ously defined concepts, and avoid ambiguity. All non-trivial claims and non-standard assumptions
should be clearly stated and justified.
Assessment criteria for the CS260 coursework, the class test, and the exam include:
understanding of the fundamental concepts and results, and the ability to apply them in
context,
clarity and succinctness of presentation,
coherence and rigour of arguments,
completeness of solutions,
correctness of reasoning and of algorithms,
efficiency of algorithms,
creativity of problem solving.
Verbosity often hurts clarity. Please be concise.
We wish you success.
1
For an undirected graph G = (V,E), we say that a set D ⊆ V of vertices is a dominating set if every
vertex that is not in D has an edge to a vertex in D. An undirected graph without cycles is called
a forest; its connected components are trees.
In this problem you are asked to develop a polynomial-time algorithm for computing a minimum-size
dominating set in a forest.
You can assume that a forest is represented by the set of vertices V = {1, 2, . . . , n}, and an
array p[1..n], such that for every vertex v ∈ V : either v is a root of a tree and p[v] = v, or p[v] 6= v
and p[v] is the parent of v.
For example, the set V = {1, 2, 3, 4, 5, 6} and the array:
Vertex v 1 2 3 4 5 6
Parent p[v] of v 1 3 3 5 3 5
represent the following forest:
in which vertices 1 and 3 are the roots of the two trees in the forest. For vertices v and w, such that
v 6= w, we say that v is a child of w if p[v] = w.
(a) [12 marks] Is {1, 3, 4, 6} a dominating set in the above example?
Give a dominating set of size 3.
(b) [12 marks] A stranger is a vertex that is a root with no children.
List all strangers in the above example.
Argue that every stranger in a forest must belong to every dominating set.
(c) [20 marks] A leaf is a vertex that has no children. A young parent is a vertex that is not a
leaf and whose all children are leaves.
List all leaves and young parents in the above example.
Prove that if a vertex in a forest is a young parent then it belongs to some minimum-size
dominating set.
(d) [20 marks] Prove that every tree with at least two vertices contains a young parent.
(e) [36 marks] Describe a polynomial-time algorithm that—given a forest—computes a mini-
mum-size dominating set. You may use the facts from parts (b)–(d) to justify the correctness
of your algorithm.
In order to achieve maximum credit, your algorithms must run in linear time.