UNIVERSITY OF PORTSMOUTH
SCHOOL OF COMPUTING
FIRST ATTEMPT EXAMINATIONS 2018/2019
U21276 – THEOCS – THEORETICAL COMPUTER SCIENCE
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
(a) Using the “simple programming language” write a program to perform the
following macro:
• X, Y are variables with the given values which should not be modified, • return the value Z, where Z := mxY − X, 0,
hence Z:= Y−X, ƒ Y≥X,
0, otherse.
Apart for the standard assignments which are allowed by the rules of the “simple programming language”, you are also allowed to use the following assignment: X := Y.
(b) Suppose you are given the following primitive recursion function F defined
for natural numbers
F(0) = 0, F(scc(y)) = dd(2, F(y)),
dd(, 0) = ,
dd(, scc(y)) = scc(dd(, y)).
Work out the value F(2).
[4 marks] (c) You are given the following Markov algorithm over the alphabet {, b}:
1. b → Λ 2. b → Λ
(i) Describe what the algorithm returns for the input string bbjbk, where ,j,k ≥ 1.
(ii) Characterise all strings over the alphabet {,b} for which the algo- rithm returns Λ.
[Question 1 continued over the page]
U21276/THEOCS, Page 3 of 10
(d) Does there exist a function which can be computed by a Turing machine but it is not primitive recursive? Explain why or why not.
(e) Name at least three computational models which are equivalent to Turing machines in the sense that they can solve the same class of problems. Does there exist a computational model which is more powerful than Turing ma- chines? Justify your answer.
[5 marks] [Total marks for the question: 25 marks]
U21276/THEOCS, Page 4 of 10
Question 2: Decidable and undecidable problems
(a) Clearly state the Halting problem and choose the best characterization for
(b) Is it true that the problem from (a) cannot be solved on today’s computers because of their current limits of memory and speed? Is there a chance it can be solved in the future with increasing capacity of memory and speed?
(c) Decide whether the size of each set (i)–(ii) is countable or uncountable.
Justify your answer.
(i) The set of all strings over the alphabet {, b, c} of length 10.
(ii) The set S of all languages over the alphabet {, b, c} with the following property: each language from S contains only strings of length ten.
(d) Find a solution (or state that no solution exists) for the following instance of
Justify your answer.
“decidable/partially decidable/undecidable”
the Post Correspondence Problem:
{(11, 1), (0111, 10), (10, 0), (1, 111)}
Justify your answer.
[Question 2 continued over the page]
U21276/THEOCS,
Page 5 of 10
(e) Suppose a list A contains n different randomly generated strings over the alphabet {, b, c, d}, and the length of each string is n, n ≥ 5.
Describe clearly how you would construct a string of length m over the alphabet {, b, c, d} which is not in the list A:
(i) for m = 4, (ii) for m = n, (iii) for m = 2n.
In each case explain why such a string is not in A.
[Total marks for the question: 25 marks]
U21276/THEOCS, Page 6 of 10
Question 3: Time-complexity
(a) Consider the following functions from N → R:
n20 n! n4 nn
3n, log2 n20, 20 , n6 log2 n, 202 , 2007n5 log2 n, 3 , (log2 n)20, 20!, log2 n, 4200n
(i) List all of the functions that are between Ω(n4) and O(n6). If there is no function with such property give an example of your own function.
(ii) Choose the function with the slowest and with the fastest growth rate.
(iii) List all of the functions that are in Θ(n). If there is no function with such property give an example of your own function.
(iv) Which of the functions 3n and 2007n5 log2 n growths faster when n → ∞ (with increasing n)? Give a reason.
(b) Suppose we have two algorithms A and B for solving a problem P.
The algorithm A has a time complexity function TA(n) = A · n2 for some constant A and for n = 10 the algorithm takes 31 seconds on our testing computer.
The algorithm B has a time complexity function TB(n) = B · 2n, for some constant B and for n = 10 the algorithm takes 2·10−3 seconds on our testing computer. (You may use the approximation 210 ≈ 103, actually 210 > 103.)
(i) We wish to solve the problem as quickly as possible for various values of n. Which of the two algorithms is better to use for n = 5, n = 15, n=20, n=25?
(ii) Is the problem P tractable, intractable or undecidable? Give a reason
for your answer.
[Question 3 continued over the page]
U21276/THEOCS, Page 7 of 10
(c) Given the following algorithm: //, j, n are integer variables
for:=1 to2∗ndo forj:= to (+4)doS;
Let T(n) be the time complexity function, i.e. it determines how many times the statement S is executed as a function of n, when we run the program.
(i) Determine the value T(2), i.e. how many times the statement S is exe- cuted for n = 2. Show your working.
(ii) Choose the growth of the function T(n) from the given list and justify your answer:
Θ(n), Θ(n2), or Θ(2n).
(iii) Express T(n) as a function of n.
[Total marks for the question: 25 marks]
U21276/THEOCS, Page 8 of 10
Question 4: Computational complexity
(a) Can you sort n natural numbers in increasing order with an algorithm which
(i) constant time complexity (hence independent from n)? (ii) linear time complexity O(n)? [YES/NO]
(iii) time complexity O(n2)? [YES/NO]
In each case choose one answer and give a reason for it.
(b) Suppose you are given a sorted list A of 100 different integers A1