COMPSCI 720代写、代写Python/C++编程

日期：2022-06-03 04:10

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

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

0 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:

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

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

2 ( 10 20 0 10 21 1 21 10 )

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

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

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

6. 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)