University of Sussex Informatics
Spring 2021
Limits of Computation
Exercises 1
Effective Procedures, Problems, WHILE Syntax
(covers Lectures 1 – 3)
1. What are the four defining characteristics of effective procedures?
2. For each problems below state whether it is a function problem (and if so, if it is an optimisation problem), a decision problem, or whether it does not qualify as problem in our sense. If it is not a problem in our sense explain why it is not.
(a) Is 221 a prime number?
(b) Given a finite array of integers, what is the sum of all its values?
(c) Can an integer number n be divided by 7?
(d) Does a given Java program run on a Java SE10 virtual ma-
chine with input string “Turing” return the string “Icon”?
(e) What is the maximum value of a given function f on the real
numbers in a given interval [a, b]?
(f) What is the meaning of life?
3. For the pairs of sets A and B in (a)-(e) below, explain whether A ⊆ B (A is a subset of B), whether B ⊆ A (B is a subset of A), whether A = B, and whether A ̸= B.
(a) A = {1,3,5} and B = {1,3,5,6} (b) A = {1,3,3,3} and B = {1,3}
(c) A={x∈N|x=x+1}andB=∅
(d) A={x∈N|even(x) ∧ x<11}andB={0,2,4,6,8,10}
4. Which of the following are legal expressions or legal commands, respectively, in core WHILE (as presented in Lecture 3)?
1
(a) tl nil (b) tl rl
(c) cons hd hd x x tl x (d) while a { cons hd a }
(e) if tl tl X { } else { X:= Y } 5. Given are the following elements of D:
s = ⟨⟨nil.nil⟩.nil⟩ t = ⟨nil.⟨nil.nil⟩⟩
(a) Draw s and t as (two-dimensional) trees.
(b) Iss=t?
(c) State whether s and t, respectively, can be read as numbers, and if so, which numbers?
(d) State whether s and t, respectively, can be read as lists, and if so, which lists?
2