[SOLVED] CS Java University of Sussex Informatics

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={xN|x=x+1}andB=
(d) A={xN|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