Question 1:

a. We initialise four variables a, b, m and lst as follows:

a=1

b=2

m  =  [[3.0,4.0],a,b]

lst  =  ["5","6",m]

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

(ii)  Using only the content of m and lst, write code to get the following output without modifying the content of any of the variables. You are expected to use coercion, indexing, and slicing for this.

[1,  2,  3,  4,  5,  6]

(iii) After the previous initialisation, we run these lines of code: m[1]=2

b  = b  +  1

lst[2][0][0]  = b

Draw how the four variables now look in memory.

(iv)  Using exclusively m, create a variable my list that looks like this:

[[3,  4.0,  3,  4.0],  [3,  4.0,  3,  4.0],  [3,  4.0,  3,  4.0]]

(v) m is currently [[3, 4.0], 2, 2].  Write a function foo with one parameter l, so that, after running foo(m), m will look like this: [[2,2,3,4.0]]

The function should only use the content of the list m.

(10 marks)

b.  Define a function split and merge(a,b) which given two strings a and b, will split the content of both variables into two parts (of the

same size) each. Then it will merge the splits of both strings, so that: split_and_merge("Stupid","Program")

should return ’StuPropidgram’.

Both strings a and b will have an even number of elements.

Will your solution work with two lists?  Briefly explain your answer   (5 marks)

c.  Define a function split and merge 2(lista,word) which given a list lista and a string word, it will change the input list lista as follows.  It will first split the content of both variables into two parts (of the same size) each.  Then it will merge the splits, so that, the function should behave as follows:

lista  =  list("Stupid")

word  =  "Program"

split_and_merge_2(lista,word)

print(lista)

[’S’,’t’,’u’,’P’,’r’,’o’,’p’,’i’,’d’,’g’,’r’,’a’,’m’]

The function should not return a result.  Both variables lista and word will have an even number of elements.

Will your solution work if lista is a string?  Briefly explain your answer.

(5 marks)

d.  Using the diagrams explained in the lecture to represent variables in memory and the stack, explain what is the output of the following program and why:

var  =  1

lst  =  [1,2,3]

def  test(var,l)  :

var  =  var+1

print(var)

l  =  [3,2,1]

print(l)

test(var+1,lst)

print(var)

print(lst)

(5 marks)

Question 2:

a.   (i)  Fill the gaps with either True, False, or Boolean operators, to obtain the output you see below:

b  =  <GAP>

c  = not b

d  = b  <GAP>  c

if b  and  c  or  d:

print("Option  1")

else:

print("Option  2")

Output:

’Option  1’

(ii)  Fill the gaps to obtain the output you see below: try:

x  =  <GAP>

y  =  <GAP>

print(<GAP>)

z  =  int(x)

print("End")

except ValueError:

print  ("Ups!  there was  an  error")

Output:

a4

Ups!  there was  an  error

(iii)  Fill the gaps to obtain the output you see below:

count  =  0

while  <GAP>:

if  <GAP>:

print(".",end="")

else:

print("-",end="")

count  +=1

Output:

.---.---.-

(iv)  Fill the gaps to obtain the output you see below:

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

for  i  in  <GAP>:

print(lst[i],end=",")

print()

for  i  in  <GAP>:

print(lst[i],end=",")

Output:

10,8,6,4,2,

9,7,5,3,1,

(v)  Using for loops, implement a Python program that prints this:

*  _  _  _  _ _  *  _  _  _ _  _  *  _  _ _  _  _  *  _ _  _  _  _  *

(10 marks)

b. Write a function sum divisors(a) that returns the sum of the di- visors of the input parameter a (except itself). Remember that a di- visor of a number is a positive number that divides it with remainder 0.

For example, the sum of divisors for 220 is: 1+2+4+5+10+11+20+44+55+110 = 284.

sum_divisors(220)

284

The function assumes that the input is always a positive integer.      (5 marks)

c.  Using the previous function sum divisors(a), you are asked to write a function amigos that returns True if the two input parameters (two integer numbers) are amicable numbers.  Two number a and b are amicable numbers (numeros amigos) if the sum of the divisors (except itself) of each is equal to the other number.

For example, 220 and 284 are amicable.

sum_divisors(220)

284

sum_divisors(284)

220

Your function should work as follows:

amigos(15,20)

False

amigos(220,  284)

True

Your function should handle wrong inputs and return an error in that case.

amigos(’Isaac’,’Thorsten’)

’Error: Wrong  input’

(5 marks)

d. You are now asked to write another function list amigos(n,m) that takes two parameters n and m and prints all the pairs of amicable numbers in the interval  [n,m].  We assume that m is always higher than n.

For example:

list_amigos(1,2000)

6,6

28,28

220,284

284,220

496,496

1184,1210

1210,1184

Depending on how you implement it, this function is likely to be very slow. If you want to obtain full marks, this needs to be efficient.      Hint 1: You do not need to check all pairs in the range  [n,m].       Hint 2:  Additionally, you could calculate the sum of divisors for all the numbers in the range [n,m] using the sum divisors(a) function and store it separately.

(5 marks)

Question 3:

a. We want to define recursive implementations of the reverse function for lists and the Fibonacci sequence 1, 1, 2, 3, 5, 8, · · · ? What is miss- ing from the following definitions:

def  rev(l)  :

return  rev(l[1:])+[l[0]]

def  fib(n)  :

return  fib(n-1)+fib(n-2)

Complete the definitions so that the functions work correctly for pos- itive integers (including 0), e.g.

rev([1,2,3])

Out:  [3,  2,  1]

fib(5)

Out:  8

(10 marks)

b. Write a recursive function tails that computes all the terminal seg- ments of a list. That is for example:

tails([1,2,3])

returns:

[[1,  2,  3],  [2,  3],  [3],  []]

The program should not modify its input and should only use opera- tions that were introduced in the lecture.

(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:

We define the following classes to represent a simple file system:

File everything is a file,

PlainFile  a plain file has a name (we are ignoring its contents), Directory  has a name and its contents are a list of files.

This can be implemented using the following class definitions:

class  File  :

pass

class  PlainFile(File)  :

def  __init__(self,name)  :

self.name  = name

class  Directory(File)  :

def  __init__(self,name,contents)  :

self.name  = name

self.contents  =  contents

Here is an example for a file system:

fs  =  Directory("root",

[PlainFile("boot.exe"),

Directory("home",[

Directory("thor",

[PlainFile("hunde.jpg"),

PlainFile("quatsch.txt")]), Directory("isaac",

[PlainFile("gatos.jpg")])])])

a.  Using fs answer the following questions:

(i) Write a Python expression that evaluates to boot.exe by ac- cessing fs.

(ii) Write the python expression that evaluates to thor by accesing fs.

(iii) Write  a  python statement that changes the  name of the file hunde.jpg to dogs.jpg in fs.

(iv) Write a python expression that removes the file quatsch.txt in fs but doesn’t change anything else.

(v) Add a hard link to the directory isaac in the directory thor in fs. This means that the directory thor now contains a reference to the directory isaac.  In unix this is achieved with the command ln.

(10 marks)

b. Add methods that print the file system tree (i.e.  define appropriate __str__ methods).

To apply str to a list you can use the following function:

def  str_list(l)  :

return  "["+’,’.join(map(str,l))+"]"

You don’t need to produce a pretty output - it is ok if it looks like this:

Directory(root,[PlainFile(boot.exe),Directory(home,

[Directory(thor,[PlainFile(hunde.jpg),PlainFile(           quatsch.txt)],Directory(isaac,[PlainFile(gatos.jpg)]]]

(10 marks)

c.  Implement a method find(name) for all the subclasses of file which tries to find a file name in a filesystem and returns the path to the

first occurence of the file if it finds it but False otherwise.

So for example:

fs.find("gatos.jpg")

Out:  ’root/home/isaac/gatos.jpg’

fs.find("thor")

Out:  ’root/home/thor’

fs.find("unix")

Out:  False

(5 marks)