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 O- complexity which is unnecessarily high; e.g. for 4n, O(n) would be fine, however O(n2) would not).
(a) n!+3n6 +2n3 = O(n6) (b) 2√n = O(n!)
(c) log3 n = O(log2 n)
(d) log2 n = O(log3 n)
(e) 3·2n =O(1.5n) (f) 3·2n =2O(n)
(g) 3n = 2O(n)
(h) 3n = O((√n)2)
(i) 3!+7 = O(1)
(j) 2n+√n=O(nlogn)
[1 mark] [1 mark] [1 mark] [1 mark] [1 mark] [1 mark] [1 mark] [1 mark] [1 mark] [1 mark]
CSC2047/Assignment 2 (v1)
Page 2 of 9
2. Consider the language
L = {⟨G, n⟩ | 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)⟨G1,1⟩∈L
(ii)⟨G2,2⟩∈L (iii) ⟨G3, 1⟩ ∈ L (iv)⟨G3,4⟩∈L
(v)⟨G4,3⟩∈L (vi)⟨G4,4⟩∈L
[1 mark] [1 mark] [1 mark] [1 mark] [1 mark] [1 mark]
CSC2047/Assignment 2 (v1)
G1 v2 v0 v1
v3
v0
G2
v2
v1
v1
v4
G3
v0 v2 v3
v1 v3 v5 G4
v0 v2 v4
(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, #}:
0, 1 → R # → R 0, 1 → L
q #→R q ␣→L q 0→1,L q q
0123a
#→R
1 → 0, L
(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) # (ii) ##
(iii) 0 (iv) #0 (v) #1
[1 mark] (vi) #00 [1 mark] (vii) #01 [1 mark] (viii) #10 [1 mark] (ix) #11 [1 mark] (x) #101
[1 mark] [1 mark] [1 mark] [1 mark] [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}:
c,␣,␣ → (c,N),(␣,N),(␣,L)
q5 q6 c,␣,a → (c,R),(␣,N),(␣,N)
qa q7q3
b,␣,␣ → (b,N),(␣,L),(␣,N)
b,a,␣ → (b,R),(␣,N),(␣,N)
q4
c,␣,␣ → (c,N),(␣,N),(␣,N)
b,␣,␣ → (b,N),(␣,N),(␣,N)
a,␣,␣ → (a,R),(a,R),(␣,N)
q0 q1 q2
a,␣,␣→(a,N),(a,R),(a,R) a,␣,␣ → (a,N),(a,R),(a,R)
(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] (iii) abbbcc [1 mark] (v) bac [1 mark] (ii) abc [1 mark] (iv) abbb [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
␣,␣,␣ → (␣,N),(␣,N),(␣,N) ␣,␣,␣ → (␣,N),(␣,L),(␣,L) ␣,␣,␣ → (␣,N),(␣,L),(␣,L)
CSC2047/Assignment 2 (v1) 5. Consider the following nondeterministic Turing machine with input alphabet Σ = {0, 1}:
0, 1 → R 1 → ␣, L
q 1→␣,L q 0→R q
01a
(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] (iii) 1 [1 mark] (v) 10 [1 mark] (vii) 11100 [1 mark] (ii) 0 [1 mark] (iv) 01 [1 mark] (vi) 101 [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? Remem- ber 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? Re- member 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) HAMPATH = {⟨G, s, t⟩ | G is a directed graph with a Hamiltonian path from s to t}
6. Consider the language
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≤nand1≤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≤nand1≤i≤nand1≤j≤nandi