xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

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

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

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

微信客服：xiaoxionga100

微信客服：ITCS521

理论题代写-COMP4141-Assignment 4

时间：2021-04-15

COMP4141 Assignment 4 2021 Term 1

Due: Monday, 26th April, 12:00 (AEST)

Submission is through WebCMS/give and should be a single pdf file, maximum size 2Mb. Prose should

be typed, not handwritten. Use of LATEX is encouraged, but not required.

Discussion of assignment material with others is permitted at a high level, but the work submitted must

be your own in line with the University’s plagiarism policy.

Problem 1 (10 marks)

Consider the following decision problem:

4-Col

Input: A graph G

Question: Does G have a valid 4-colouring? That is, an assignment of one of four colours to each

vertex such that no edge has two endpoints the same colour.

Show that 4-Col is NP-complete.

Problem 2 (14 marks)

The Job scheduling problem is defined as follows: we have two processors and a set of n jobs, j1, j2, . . . , jn

each of which takes time t1, t2, . . . tn (respectively) to complete on either processor. Each job can only be

run on one processor and each processor can only process one job at a time (the order does not matter).

The Job scheduling problem is to allocate the jobs to the processors so as to minimize the processing

time: that is minimize the maximum time taken by either processor. For example, if we had four jobs

j1, j2, j3, j4 with completion times of t1 = 1, t2 = 2, t3 = 3, and t4 = 7, then the allocation of j1, j2, j3 to one

processor and j4 to the other processor would have the minimum processing time of max{1+ 2+ 3, 7} = 7.

(a) State the Job scheduling problem as a decision problem. (4 marks)

(b) Show that the decision version of the Job scheduling problem is NP-complete. (10 marks)

Problem 3 (16 marks)

The Knapsack problem is the problem of maximizing the value of contents of a knapsack, without ex-

ceeding a specified weight limit. More precisely, the decision problem is:

1

Knapsack

Input: A set of n pairs of positive integers: {(w1, v1), (w2, v2), . . . (wn, vn)}; and two positive integers

W and V.

Question: Is there a subset K ⊆ {1, 2, . . . n} such that

∑

i∈K

wi ≤W and ∑

i∈K

vi ≥ V?

Show that Knapsack is NP-complete.

Problem 4 (30 marks)

Consider the following graph:

x

y y′

x

(a) Give a valid 3-colouring of this graph where x and y have different colour. (2 marks)

(b) Give a valid 3-colouring of this graph where x and y have the same colour. (2 marks)

(c) What can be said about any valid 3-colouring of this graph? Justify your answer. (4 marks)

A graph is planar if it can be drawn on the plane with no crossing edges. The graph above is an example

of a planar graph.

(d) Consider the following decision problem:

Planar 3-Col

Input: A planar graph G

Question: Does G have a valid 3-colouring?

Show that Planar 3-Col is NP-complete. Hint: Use the above graph to “uncross” edges (16 marks)

(e)∗ Prove that there is no planar graph G, with x, y, x′, y′ on an outer face (in that order), that satisfies

the conditions indicated in (a), (b) and (c), but with a 4-colouring rather than a 3-colouring. (6 marks)

2

Problem 5 (20 marks)

A boolean program is a program in which all variables have type Boolean, and which may use the following

constructions:

• Boolean expressions e may be formed from boolean variables using the operators ∧,∨,¬ and con-

stants true, false

• if x is a variable and e is a Boolean expression, then the statement x := e is a program. It runs by

calculating the value of e and updating x to have this value.

• If P and Q are programs, then P; Q is a program that runs by first executing P and then executing

Q.

• If P and Q are programs and e is a boolean expression, then

if e then {P} else {Q}

is a program that runs by first calculating the value of e and executing P if e is true and executing Q

otherwise.

• If P is a program and e is a boolean expression, then

while e do {P}

is a program that runs by repeatedly testing if e is true and executing P if so. The loop exits as soon

as e evaluates to false.

Boolean programs run starting from some given initial assignment pi to their boolean variables, and

update this assignment during their execution. They may terminate or not, possibly depending on the

initial assignment. For example

while x do {if y then {y := false} else {y := true}}

when run from initial assignment pi, halts immediately if pi(x) = false and is non-terminating if pi(x) =

true.

Consider the following decision problem

BP-Halt

Input: A boolean program P

Question: Does there exist an assignment pi such that P terminates when run from initial assign-

ment pi?

Show that BP-Halt is PSPACE-complete.

Problem 6 (10 marks)

Consider the following decision problem:

3

2-SAT

Input: A boolean formula ϕ in CNF with at most 2 literals per clause

Question: Is ϕ satisfiable?

Show that

PATH ≤L 2-SAT.

Hint 1: Find a reduction first then check if it is log-space.

Hint 2: The 2-CNF clause (¬x ∨ y) is logically equivalent to the expression (x → y).

4

学霸联盟

Due: Monday, 26th April, 12:00 (AEST)

Submission is through WebCMS/give and should be a single pdf file, maximum size 2Mb. Prose should

be typed, not handwritten. Use of LATEX is encouraged, but not required.

Discussion of assignment material with others is permitted at a high level, but the work submitted must

be your own in line with the University’s plagiarism policy.

Problem 1 (10 marks)

Consider the following decision problem:

4-Col

Input: A graph G

Question: Does G have a valid 4-colouring? That is, an assignment of one of four colours to each

vertex such that no edge has two endpoints the same colour.

Show that 4-Col is NP-complete.

Problem 2 (14 marks)

The Job scheduling problem is defined as follows: we have two processors and a set of n jobs, j1, j2, . . . , jn

each of which takes time t1, t2, . . . tn (respectively) to complete on either processor. Each job can only be

run on one processor and each processor can only process one job at a time (the order does not matter).

The Job scheduling problem is to allocate the jobs to the processors so as to minimize the processing

time: that is minimize the maximum time taken by either processor. For example, if we had four jobs

j1, j2, j3, j4 with completion times of t1 = 1, t2 = 2, t3 = 3, and t4 = 7, then the allocation of j1, j2, j3 to one

processor and j4 to the other processor would have the minimum processing time of max{1+ 2+ 3, 7} = 7.

(a) State the Job scheduling problem as a decision problem. (4 marks)

(b) Show that the decision version of the Job scheduling problem is NP-complete. (10 marks)

Problem 3 (16 marks)

The Knapsack problem is the problem of maximizing the value of contents of a knapsack, without ex-

ceeding a specified weight limit. More precisely, the decision problem is:

1

Knapsack

Input: A set of n pairs of positive integers: {(w1, v1), (w2, v2), . . . (wn, vn)}; and two positive integers

W and V.

Question: Is there a subset K ⊆ {1, 2, . . . n} such that

∑

i∈K

wi ≤W and ∑

i∈K

vi ≥ V?

Show that Knapsack is NP-complete.

Problem 4 (30 marks)

Consider the following graph:

x

y y′

x

(a) Give a valid 3-colouring of this graph where x and y have different colour. (2 marks)

(b) Give a valid 3-colouring of this graph where x and y have the same colour. (2 marks)

(c) What can be said about any valid 3-colouring of this graph? Justify your answer. (4 marks)

A graph is planar if it can be drawn on the plane with no crossing edges. The graph above is an example

of a planar graph.

(d) Consider the following decision problem:

Planar 3-Col

Input: A planar graph G

Question: Does G have a valid 3-colouring?

Show that Planar 3-Col is NP-complete. Hint: Use the above graph to “uncross” edges (16 marks)

(e)∗ Prove that there is no planar graph G, with x, y, x′, y′ on an outer face (in that order), that satisfies

the conditions indicated in (a), (b) and (c), but with a 4-colouring rather than a 3-colouring. (6 marks)

2

Problem 5 (20 marks)

A boolean program is a program in which all variables have type Boolean, and which may use the following

constructions:

• Boolean expressions e may be formed from boolean variables using the operators ∧,∨,¬ and con-

stants true, false

• if x is a variable and e is a Boolean expression, then the statement x := e is a program. It runs by

calculating the value of e and updating x to have this value.

• If P and Q are programs, then P; Q is a program that runs by first executing P and then executing

Q.

• If P and Q are programs and e is a boolean expression, then

if e then {P} else {Q}

is a program that runs by first calculating the value of e and executing P if e is true and executing Q

otherwise.

• If P is a program and e is a boolean expression, then

while e do {P}

is a program that runs by repeatedly testing if e is true and executing P if so. The loop exits as soon

as e evaluates to false.

Boolean programs run starting from some given initial assignment pi to their boolean variables, and

update this assignment during their execution. They may terminate or not, possibly depending on the

initial assignment. For example

while x do {if y then {y := false} else {y := true}}

when run from initial assignment pi, halts immediately if pi(x) = false and is non-terminating if pi(x) =

true.

Consider the following decision problem

BP-Halt

Input: A boolean program P

Question: Does there exist an assignment pi such that P terminates when run from initial assign-

ment pi?

Show that BP-Halt is PSPACE-complete.

Problem 6 (10 marks)

Consider the following decision problem:

3

2-SAT

Input: A boolean formula ϕ in CNF with at most 2 literals per clause

Question: Is ϕ satisfiable?

Show that

PATH ≤L 2-SAT.

Hint 1: Find a reduction first then check if it is log-space.

Hint 2: The 2-CNF clause (¬x ∨ y) is logically equivalent to the expression (x → y).

4

学霸联盟