1213-1 COMPSCI 720 (21/06/2021 17:30) Adv Design and Analysis of Alg (Exam)
By submitting this assessment, I agree to the following declaration:
As a member of the University’s student body, I will complete this assessment in a fair, honest,
responsible and trustworthy manner. This means that:
· I will not seek out any unauthorised help in completing this assessment. (NB. Unauthorised help
includes a tutorial or answer service whether in person or online, friends or family, etc.)
· I will not discuss or share the content of the assessment with anyone else in any form, including
but not limited to, Canvas, Piazza, Chegg, Facebook, Twitter, Discord or any other social media
within the assessment period.
· I will not reproduce and/or share the content of this assessment in any domain or in any form
where it may be accessed by a third party.
· I am aware the University of Auckland may use Turnitin or any other plagiarism detecting
methods to check my content.
· I declare that this assessment is my own work, except where acknowledged appropriately (e.g.,
use of referencing).
· I declare that this work has not been submitted for academic credit in another University of
Auckland course, or elsewhere.
Note: Include as applicable e.g., STEM subjects (Science, Technology, Engineering and
Mathematics)
? I declare that I generated the calculations and data in this assessment independently, using only
the tools and resources defined for use in this assessment.
? I declare that I composed the writing and/or translations in this assessment independently, using
only the tools and resources defined for use in this assessment.
I understand the University expects all students to complete coursework with integrity and
honesty. I promise to complete all online assessment with the same academic integrity standards
and values.
Any identified form of poor academic practice or academic misconduct will be followed up and
may result in disciplinary action.
I Agree
1213-1 COMPSCI 720 (21/06/2021 17:30) Adv Design and Analysis of Alg (Exam)
2/2
1 Please answer all the questions and upload your answers in a single PDF file.
You can also download the questions here: COMPSCI 720 S1 2021
Please make sure that any documents you scan are in portrait orientation when uploading your
answers before the time ends. We recommend Adobe Scan to scan your work before
submission. Adobe Scan is freely available and lets you rotate each page if necessary.
Best of luck!
Upload a single pdf file in portrait format here:
The following file types are allowed: .pdf Maximum file size is 1 GB
Select file to upload
Maximum marks: 60
Question 1
Attached
- Combinatorial Objects.
To test your understanding about the bijection between labeled trees and Pru¨fer sequences, for
this question submit a solution (program) for the following problem to the automarker at: http:
//www.automarker.cs.auckland.ac.nz.
The input will be a single line of 1 < n ≤ 50000 (white-space separated) sequence of integers
S = s0 s1 · · · sn?1, where 0 ≤ si < n and si 6= i. This denotes a labeled tree of n nodes (labeled - to n? 1) that is constructed as follows. The integer si in position 0 ≤ i < n denotes the label of
an adjacent node of node i (that is, {si, i} is a tree edge). Note that since a tree has only n?1 edges
one of these edges will be duplicated on the input line, as {si = x, i = y)} = {sj = y, j = x}.
You can assume the edge connections generate a connected acyclic graph (a tree).
The output of your program should be one line of n? 2 integers denoting its corresponding Pru¨fer
sequence over {0, 1, . . . , n? 1}. There will be ten (10) input cases, each worth one mark.
Sample Input: - Treewidth and Pathwidth.
(a) For the following graph compute its pathwidth and treewidth and give a path decomposition
and a tree decomposition that corresponds to the smallest width(s).
(6 marks)
(b) Show that you can use a DFS (Depth-First-Search) of a graph to find an approximation tree-
decomposition of width at most the distance any back-edge reaches up the tree (e.g. its
treewidth is bounded above by the longest cycle length detected).
(4 marks)
2 - t-parse Algorithms.
For this question we assume we have the simple variation of the Weighted Independent Set problem
that was a part of your Assignment 2.
Problem: WEIGHTED INDEPENDENT SET (WIS)
Input: (undirected) Graph G = (V,E) with vertices labeled 0, 2, . . . , |V | ? 1.
Question: Let the weight of each vertex be its graph index (label).
What is the largest sum of vertex weights over all independent sets of vertices?
That is, maxV ′?V
∑
v∈V ′ int(v) where for all {v1, v2} ? V ′ we have (v1, v2) 6∈ E.
(a) For the following two t-parses, give the corresponding graph adjacency lists, as we interpreted
them in class. - (10 20 0 10 21 1 21 10)
- (( 10 20 0 10 21 1 21 10) (20 0 20 0 10 0) 1 10 21 )
(3 marks)
(b) What is the answer to the WIS problem on the two graphs given in part (a)?
(2 marks)
(c) Assume we have a pathwidth t-parse of a graph G. Describe a linear-time algorithm that can
solve the WIS problem.
(3 marks)
(d) Assume we have a treewidth t-parse of a graph G. Show how one can extend your algorithm
of part (c) for the WIS problem.
(2 marks)
3 - Parameterized Algorithms.
(a) In your own words, describe what it means for a reduction rule to be safe.
(2 marks)
(b) Let G be a graph with vertex set V . Let H and I be subsets of V with H ∩ I = ?, I is an
independent set of G, and H precisely contains all neighbors of vertices in I . Assume that
|I| < |H|. Is it possible for the vertices in H ∪ I to form a crown of G? Explain your answer.
(2 marks)
(c) Recall the INDEPENDENT SET problem which is formally stated as follows.
Instance. A graph G = (V,E) and a non-negative integer k.
Question. Is there a subset S ? V with |S| ≥ k such that, for all pairs of two distinct ele-
ments u and v in S, we have that {u, v} is not an edge in E?
Is INDEPENDENT SET restricted to graphs for which the maximum degree d of a vertex is a
constant fixed-parameter tractable when parameterized by k? Explain your answer.
(3 marks)
(d) Consider the TRIANGLE VERTEX DELETION problem which is formally stated as follows.
Instance. A graph G = (V,E) and a non-negative integer k.
Question. Are there k vertices in V whose deletion from G results in a graph that has no
cycle of length three?
Show that TRIANGLE VERTEX DELETION is fixed-parameter tractable when parameterized
by k. To this end, describe a depth-bounded search tree algorithm to solve any given instance
of TRIANGLE VERTEX DELETION and give the algorithm’s running time.
(3 marks)
4 - Approximation Algorithms.
(a) Is the 2-approximation algorithm for the (unweighted) VERTEX COVER problem that we
discussed in class tight? Explain your answer.
(2 marks)
(b) What does it mean for a problem P to have an r-approximation with r = 2?
(2 mark)
(c) Consider the 3-MATCHING problem which is formally stated as follows.
Instance. A set S = {s1, s2, . . . , sn} and a set T = {T1, T2, . . . , Tm}, where each element
Ti with i ∈ {1, 2, . . . ,m} is a set that contains exactly 3 distinct elements of S.
Goal. Find a maximum 3-matching, that is a maximum size subset of T that contains each
element of S at most once.
Example. Let S = {1, 2, 3, 4, 5, 6}, and let T1 = {2, 3, 4}, T2 = {1, 2, 3}, and T3 = {4, 5, 6}.
Then a maximum 3-matching for this example is {T2, T3}. There also exists a maximal 3-
matching of size one for the example because {T1} is a matching and neither T2 nor T3 can
be added to it.
i. Give an instance of 3-MATCHING with |S| = 9 and a set T = {T1, T2, . . . , Tm} such
that the instance has a maximum matching of size 3 and a maximal matching of size 1.
You are free to choose m.
(2 marks)
ii. Describe a 13 -approximation algorithm for finding a maximum 3-matching and explain
why your algorithm has approximation ratio 13 .
(4 marks)
5 - Algorithms for Problems in Computational Biology.
(a) Give two rooted binary phylogenetic X-trees T and T ′ with |X| = 8 such that h(T , T ′) >
drSPR(T , T ′). Explicitly say what h(T , T ′) and drSPR(T , T ′) are for the two trees that you
have chosen.
(2 marks)
(b) Are there two rooted binary phylogeneticX-trees T and T ′ such that h(T , T ′) < drSPR(T , T ′).
If yes, give an example for two such trees. If no, explain why.
(2 marks)
(c) Describe three differences between the two kernelization algorithms to compute h(T , T ′) and
drSPR(T , T ′) for two rooted binary phylogenetic X-trees T and T ′.
(3 marks)
(d) Let T and T ′ be two rooted binary phylogenetic X-trees, and let F be a maximum acyclic
agreement forest for T and T ′. Let Tρ be the element in F that contains the root ρ, and let
L(Tρ) be the leaf set of Tρ. Explain why L(Tρ) ∩X 6= ?.
(3 marks)