G54PRG/COMP4008 Programming 2019-2020

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)

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)

 

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

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)

 

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:

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:

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)

 

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.

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