首页 >
> 详细

CSC2047/Assignment 2 (v1)

1. Decide whether each of the following expressions are true or not. Answer yes or no.

Hint: Remember that e.g. 4n = O(n2) is true, even though 4n = O(n) is also the case.

In any case where it is not true, perform an asymptotic analysis using the informal method

discussed in the lecture so as to provide a correct O-complexity (that is, do not provide an Ocomplexity

which is unnecessarily high; e.g. for 4n, O(n) would be fine, however O(n

2) would not).

2. Consider the language

L = {hG, ni | G is an undirected graph with n connected components}.

Consider the following undirected graphs:

(a) For each of the following statements, decide whether it holds.

(i) hG1, 1i ∈ L [1 mark]

(ii) hG2, 2i ∈ L [1 mark]

(iii) hG3, 1i ∈ L [1 mark]

(iv) hG3, 4i ∈ L [1 mark]

(v) hG4, 3i ∈ L [1 mark]

(vi) hG4, 4i ∈ L [1 mark]

(b) Prove that L is decidable by providing a high-level decider. (That is, an algorithm-like

description in English, cf. the according lecture slides) Your implementation should require

no more than polynomial time. [2 marks]

(c) Argue that your decider runs in polynomial time. Do so by reasoning about the runtime of

its individual steps, the number of steps required, etc. as in the lecture. [2 marks]

Page 3 of 9

CSC2047/Assignment 2 (v1)

3. Consider the following Turing machine M with input alphabet Σ = {0, 1, #}:

(a) Let C1 be the initial configuration for the input word #101 and let C2 be the configuration

yielded by C2. That is, C2 is the configuration obtained from the Turing machine after one

step when it is started on the word #101.

(i) Provide C1 in terms of a string [1 mark]

(ii) Provide C2 in terms of a string [1 mark]

(b) Decide whether each of the following strings would be accepted by the Turing machine.

Write down the computation the Turing machine performs for each of them in terms of a

sequence of configurations. For the accepted ones, answer yes; otherwise, no.

(i) # [1 mark]

(ii) ## [1 mark]

(iii) 0 [1 mark]

(iv) #0 [1 mark]

(v) #1 [1 mark]

(vi) #00 [1 mark]

(vii) #01 [1 mark]

(viii) #10 [1 mark]

(ix) #11 [1 mark]

(x) #101 [1 mark]

(c) What is the language of accepted (input) words of this Turing machine? Describe the

language using a regular expression. [1 mark]

(d) What is the language of (output) words which may be on the tape at the moment the

Turing machine has moved to the accepting state? Describe the language using a regular

expression. [1 mark]

(e) What is the worst-case runtime f(n) of this Turing machine for a word of length n? [2 marks]

(f) What is the best-case runtime g(n) of this Turing machine for a word of length n? [2 marks]

(g) Formalise the graphical representation of the Turing machine above as a 7-tuple. [2 marks]

Page 4 of 9

CSC2047/Assignment 2 (v1)

4. Consider the following three-tape Turing machine with input alphabet Σ = {a, b, c}:

a, ␣, ␣→(a, N),(a, R),(a, R) a, ␣, ␣ → (a, N),(a, R),(a, R)

a, ␣, ␣ → (a, R),(a, R),(␣, N)

b, ␣, ␣ → (b, N),(␣, N),(␣, N)

b, a, ␣ → (b, R),(␣, N),(␣, N)

b, ␣, ␣ → (b, N),(␣, L),(␣, N)

c, ␣, ␣ → (c, N),(␣, N),(␣, N)

c, ␣, a → (c, R),(␣, N),(␣, N)

c, ␣, ␣ → (c, N),(␣, N),(␣, L)

␣, ␣, ␣

→ (␣, N),(␣, L),(␣, L) ␣, ␣, ␣

→ (␣, N),(␣, L),(␣, L)

␣, ␣, ␣

→ (␣, N),(␣, N),(␣, N)

(a) Decide whether each of the following strings would be accepted by the Turing machine.

Write down the computation the Turing machine performs for each of them in terms of a

sequence of configurations. For the accepted ones, answer yes; otherwise, no.

(i) ε [1 mark]

(ii) abc [1 mark]

(iii) abbbcc [1 mark]

(iv) abbb [1 mark]

(v) bac [1 mark]

(vi) aabbbbbbcccc [1 mark]

(b) Which language does this machine recognise? Provide the language in set notation.

[2 marks]

(c) Provide a two-tape Turing machine which recognises the same language and still runs in

the same runtime order O(n). [2 marks]

Page 5 of 9

CSC2047/Assignment 2 (v1)

5. Consider the following nondeterministic Turing machine with input alphabet Σ = {0, 1}:

(a) Decide whether each of the following strings would be accepted by the Turing machine.

Write down a computation the Turing machine performs for each of them in terms of a

sequence of configurations. For the accepted ones, the computation you write down should

be an accepting computation. For the accepted ones, answer yes; otherwise, no.

(i) ε [1 mark]

(ii) 0 [1 mark]

(iii) 1 [1 mark]

(iv) 01 [1 mark]

(v) 10 [1 mark]

(vi) 101 [1 mark]

(vii) 11100 [1 mark]

(viii) 10100 [1 mark]

(b) What is the language of accepted words of this Turing machine? Describe the language

using a regular expression. [2 marks]

(c) What is the worst-case runtime f(n) of this Turing machine for a word of length n? Remember

that you have to consider the maximum over all possible runs for the word. [2 marks]

(d) What is the best-case runtime g(n) of this Turing machine for a word of length n? Remember

that you have to consider the maximum (not the minimum) over all possible runs

for the word. [2 marks]

(e) What is the maximum number of different runs for a given word of length n? [1 mark]

(f) What is the minimum number of different runs for a given word of length n > 0? [1 mark]

(g) Provide a (deterministic) Turing machine which always halts which recognises the same

language as this nondeterministic Turing machine. [2 marks]

(h) Formalise the graphical representation of the nondeterministic Turing machine above as a

7-tuple. [2 marks]

Page 6 of 9

CSC2047/Assignment 2 (v1)

6. Consider the language

HAMPATH = {hG, s, ti | G is a directed graph with a Hamiltonian path from s to t}

HAMPATH can be reduced to SAT as follows: Consider an arbitrary directed graph G = (V, E)

with n vertices and m edges. We assume V = {v1, . . . , vn}. We consider the set of variables

C = {ci,j | 1 ≤ i ≤ n and 1 ≤ j ≤ n}.

Consider formula φ consisting of the conjunction (∧) of the following set S of clauses:

S = Satleastonce ∪ Smaxoneperstage ∪ Snottwice ∪ Sfirst ∪ Slast ∪ Spath

where

• Satleastonce = {(ci,1 ∨ . . . ∨ ci,n) | 1 ≤ i ≤ n},

• Smaxoneperstage = {ci,k ∨ cj,k | 1 ≤ i ≤ n and 1 ≤ j ≤ n and i < j and 1 ≤ k ≤ n}

• Snottwice = {(ck,i ∨ ck,j ) | 1 ≤ k ≤ n and 1 ≤ i ≤ n and 1 ≤ j ≤ n and i < j},

• Sfirst = {ci,1} where vi = s,

• Slast = {ci,n} where vi = t,

• Spath = {ci,k ∨ cj,k+1 | (vi

, vj ) ∈/ E and 1 ≤ i ≤ n and 1 ≤ j ≤ n and 1 ≤ k ≤

n − 1 and i 6= j}.

For instance, if we consider the set A = {a ∨ b, c, c ∨ a}, then the conjunction of the clauses of

A would be φ = (a ∨ b) ∧ c ∧ (c ∨ a), where the order of clauses in φ is arbitrary. The way the

encoding works is similar to how the nondeterministic decider N1 from “Time Complexity - Part

3” recognises HAMPATH . A variable ci,k encodes the fact that that node vi

is chosen as the

k-th number (pk in the algorithm). Satleastonce ensures that each node is chosen at least once.

Accordingly, Snottwice ensures that each node is chosen no more than once: if vk it is chosen as

the i-th number, then it cannot be chosen again as later number j. Sfirst and Slast ensure that

s and t are the first and last nodes of the path to be obtained. Spath encodes step 4. of the

algorithm seen in the lecture: it disallows that a node vi

is followed by node vj

if there is no edge

from the first to the second node.

(a) Consider the following directed graphs:

Encode the following problems into Boolean formulas as described above.

(i) hG1, v1, v2i ∈ HAMPATH [1 mark]

(ii) hG2, v1, v3i ∈ HAMPATH [1 mark]

(iii) hG3, v1, v4i ∈ HAMPATH [1 mark]

(iv) hG4, v1, v4i ∈ HAMPATH [1 mark]

wwwwwwwwwwwww(continued at next page)

Page 7 of 9

CSC2047/Assignment 2 (v1)

wwwwwwwwwwwww(continued from previous page)

(b) DIMACS is a text-based format for Boolean formulas in CNF. Read the description at

http://people.sc.fsu.edu/~jburkardt/data/cnf/cnf.html. Encode the following

problems in DIMACS. Also state which ci,j is assigned which variable number. Afterwards,

use the webpage https://jgalenson.github.io/research.js/demos/minisat.html

to solve these SAT problems automatically. For each problem, provide the resulting output.

If the problem is satisfiable, provide the Hamilton path which corresponds to the solution.

(i) hG1, v1, v2i ∈ HAMPATH [1 mark]

(ii) hG2, v1, v3i ∈ HAMPATH [1 mark]

(iii) hG3, v1, v4i ∈ HAMPATH [1 mark]

(iv) hG4, v1, v4i ∈ HAMPATH [1 mark]

(c) SAT problems can be solved in O(2q

· p) where q is the number of variables and p the

length of the formula (total number of literals). Let EXPTIME =

S

k TIME(2nk) be

the set of languages which are decidable in exponential time.

(i) Provide the complexity of deciding HAMPATH via SAT using the O-notation depending

on the number of vertices n. [2 marks]

(ii) Is HAMPATH in EXPTIME? Justify your answer. [2 marks]

(iii) Is this method to solve HAMPATH faster than the one from the lecture? Justify your

answer. [2 marks]

(d) Describe an encoding of the following language to SAT:

ANYHAM = {hGi | G is a directed graph with a Hamiltonian path}

[2 marks]

(e) Describe an encoding of the following language to SAT:

HCIRC = {hGi | G = (V, E) is a directed graph and it has a Hamiltonian path

from some s ∈ V to some t ∈ V with (t, s) ∈ E} [2 marks]

(f) Describe how you could exclude a particular Hamiltonian path when constructing the SAT

problem (e.g. because you have already found it and you want to find another one).

[2 marks]

Page 8 of 9

CSC2047/Assignment 2 (v1)

7. Consider the recurrences below defined for n ≥ 0.

Note: The lecture discussing the methods necessary for solving this exercise is scheduled for

Thursday, February 27th, 2020.

f(n) = (1 if n = 0

f(n − 1) + 2n else

g(n) = (1 if n = 02g(n − 1) + 2n else

(a) Give the values for the following items.

(i) f(0) [1 mark]

(ii) g(1) [1 mark]

(iii) g(2) [1 mark]

(iv) f(10) [1 mark]

(b) Give a closed-form solution to the recurrence for f(n) and show your process for arriving

at this solution. [2 marks]

(c) Prove the correctness of your solution in (b) by induction. [2 marks]

(d) Prove that g(n) = 5 · 2

n − 2n − 4 by induction. [2 marks]

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp2

- Csci 3120作业代做、C++程序语言作业调试、代做c/C++课程作业、 2020-05-26
- 代写algorithms作业、Data留学生作业代做、代写java、Pyth 2020-05-26
- Data Science作业代写、C++程序设计作业代写、Programmi 2020-05-26
- Data课程作业代写、C++编程设计作业调试、C/C++语言作业代做、Alg 2020-05-26
- 代写r留学生作业、代做data课程作业、代写r编程语言作业代做r语言编程|调 2020-05-25
- Cosc473作业代做、Systems作业代写、Python编程设计作业调试 2020-05-25
- Data留学生作业代做、R编程设计作业调试、R语言作业代写、Program课 2020-05-25
- Comp 250 Assignment 3 2020-05-24
- Macm 316 – Computing Assignment 7 2020-05-24
- Sta457 Assignment 2020-05-24
- Homework 10 2020-05-24
- Lab 2 Msc: Time Series Prediction With... 2020-05-24
- Comp2011作业代做、Data Analysis作业代写、C++编程语言 2020-05-24
- 代做compsys201作业、Python，Java，C/C++编程语言作业 2020-05-24
- Program留学生作业代做、Python编程设计作业调试、Data作业代写 2020-05-24
- 代写 Practical 3 Covid-19程序作业，代写... 2020-05-23
- 代写comp3059作业、代做programming作业、Java语言作业代 2020-05-23
- Coit12206作业代写、Program课程作业代做、Java、Pytho 2020-05-23
- Data2001作业代做、Data Science作业代做、Sql语言作业代 2020-05-23
- 代写comp2017作业、代写c/C++语言作业、代写data作业、C/C+ 2020-05-23