Question 1:

1. We initialise three variables a, lst and m as follows:

a = 3

lst = [[4.5,['1'],a]]

m = [lst[0][1],lst[0],a]

(a) Draw how these three variables look like in memory, using the same style that we have explained in the lecture.

(b) If we execute the following lines of code in order, give the output of each line and briefly explain why it appears:

m[0]+m[1]+a

m[1:-1][0][-1]

str(lst[0][0])+lst[0][1][0]

lst[0][2]=[0]

print(m)

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]

2. Define a function repl_last_2rows(mat,lst) which has a matrix and a list as its input and which returns the matrix with the last two rows replaced with lst. The function should not modify the matrix mat or the list lst.  You may assume that the matrix mat has at least two rows. E.g. the function should behave as follows:

>> matriz = [[1,2,3],

[4,5,6],

[0,0,0]]

>> row = [7,8,9]

>> z = repl_last_2rows(matriz,row)

>> print(z)

[[1, 2, 3], [7, 8, 9]]

[5 marks]

3. Define a function repl_last_2rows_x(mat,lst) which has a matrix and a list as its input and modifies the matrix mat by replacing the last two rows with lst. The function should not return anything. You may assume that the matrix mat has at least two rows. E.g. the function should behave as follows:

>> matriz = [[1,2,3],

[4,5,6],

[0,0,0]]

>> row = [7,8,9]

>> repl_last_2rows_x(matriz,row)

>> print(matriz)

[[1, 2, 3], [7, 8, 9]]

[5 marks]

4. What would be the output of the following program? Explain your answer.

var = 1

def foo(x):

return var + 1

def test(var) :

var = var+foo(var)

print(var)

test(var+1)

print(var)

[5 marks]

3. Write a function shuffle_matrix(mat) that will return a new matrix in which the rows of the input matrix mat have been randomly shuffled (without repetition!). You have to use the random library from Python to shuffle the rows (random.randint(0,number of rows)).  For full marks, you need to take into consideration that the random.randint function will pro- vide random numbers within the specified range with a replacement policy, meaning that you could get the same random number multiple times when running that function. The shuffle_matrix(mat) function could give a different result every time you run it (including showing the original matrix!):

>> matr = [[1,2,3],

[4,5,6],

[7,8,9]]

>> shuffle_matrix(matr)

[[4, 5, 6], [1, 2, 3], [7, 8, 9]]

>> shuffle_matrix(matr)

[[1, 2, 3], [7, 8, 9], [4, 5, 6]]

[5 marks]

4. Write a function sub_matrix(mat,row,col) that returns a sub matrix of the input matrix mat by deleting the row and/or column indicated as indexes.  Your function should allow us to only delete a row or a column if it is specified as a parameter.  This means that the parameters row and col are optional! The function should not modify the input but return a new matrix which is a sub-matrix of the input. You don’t need to handle error cases. The function should work as follows:

>> matr = [[1,2,3],

[4,5,6],

[7,8,9]]

>> sub_matrix(matriz,1,1)

[[1, 3], [7, 9]]

>>sub_matrix(matriz,0,0)

[[5, 6], [8, 9]]

# if we don't specify any row or column, the original matrix is returned.

>>sub_matrix(matriz)

[[1, 2, 3], [4, 5, 6], [7, 8, 9]]

>> sub_matrix(matriz,row=1)

[[1, 2, 3], [7, 8, 9]]

[5 marks]

5. If we assume that there is a function that decides the Halting problem we can derive a contradiction.

To be precise if we assume that there is a program

def halts(prm,args) :

that returns True if prm is a string containing the code of a Python program which terminates (i.e. doesn’t run forever) when applied to a string args as an input, and False otherwise.

Show that this is impossible by deriving a contradiction.  Hint:  You need to construct a Python program that will run forever when it terminates and terminates when it runs forever.

[5 marks]

Question 3:

1. Evaluate the following recursive functions:

(a) What is the output of f0(3)?

def f0(n) :

if n==0 :

return 0

else :

return 1+f0(n-1)

(b) What is the output of f1(4)?

def f1(n) :

if n==0 :

return 0

else :

return 2+f1(n-1)

(c) What is the output of f2(3)?

def f2(n) :

if n<=1 :

return 0

else :

return 1+f2(n-2)

(d) What is the output of f3(3,4)?

def f3(m,n) :

if m==0 :

return n

else :

return 1+f3(m-1,n)

(e) What is the output of f4(3,4)?

def f4(m,n) :

if m==0 :

return 0

else :

return f3(f4(m-1,n),n)

In each case, explain how Python calculates the answer.  Describe the function in one short sentence.

[10 marks]

2. Define a recursive function foo that given a list of numbers returns a list of sums of adjacent numbers, e.g.

>> foo([1,2,3,4,5])

[3, 5, 7, 9]

>> foo([10,5,20,6])

[15, 25, 26]

>> foo(foo([1,2,3,4,5]))

[8, 12, 16]

Note that the output list will be one element shorter than the original list.  Hence the function should return [] for the empty and one-element list.

[10 marks]

3. Implement a Python program that finds all possible paths through a maze from a given starting position to a marked target. This is excluding paths where you walk in a circle, i.e. you should visit each spot at most once.

#################

#      ###   ##

# #### #### ## ##

# ####     ## ##

# ############ ##

# * ## #      #

####     #### ##

#################

Here # stands for walls, * is the target and empty space are paths. You may assume that the boundary of the maze consists of walls (#).  Running the program finds two paths which are represented by a dot ".". On the example we get the following output:

#################

#...... ###....##

# ####.####.##.##

# ####......##.##

# ############.##

# *..## #...... #

####......#### ##

#################

More?

and after pressing return it shows the 2nd solution:

#################

#.     ###   ##

#.#### #### ## ##

#.####     ## ##

#.############ ##

#.* ## #      #

####     #### ##

#################

More?

>>>

We assume that the maze is stored in a global variable maze which is a list of lists, such that maze[y][x] is the item at the yth row and xth column, which is either "#", " " or "*" initially. Later it will also contain way markers ".".

You can assume that there is a function print_maze() with no parameters that prints the current maze.

Implement a function solve(x,y) that finds a path from position (x, y) to the * and then prints it and waits for further input before it displays further solutions. The output above is produced by calling solve(1,1).

[5 marks]

Question 4:

We want to represent boolean expressions like !(x&y)|x&y as trees in Python together with printing and evaluation functions.

1. Define classes for expressions only using | (Or) and ! (Not). Include variables represented as strings and introduce an (abstract) superclass Expr. Implement __init__ methods which create the tree structure using instance variables. E.g. the following examples should be definable:

e1 = Or (Var ("x") , Not (Var ("x")))

e2 = Or (Var ("x") , Not (Var ("y")))

e3 = Or (Not(Or(Var("x"),Var("y"))),Or(Var("x"),Var("y")))

[5 marks]

2. Define __str__ methods which produce a readable version of the tree. You don’t need to minimimise brackets but the output should be unambiguous.  E.g. the examples should produce the following outputs:

>> print(e1)

(x|!x)

>> print(e2)

(x|!y)

>> print(e3)

(!(x|y)|(x|y))

[5 marks]

3. We want to evaluate the expressions with respect to an assignment of truth values to variables represented as a dictionary like:

env = {"x" : False , "y" : True}

Implement a method eval for all the classes which gets a dictionary as a parameter. E.g. we expect the following behaviour:

>> e1.eval(env)

True

>> e2.eval(env)

False

>> e3.eval(env)

True

[5 marks]