UNIVERSITY OF PORTSMOUTH
SCHOOL OF COMPUTING
FIRST ATTEMPT EXAMINATIONS 2017/2018
U21276 – THEOCS – THEORETICAL COMPUTER SCIENCE
Copyright By PowCoder代写 加微信 powcoder
Duration: Instructions:
Additional Information: Permitted:
Calculator:
1 Hour 30 Minutes Answer all four questions
This is a CLOSED book examination No materials permitted
Calculators ARE permitted (calculators must not have long-term data storage)
Question 1: Computability and equivalent models
Using the “simple programming language” write a program to perform the following tasks:
X, Y are variables with given values (natural numbers) (i) X:=X+Y
(ii) Z:=X∗Y
Except for the standard assignments which are allowed by the rules of the “simple programming language”, you are allowed to use the following assignments: X := Y, X := any constant, and in (ii) also X := X + Y.
For the following Markov algorithm over the alphabet {, b}
(1) b → b (2) b → Λ (3) b → b
describe what the algorithm returns for the input string bjbk, where ≥ j ≥ k ≥ 0.
(ii) Will the output be the same when you swap rules (2) and (3)? If not what is the output in that case?
In computability theory, recursive functions play an important role.
(i) Define three initial functions used as building blocks in the definition of primitive recursive functions.
(ii) Give an example of a primitive recursive function which cannot be computed by a Turing machine. Give a reason if such a function does not exist.
[Question 1 continued over the page]
U21276/THEOCS, Page 3 of 9
(d) Suppose you are given the non-deterministic Post algorithm over the alphabet {, b, c}:
XY → XccY
(i) What the algorithm returns for the input string bccb? Can you
describe how the algorithm modifies the output?
(ii) Will the output be the same when you add ‘halt’ at the end of the instruction above? The only instruction is
XY → XccY (halt)
If not what is the output in this case?
[Total Marks for Question: 25 Marks]
U21276/THEOCS, Page 4 of 9
Question 2: Decidable and undecidable problems
Suppose a list D contains k, finite strings of various lengths over the alphabet {, b, c}, the length of each string is at most k, k ≥ 1. Describe a method of how to construct a string of length k over the alphabet {, b, c} which is not in the list D. Explain clearly why such a string is not in D.
Suppose you are given a language L over the finite alphabet {}. Can you always find a Turing machine that recognises L? Justify your answer.
Explain clearly the Post Correspondence Problem (PCP). Is it possible to design an algorithm which returns the correct answer ‘YES’ for all instances for which a solution exists? Is it possible to design an algorithm which returns the correct ‘YES/NO’ answer for all instances? Give a reason.
(ii) Find a solution (or state that no solution exists) for the following instance of PCP over the alphabet {, b, c, d}:
{(bb, bc), (bbbb, b), (cb, bb), (db, b), (bb, b)} Justify your answer.
[Total Marks for Question: 25 Marks]
(ii) Give an example of three disjoint uncountable sets.
Explain when a set is countable. Give an example of two disjoint countable sets (no element in common) and present reasons why they are countable.
U21276/THEOCS, Page 5 of 9
Question 3: Time-complexity
(a) Assume you have a program with time complexity T(n) given by T(n) = An4 + Bn2 log2 n,
where A, B are constants and n is the size of the input. Which of the following statements are true? Justify your decision.
(i) T(n) = Θ(n4) (ii) T(n) = Ω(2n) (iii) T(n) = O(n4)
(iv) T(n) = Θ(n2 log2 n) (v) T(n) = O(n3)
(b) For a problem P you have an algorithm A which has a time complexity function T(n) = A × 2n where n is the size of the input. You are told that for n = 10, the algorithm takes 10−2 seconds. (Below you may use the approximation 210 ≈ 103.)
(i) How long does it take (approximately) for n = 20 ?
(ii) What is the maximum value of n which the algorithm A can solve in ten
days (you can approximate 10 days by ≈ 107 seconds).
(iii) Which statement about the problem P may be correct: tractable, intractable
or undecidable? Choose all possible answers and justify your choice.
[Question 3 continued over the page]
U21276/THEOCS, Page 6 of 9
(c) Given the following algorithm for an input n ∈ N:
while < (3 ∗ n + 1)
:= + 3;
for j := 1 to n do S od od
Find the number of times that the statement S is executed during the running of the algorithm
(i) first for n = 3; then as a function T(n) of n.
(ii) Is Θ(n) the asymptotically tight bound of T(n)? Justify your answer.
(iii) Is the asymptotically tight bound Θ for the algorithm the same if the line
for j := 1 to n do S
is replaced by the line for j := 1 to do S ?
(d) Consider the following functions from N → R:
n20 n! 2n 32003n, 2018, 2018, n8 log2 n, 2010 , 2007n2 log2 n, n, (log2 n)210, 200
(i) List all of the functions that are between Ω(n3) and O(n8). If there is no function with such a property give an example of your own function.
(ii) Choose the function with the fastest growth rate.
[Total Marks for Question: 25 Marks]
U21276/THEOCS, Page 7 of 9
Question 4: Computational complexity
(a) For each of the following problems:
(i) searching for a minimum in an unordered array of integers, (ii) the Halting problem,
(iii) the decision version of the Travelling Salesman Problem,
choose one of the following four options which best characterises the complexity
of the given problem (assume that P ̸= NP):
the problem is tractable,
the problem is NP-complete, the problem is undecidable, none of the above.
Give a brief reason in each case.
(b) Explain the main differences between P and NP-complete problems. Are
there any undecidable NP-complete problems?
(c) Explain what is the lower and upper bound of the complexity for a combinatioral
optimisation problem Q.
(d) Suppose that somebody proves that the satisfiability problem (one of the basic NP-complete problems) can be solved in a polynomial time. Would it change the complexity of any other problems? In the scale of 1 (min) to 10 (max), how significant you would consider such result and why?
(e) Suppose you find that your problem Q is NP-hard. Explain two approaches
you might use to attack the problem Q in polynomial time.
[Question 4 continued over the page]
U21276/THEOCS, Page 8 of 9
(f) Can you sort out n natural numbers in increasing order with an algorithm which has
constant time complexity (hence independent on n)? linear time complexity O(n)?
time complexity O(n2)?
time complexity Θ(2n)?
Choose the correct answer and justify it.
[3 Marks] [Total Marks for Question: 25 Marks]
END OF EXAM
U21276/THEOCS, Page 9 of 9
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com