xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

Python代写-S1-Assignment 2

时间：2021-04-22

Computer Science 720 S1 – (2021)

Assignment 2 (Bounded Treewidth Algorithms)

Due: Friday, April 23, 11:59pm

Requirements

In this assignment you will learn how to use and understand the t-parse data structure for graphs

of bounded pathwidth/treewidth. We will do some basic programming regarding the t-parse repre-

sentation of graphs.

We use the following t-parse input format for graphs of bounded treewidth. The first token will be

a positive integer t ≤ 9 denoting the pathwidth/treewidth of the graph (i.e., it indicates a t-parse

will follow). The interpretation for the remaining tokens are given in the next table.

token semantic meaning

i a vertex operator i, represented as an integer, where 0 ≤ i ≤ t ≤ 9

ij an edge operator (i, j) where t ≥ i > j ≥ 0 (note: no space between i and j)

( a begin marker for a pathwidth t-parse (can be nested for treewidth t-parses)

) an end marker for a pathwidth/treewidth t-parse

Thus, if you read/encounter the two tokens ‘)’ and ‘(’ in sequence then this denotes a circle plus

⊕ operator. Note that it is guaranteed that each right token ‘(’ will have a matched left token ‘)’.

Each ’(’ except first token must be preceded by a parenthesis and ’)’ may be succeeded “up the parse

tree” by pathwidth operators. We assume boundary vertices 0, 1, . . . , t precede the first token of a

pathwidth t-parse (and these empty boundaried graph axioms are not given in the input format).

Assume left-associativity for all operators and at least one space between each of them, including

the parentheses.

For each part of the assignment the input will consist of several test cases, each on its own line. The

input is terminated by a t = 0 case, which is also processed.

1

Problem 1: Parse and Extract Graph

You need to output an adjacency list representation using a sorted ‘CompSci 220 graph format’.

Here the first line is an integer n representing the order of the graph. The next n lines consist of a

(sorted integer) adjacency lists, for vertices indexed 0 to n− 1, of neighbor indices. To have unique

graph, the vertex indices are assigned labels to vertices in the same order as the new vertex operators

appear in the t-parse from left-to-right.

The following show typical input instances and expected output. Note that you can assume that

each input graph fits on one line.

Sample input

2 ( 10 21 1 10 21 0 10 20 2 20 21 )

2 ( ( 10 21 1 10 21 1 21 10 ) ( 21 2 21 20 ) ( 10 ) )

4 ( ( 10 20 30 41 4 41 31 ) ( ( 40 21 32 42 ) ( 10 0 43 10 20 ) ) )

0 ( ( 0 ) ( 0 0 ) )

Sample output

6

1 3

0 2

1 3 4

0 2 4 5

2 3 5

3 4

6

1 2 3 4

0 2

0 1 3 4

0 2

0 2 5

4

7

1 2 3 5

0 2 3 4 5 6

0 1 3 5

0 1 2 5

1

0 1 2 3

1

4

2

Problem 2: Weighted Independent Sets

In this part of the assignment you will learn how to exploit the structure of bounded pathwidth/treewidth

for a known hard graph problem:

Problem: Degree-Weighted Independent Set (DWIS)

Input: (undirected) Graph G = (V,E)

Question: Let the weight of each vertex be its degree (number of vertex neighbors).

What is the largest sum of vertex weights over all independent sets of vertices?

That is, maxV ′⊆V

∑

v∈V ′ deg(v) where for all {v1, v2} ⊆ V ′ we have (v1, v2) 6∈ E.

Your main requirements are to do the following.

1. For input graph of bounded pathwidth (in t-parse representation described above), determine

the DWIS.

2. Extend your linear-time program for item 1 for input of bounded treewidth.

The following show typical input instances. Again you can assume each input t-parse graph fits on

one line.

Sample input output

2 ( 10 21 1 10 21 0 10 20 2 20 21 ) 7

2 ( ( 10 21 1 10 21 1 21 10 ) ( 21 2 21 20 ) ) 7

4 ( ( 10 20 30 41 4 41 31 ) ( ( 40 21 32 42 ) ( 10 0 43 10 20 ) ) ) 6

3 ( 32 31 30 20 21 10 0 10 20 21 1 10 21 1 10 21 1 10 0 10 30 20 ) 11

2 ( 21 2 21 2 21 20 1 10 1 10 1 21 1 10 2 21 1 10 21 2 21 1 10 2 20 0 20 10 ) 16

3 ( ( 30 32 21 10 1 10 21 2 21 32 1 21 10 31 1 21 10 31 ) ( 20 21 32 2 21 32 ) 0 21 10 30 20 ) 14

4 ( 10 20 30 40 43 21 32 2 20 21 42 0 30 40 10 2 21 3 30 31 4 41 43 42 40 ) 13

0 ( 0 0 ) 0

Submission and Marks

All solutions should be submitted to the automarker http://automarker.cs.auckland.ac.nz/.

All input should be taken from the keyboard (stdin) and output to the console (stdout). There will

be two test cases for each of our problems.

The first data set will only contain pathwidth t-parses and are worth 3 marks. The slightly harder

treewidth t-parse input cases will be worth 2 marks each. This assignment is worth 10% of your

final grade, where both Problems 1 and 2 are worth 5 marks each. Partial marks may be awarded

later (after due date) if determined to be close to correct.

3

学霸联盟

Assignment 2 (Bounded Treewidth Algorithms)

Due: Friday, April 23, 11:59pm

Requirements

In this assignment you will learn how to use and understand the t-parse data structure for graphs

of bounded pathwidth/treewidth. We will do some basic programming regarding the t-parse repre-

sentation of graphs.

We use the following t-parse input format for graphs of bounded treewidth. The first token will be

a positive integer t ≤ 9 denoting the pathwidth/treewidth of the graph (i.e., it indicates a t-parse

will follow). The interpretation for the remaining tokens are given in the next table.

token semantic meaning

i a vertex operator i, represented as an integer, where 0 ≤ i ≤ t ≤ 9

ij an edge operator (i, j) where t ≥ i > j ≥ 0 (note: no space between i and j)

( a begin marker for a pathwidth t-parse (can be nested for treewidth t-parses)

) an end marker for a pathwidth/treewidth t-parse

Thus, if you read/encounter the two tokens ‘)’ and ‘(’ in sequence then this denotes a circle plus

⊕ operator. Note that it is guaranteed that each right token ‘(’ will have a matched left token ‘)’.

Each ’(’ except first token must be preceded by a parenthesis and ’)’ may be succeeded “up the parse

tree” by pathwidth operators. We assume boundary vertices 0, 1, . . . , t precede the first token of a

pathwidth t-parse (and these empty boundaried graph axioms are not given in the input format).

Assume left-associativity for all operators and at least one space between each of them, including

the parentheses.

For each part of the assignment the input will consist of several test cases, each on its own line. The

input is terminated by a t = 0 case, which is also processed.

1

Problem 1: Parse and Extract Graph

You need to output an adjacency list representation using a sorted ‘CompSci 220 graph format’.

Here the first line is an integer n representing the order of the graph. The next n lines consist of a

(sorted integer) adjacency lists, for vertices indexed 0 to n− 1, of neighbor indices. To have unique

graph, the vertex indices are assigned labels to vertices in the same order as the new vertex operators

appear in the t-parse from left-to-right.

The following show typical input instances and expected output. Note that you can assume that

each input graph fits on one line.

Sample input

2 ( 10 21 1 10 21 0 10 20 2 20 21 )

2 ( ( 10 21 1 10 21 1 21 10 ) ( 21 2 21 20 ) ( 10 ) )

4 ( ( 10 20 30 41 4 41 31 ) ( ( 40 21 32 42 ) ( 10 0 43 10 20 ) ) )

0 ( ( 0 ) ( 0 0 ) )

Sample output

6

1 3

0 2

1 3 4

0 2 4 5

2 3 5

3 4

6

1 2 3 4

0 2

0 1 3 4

0 2

0 2 5

4

7

1 2 3 5

0 2 3 4 5 6

0 1 3 5

0 1 2 5

1

0 1 2 3

1

4

2

Problem 2: Weighted Independent Sets

In this part of the assignment you will learn how to exploit the structure of bounded pathwidth/treewidth

for a known hard graph problem:

Problem: Degree-Weighted Independent Set (DWIS)

Input: (undirected) Graph G = (V,E)

Question: Let the weight of each vertex be its degree (number of vertex neighbors).

What is the largest sum of vertex weights over all independent sets of vertices?

That is, maxV ′⊆V

∑

v∈V ′ deg(v) where for all {v1, v2} ⊆ V ′ we have (v1, v2) 6∈ E.

Your main requirements are to do the following.

1. For input graph of bounded pathwidth (in t-parse representation described above), determine

the DWIS.

2. Extend your linear-time program for item 1 for input of bounded treewidth.

The following show typical input instances. Again you can assume each input t-parse graph fits on

one line.

Sample input output

2 ( 10 21 1 10 21 0 10 20 2 20 21 ) 7

2 ( ( 10 21 1 10 21 1 21 10 ) ( 21 2 21 20 ) ) 7

4 ( ( 10 20 30 41 4 41 31 ) ( ( 40 21 32 42 ) ( 10 0 43 10 20 ) ) ) 6

3 ( 32 31 30 20 21 10 0 10 20 21 1 10 21 1 10 21 1 10 0 10 30 20 ) 11

2 ( 21 2 21 2 21 20 1 10 1 10 1 21 1 10 2 21 1 10 21 2 21 1 10 2 20 0 20 10 ) 16

3 ( ( 30 32 21 10 1 10 21 2 21 32 1 21 10 31 1 21 10 31 ) ( 20 21 32 2 21 32 ) 0 21 10 30 20 ) 14

4 ( 10 20 30 40 43 21 32 2 20 21 42 0 30 40 10 2 21 3 30 31 4 41 43 42 40 ) 13

0 ( 0 0 ) 0

Submission and Marks

All solutions should be submitted to the automarker http://automarker.cs.auckland.ac.nz/.

All input should be taken from the keyboard (stdin) and output to the console (stdout). There will

be two test cases for each of our problems.

The first data set will only contain pathwidth t-parses and are worth 3 marks. The slightly harder

treewidth t-parse input cases will be worth 2 marks each. This assignment is worth 10% of your

final grade, where both Problems 1 and 2 are worth 5 marks each. Partial marks may be awarded

later (after due date) if determined to be close to correct.

3

学霸联盟