[SOLVED] EXAMINATIONS 2019/2020

UNIVERSITY OF PORTSMOUTH
SCHOOL OF COMPUTING
FIRST ATTEMPT EXAMINATIONS 2019/2020
U21276 THEOCS THEORETICAL COMPUTER SCIENCE

Copyright By Assignmentchef assignmentchef

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) Calculate the value A(1, 2) of the Ackermann function defined by:
Show your working.
A(0, y) = y + 1
A(, 0) = A( 1, 1)
A(, y + 1) = A( 1, A(, y))
[4 marks] (b) From each of the statements (i)-(iii) choose the best characterisation for the
Ackermann function.
The Ackermann function is
(i) total/partial/it is unknown whether it is total or partial. (ii) primitive recursive/not primitive recursive/it is unknown.
(iii) computable/non-computable/it is unknown. In each case clearly justify your answer.
(c) Describe in detail the simple programming language computational model from the lectures. Is the Turing machine model a more powerful computa- tional model than simple programming language? Explain why or why not.
(d) Explain briefly the Church-Turing thesis.
(e) Write a Markov algorithm over the alphabet {, b, c} which interchanges all s and bs in each input string,
e.g. the input bcb will be modified to bbcb.
[6 marks] [Total marks for the question: 25 marks]
U21276/THEOCS, Page 3 of 8

Question 2: Decidable and undecidable problems
(a) For the following instance of the Posts correspondence problem over {, b, c}
find a solution or state that no solution exists (give a reason): {(b, c), (, b), (c, ), (bc, c), (b, b), (b, b)}.
Is it true that the Posts correspondence problem is partially decidable? Jus- tify your answer.
(b) Is it true that the problem from (a) cannot be solved on todays 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) Give a full description of one decidable problem and explain why your prob-
lem is decidable.
(d) Suppose a list A contains n different randomly generated strings over the
alphabet {, b, c}, and the length of each string is at least n, n 5. Describe clearly how you would construct a string of length m over the
alphabet {, b, c} which is not in the list A: (i) for m < n,(ii) for m = n.(iii) for m > n.
(e) Decide whether the size of each set (i)(ii) is countable or uncountable.
Clearly justify your answer.
(i) The set of all languages over the alphabet {, b, c}.
(ii) The set S of all languages over the alphabet {, b, c} with the property: each language from S contains only strings of length 2019.
[5 marks] [Total marks for the question: 25 marks]
U21276/THEOCS, Page 4 of 8

Question 3: Time-complexity
(a) Consider the following nine functions from N R:
200 n n20 n9log2n n! 3 8 2 n2n 3 2 , 2019, 2019, 5 , 202019, 200 n log2n, n, (log2n) , 1200
(i) Order the functions in terms of their growth rate from slowest to fastest. [7 marks]
(ii) List all of the functions that are in O(n2).
(iii) List all of the functions that are in (n10).
(b) Suppose you have a computer that requires 1 minute to solve a problem using your algorithm A for instances of size n = 1000. Suppose you buy a new computer that runs 1000 times faster than the old one, hence the new computer runs 1000 times more operations for the same input. What size of input can be run in 1 minute on the new computer, assuming the following time complexities T(n) for the algorithm A? Show your working.
(i) T(n) = n, (ii) T(n) = n3,
(iii) T(n) = 10n.
U21276/THEOCS,
Page 5 of 8
[Question 3 continued over the page]

(c) Given the following algorithm: //, j, n are integer variables
for := 1 to n do
for j:=1 to 3n do
if j=3 then S;
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(5), i.e. how many times the statement S is exe-
cuted for n = 5. Show your working.
(ii) Choose the growth of the function T(n) from the given list and justify
your answer:
(iii) Express T(n) as a function of n.
(iv) Is it true that if the condition j = 3 is changed to j = 3, hence the algorithm is:
for := 1 to n do
for j:=1 to 3n do
if j=3 then S;
then the growth of the function T(n) becomes exponential? Justify your
(n), (n2), or (2n).
[Total marks for the question: 25 marks]
U21276/THEOCS, Page 6 of 8

Question 4: Computational complexity
(a) An Eulerian graph is a graph containing an Eulerian circuit a closed walk which uses each edge in the graph exactly once. A connected graph is Eulerian if and only if all vertices are of even degree.
Discuss the complexity of the following decision problem: is a given con- nected graph (the input) Eulerian?
Choose one of the following options for its complexity and explain: P, NP, NP-complete, undecidable.
(b) A Hamiltonian cycle is a cycle in an undirected graph that visits each vertex exactly once and returns to the starting vertex. Determining whether such a cycle exists in a graph is the Hamiltonian problem, which is known to be NP-complete.
(i) Explain what it means for the Hamiltonian problem to be NP-complete.
(ii) Suppose that somebody proves that the satisfiability problem (one of the basic NP-complete problems) can be solved in polynomial time. Would it change the complexity of the Hamiltonian problem? Give an explanation.
(c) Describe clearly a problem from the class P.
(d) Explain what is the lower and upper bound of the complexity for a problem. What can you say about the lower and upper bound of the problem to sort n natural numbers in increasing order?
[Question 4 continued over the page]
U21276/THEOCS, Page 7 of 8

(e) What are approximation algorithms and what are they used for?
[3 marks] (f) From the problems below choose all tractable problems and justify your an-
(i) searching for a minimum in an unordered array of integers, (ii) the Halting problem,
(iii) the Hamiltonian problem.
END OF EXAM
[3 marks] [Total marks for the question: 25 marks]
U21276/THEOCS,
Page 8 of 8

CS: assignmentchef QQ: 1823890830 Email: [email protected]