The University of Nottingham
SCHOOL OF COMPUTER SCIENCE
A LEVEL 4 MODULE, AUTUMN SEMESTER 2019-2020
Programming
G54PRG/COMP4008
Time allowed 2 Hours
Candidates may complete the front cover of their answer book and sign their
desk card but must NOT write anything else until the start of the examination
period is announced
Answer ALL FOUR questions
No calculators are permitted in this examination.
Note that all the questions are about Python 3.x.
Dictionaries are not allowed with one exception. Those whose first language is
not English may use a dictionary to translate between that language and English
provided that neither language is the subject of this examination. No electronic
devices capable of storing and retrieving text may be used.
DO NOT turn examination paper over until instructed to do so
COMP4008.G54PRG-E1 1 Turn Over
2 COMP4008.G54PRG-E1
Question 1:
a. We initialise two variables m and lst as follows:
m = [’A’,[]]
lst = [m[0], 3, m]
If we execute the following lines of code in order, what is the output
of each line?
lst[1:]
lst[0][0][-1]
lst[:1]+lst[-1:]
[lst[1]]+[lst[0]]
m[1]=[1,2,3]
lst
Some lines may have no output or trigger an error. In the latter
case, specify what the reason of the error is. Note that some
instructions may depend on the result of previous lines (e.g. a
previous assignment).
(10 marks)
b. Define a function shiftRight which receives a list as input, and
returns a list with all the elements shifted to the right, so that, the
last element will become the first. You may assume that the list has
at least one element. E.g. the function should behave as follows:
myList = list("Thor")
shiftRight(myList)
[’r’, ’T’, ’h’, ’o’]
Will your solution work with strings? Briefly explain your answer.
(5 marks)
COMP4008.G54PRG-E1 2
3 COMP4008.G54PRG-E1
c. Define a function shiftRightX which gets a list as input, which will
be modified, shifting its elements to the right, so that, the last element
will become the first. The function should not return anything. You
may assume that the list has at least one element. E.g. the function
should behave as follows:
>> myList=list("Thor")
>> shiftRightX(myList)
>> myList
[’r’, ’T’, ’h’, ’o’]
Will your solution work with strings? Briefly explain your answer.
(5 marks)
d. What would be the output of the following program?
var = 1
def test(var) :
var = var+1
print(var)
test(var+1)
print(var)
(5 marks)
COMP4008.G54PRG-E1 3 Turn Over
4 COMP4008.G54PRG-E1
Question 2:
a. What are the outputs of the following programs?
(i) b = True
c = not b
d = b and c
if b and c or d:
print("a")
elif b or c and d:
print("b")
else :
print("c")
(ii) x = 3
try :
x = int("x")
print("a")
except ValueError:
print("b")
(iii) b=True
while b :
print("a",end="")
b = not b
if not b :
break
print("b",end="")
print("c",end="")
(iv) x=-2
try :
x = int(x)
print("7",end="")
except ValueError :
print("8")
(v) for i in range(0,2):
for j in [’1’,2,’3’]:
print(j, end=",")
(10 marks)
b. Write a function isPrime that returns True if the input parameter
is a prime number, and False if it is not. Remember that a prime
number is a number (greater than 1) that is only divisible by itself and
COMP4008.G54PRG-E1 4
5 COMP4008.G54PRG-E1
1 with remainder 0. The function assumes that the input is always
higher than 0. For example:
>> isPrime(2)
True
>> isPrime(4)
False
(5 marks)
c. Using the previous function isPrime, you are asked to write another
function primes that prints the first n prime numbers. The function
receives the total number of prime numbers to print as input. For
example:
>> primes(10)
2 3 5 7 11 13 17 19 23 29
(5 marks)
d. Write a function transpose that gets a square matrix (same number
of rows and columns) as a 2-dimensional list. The function should
return the transpose of the matrix, so that, the rows and columns are
swapped.
For example given,
matr = [[1,2,3],
[4,5,6],
[7,8,9]]
the call
transpose(matr)
should return:
[[1, 4, 7],
[2, 5, 8],
[3, 6, 9]]
The program should not modify the input but return a new matrix
which is the transpose of the input. (5 marks)
COMP4008.G54PRG-E1 5 Turn Over
6 COMP4008.G54PRG-E1
Question 3:
a. Given the following recursive functions:
def f0(x) :
if x==-1 :
return 0
else :
return 1-f0(x-1)
(i) What is the output of f0(3)?
def f1(x) :
if x==1 :
return 0
else:
return 1+f1(x+2)
(ii) What is the output of f1(4)?
def f2(x) :
if x==5 :
return x
else :
y,z = f2(x+1),f2(x+1)
return y+z
(iii) What is the output of f2(3)?
def f3(x) :
if x==0 :
return -1
else :
return f3(x-1)+f3(x-1)
(iv) What is the output of f3(3)?
def f4(x):
if x>0:
f4(x-1)
print("*",end="")
f4(x-1)
(v) What is the output of f4(2)?
(10 marks)
b. Write a recursive function inits that computes all the initial seg-
ments of a list. That is for example:
COMP4008.G54PRG-E1 6
7 COMP4008.G54PRG-E1
inits([1,2,3])
returns:
[[1, 2, 3], [1, 2], [1], []]
The program should not modify its input. (10 marks)
c. Write a program that computes a knight’s tour of the chess board
using backtracking. A knight is a chess piece that can move as follows:
A knight’s tour is a sequence of moves where the knight starts on
the top-left corner (coordinates y=0,x=0) and visits all chess fields
exactly once.
To make it easier here is some initialisation code:
size = 8
board = []
for y in range(size) :
board = board + [[-1]*size]
moves= [[1,2],[1,-2],[-1,2],[-1,-2],
[2,1],[2,-1],[-2,1],[-2,-1]]
board contains the board representing the fields the knight has visited
(with the number of the move filled in). -1 means the knight hasn’t
yet visited this field. moves contains all the 8 possible moves of the
knights in the form of the difference in the y and the x direction.
Your task is to provide a function:
COMP4008.G54PRG-E1 7 Turn Over
8 COMP4008.G54PRG-E1
def knight(n,y,x)
which prints a solution (or several solutions) of the problem, where n
is the number of the move (starting with 0), and y, x is the current
position of the knight. E.g.
knight(0,0,0)
should print the first knights tour, starting in the position (0, 0) and
then print the remaining solutions once the user has pressed the return
key.
knight(0,0,0)
[[ 0, 3, 56, 19, 46, 5, 48, 21],
[33, 18, 1, 4, 57, 20, 45, 6],
[ 2, 55, 34, 59, 36, 47, 22, 49],
[17, 32, 37, 54, 51, 58, 7, 44],
[38, 13, 52, 35, 60, 43, 50, 23],
[31, 16, 39, 42, 53, 26, 61, 8],
[12, 41, 14, 29, 10, 63, 24, 27],
[15, 30, 11, 40, 25, 28, 9, 62]]
That is the number in each field now represent the number of the
step when the knight has visited the field. (5 marks)
COMP4008.G54PRG-E1 8
9 COMP4008.G54PRG-E1
Question 4:
a. Given the following class definitions:
class Tree :
def setx(self) :
self.x=10
class Node (Tree) :
def __init__(self,left,right) :
self.left,self.right = left,right
def __str__(self) :
return "({},{})".format(self.left,self.right)
class Leaf (Tree) :
def __str__(self) :
return "[]"
We create a variable mytree as follows:
mytree = Node(Leaf(),Node(Leaf(),Leaf()))
What are the outputs of the following blocks of code?
(i) print(mytree)
(ii) print(mytree.right.left)
(iii) mytree.left = mytree.right
print(mytree)
(iv) mytree.left.setx()
print(mytree.right.x)
(v) mytree.right = mytree
print(mytree)
(10 marks)
b. Design a class hierarchy to represent a simple knowledge base which
can for example be used to implement a simple customer advice sys-
tem.
Knowledge A superclass, all subclasses of Knowledge implement a
run() method which implements a simple dialogue.
Question Representing a yes/no question. Objects are created using
Question(s,y,n) where s is the question string and y,n are
Knowledge objects representing the yes/no cases.
COMP4008.G54PRG-E1 9 Turn Over
10 COMP4008.G54PRG-E1
Answer Representing an answer. Objects are created using Answer(a)
where a is the string representing the answer.
For example: we create the following knowledge base:
kb = Question("Do you want to carry it around?",
Question("Do you need to make calls?",
Answer("Buy a mobile phone."),
Answer("Buy a tablet.")),
Answer("Buy a computer"))
(i) Define the classes with the appropriate __init__ methods such
that we can create the knowledge base. (6 marks)
(ii) Implement run methods which conduct a dialogue with the user
and finish with a recommendation. E.g. we can have the follow-
ing runs:
>>> kb.run()
Do you want to carry it around?yes
Do you need to make calls?no
Buy a tablet.
or
>>> kb.run()
Do you want to carry it around?no
Buy a computer
(4 marks)
c. We can use classes to implement lists as follows:
class List:
pass
class Nil (List) :
def __str__(self) :
return "Nil()"
def append(self,lst) :
pass
class Cons (List) :
def __init__(self,hd,tl) :
self.hd = hd
self.tl = tl
COMP4008.G54PRG-E1 10
11 COMP4008.G54PRG-E1
def __str__(self) :
return "Cons("+str(self.hd)+","+str(self.tl)+")"
def append(self,lst) :
pass
For example we can create 2 lists and print the first:
lst1 = Cons(1,Cons(2,Cons(3,Nil())))
lst2 = Cons(4,Cons(5,Nil()))
print(lst1)
Which results in the following output.
Cons(1,Cons(2,Cons(3,Nil())))
Complete the definition of append method, so that it appends two
lists (without modifying the existing lists). e.g.
print(lst1.append(lst2))
has the following output:
Cons(1,Cons(2,Cons(3,Cons(4,Cons(5,Nil())))))
(5 marks)
COMP4008.G54PRG-E1 11 END