:PROPERTIES:
:ID: 11145ec1-10c6-4a26-b669-a12065b06ae4
:mtime: 20231116150010 20231115175148 20231115085002 20231115073657 20231114115930 20231114103500 20231113213338
:ctime: 20231113213333
:END:
#+title: foundations of CS supervision 5
#+filetags: :public:project:
* Questions
2017 Paper 1 Question 2
2018 Paper 1 Question 2
2019 Paper 1 Question 1
2020 Paper 1 Question 2
* 2017 Paper 1 Question 2
** Question
Define an OCaml variant type for infinite lists, without the possibility of
finite lists. Briefly illustrate programming techniques for your variant type by
declaring
(i) a recursive functional (analogous to map for ordinary lists) that applies a
given function to every element of an infinite list.
(ii) a function for generating infinite lists of the form x, f (x), f (f (x)), . . . for
any given f and x.
[6 marks]
(b) Briefly explain why the function analogous to append (@) for ordinary lists is
of no value for your infinite list data type. Code a function to combine two
arbitrary infinite lists, yielding a result that includes the elements of both lists.
[3 marks]
(c) Use the functions declared in your previous solutions to express an infinite list
consisting of all numbers of the form $5^i \times 7^j \times 9^k$ for integers $i, j, k \ge 0$
[3 marks]
(d ) The list [1; 5; 7; 25; 9; 35; 35; . . .] is a legitimate solution to part (c) above,
but note that the integers are out of order. Code a function to merge two ordered
infinite lists, and use that to modify your previous solution to yield the same set
of numbers but in strictly increasing order. Briefly comment, with justification,
on whether merge sort for ordinary lists can be generalised to infinite lists.
** Solution
#+BEGIN_SRC ocaml
type 'a ilist = Cons of 'a * (unit -> 'a ilist)
#+END_SRC
#+RESULTS:
: type 'a ilist = Cons of 'a * (unit -> 'a ilist)
#+BEGIN_SRC ocaml
let rec view n = function
| Cons (a ,b) -> if n <= 0 then [] else a :: (view (n - 1) (b()))
#+END_SRC
#+RESULTS:
: <fun>
(i)
#+BEGIN_SRC ocaml
let rec map f = function
| Cons (head , rest) -> Cons (f head ,fun _ -> map f (rest ()))
#+END_SRC
#+RESULTS:
: <fun>
(ii)
#+BEGIN_SRC ocaml
let rec iterates f x = Cons (x , fun _ -> iterates f (f x))
#+END_SRC
#+RESULTS:
: <fun>
(b)
Append has no value on infinite lists because you would never get to the elements of the second list.
#+BEGIN_SRC ocaml
let rec interleave = function
| Cons (a , a_tail) , Cons (b , b_tail) ->
Cons (a , fun _ ->
Cons (b , fun _ -> interleave (a_tail () , b_tail ())))
#+END_SRC
#+RESULTS:
: <fun>
(c)
#+BEGIN_SRC ocaml
let rec from i j k =
Cons ((i,j,k),
fun _ -> interleave
((from i j (k + 1)) ,
(interleave ((from (i + 1) j k),
(from i (j + 1) k)))))
#+END_SRC
#+RESULTS:
: <fun>
#+BEGIN_SRC ocaml :exports both
view 10 (from 0 0 0 )
#+END_SRC
#+RESULTS:
| 0 | 0 | 0 |
| 0 | 0 | 1 |
| 1 | 0 | 0 |
| 0 | 0 | 2 |
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 1 | 0 | 1 |
| 0 | 0 | 3 |
| 0 | 1 | 1 |
| 0 | 1 | 1 |
#+BEGIN_SRC ocaml
let from x = iterates succ (succ x) ;;
let rec iterates2 x y z =
Cons((x , y , z), fun _ ->
interleave (
interleave (
map
(fun y -> (x , y , z))
(from y),
map
(fun z -> (x , y , z))
(from z)),
iterates2 (succ x) y z ))
#+END_SRC
#+RESULTS:
: <fun>
#+BEGIN_SRC ocaml :exports both
view 10 (iterates2 0 0 0)
#+END_SRC
#+RESULTS:
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 0 | 0 | 1 |
| 1 | 1 | 0 |
| 0 | 2 | 0 |
| 2 | 0 | 0 |
| 0 | 0 | 2 |
| 1 | 0 | 1 |
| 0 | 3 | 0 |
#+BEGIN_SRC ocaml
let rec pow a = function
| 0 -> 1
| 1 -> a
| n ->
let b = pow a (n / 2) in
b * b * (if n mod 2 = 0 then 1 else a)
let pows (x , y , z) = pow 3 x * pow 5 y * pow 7 z
let sol_c = map (pows) (iterates2 0 0 0)
#+END_SRC
#+RESULTS:
: Cons (1, <fun>)
#+BEGIN_SRC ocaml :exports both
view 20 (sol_c)
#+END_SRC
#+RESULTS:
| 1 | 5 | 3 | 7 | 15 | 25 | 9 | 49 | 21 | 125 | 45 | 343 | 75 | 625 | 27 | 2401 | 147 | 3125 | 63 | 16807 |
(d)
#+BEGIN_SRC ocaml
let rec merge = function
| Cons (a , b) , Cons (c , d) ->
if a < c
then Cons(a , fun _ -> merge (b () , Cons (c , d)))
else Cons(c , fun _ -> merge (Cons (a, b) , d ()))
#+END_SRC
#+RESULTS:
: <fun>
#+BEGIN_SRC ocaml :exports both
view 100 (merge ((from 1) ,(map (fun x -> x * 5) (from 2))))
#+END_SRC
#+RESULTS:
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 15 | 16 | 17 | 18 | 19 | 20 | 20 | 21 | 22 | 23 | 24 | 25 | 25 | 26 | 27 | 28 | 29 | 30 | 30 | 31 | 32 | 33 | 34 | 35 | 35 | 36 | 37 | 38 | 39 | 40 | 40 | 41 | 42 | 43 | 44 | 45 | 45 | 46 | 47 | 48 | 49 | 50 | 50 | 51 | 52 | 53 | 54 | 55 | 55 | 56 | 57 | 58 | 59 | 60 | 60 | 61 | 62 | 63 | 64 | 65 | 65 | 66 | 67 | 68 | 69 | 70 | 70 | 71 | 72 | 73 | 74 | 75 | 75 | 76 | 77 | 78 | 79 | 80 | 80 | 81 | 82 | 83 | 84 | 85 | 85 | 86 |
It would not be appropriate to try to write mergesort on infinite lists. As a reductio-ad-absurdam, the
first element of the merge-sorted list would need to be the minimum of the list, but an infinite list
may not even have a well-defined minimum (example : [0 ; -1 ; -2 ; -3 ; -4 ; ...]).
#+BEGIN_SRC ocaml
let times a b = a * b;;
let from_step x s = iterates (times s) (x) ;;
let rec sorted = Cons(1 , fun _ ->
merge (
merge (
map (times 3) (sorted) ,
map (times 5) sorted ) ,
map (times 7) sorted )
)
let rec make_uniq prev = function
| Cons (a , b) ->
if a = prev
then make_uniq a (b())
else Cons(a , fun _ -> make_uniq a (b ()))
let uniq = make_uniq 0 (sorted);;
#+END_SRC
#+RESULTS:
: Cons (1, <fun>)
#+BEGIN_SRC ocaml :exports both
let tail (Cons (a,b)) = b ();;
view 100 (uniq)
#+END_SRC
#+RESULTS:
| 1 | 3 | 5 | 7 | 9 | 15 | 21 | 25 | 27 | 35 | 45 | 49 | 63 | 75 | 81 | 105 | 125 | 135 | 147 | 175 | 189 | 225 | 243 | 245 | 315 | 343 | 375 | 405 | 441 | 525 | 567 | 625 | 675 | 729 | 735 | 875 | 945 | 1029 | 1125 | 1215 | 1225 | 1323 | 1575 | 1701 | 1715 | 1875 | 2025 | 2187 | 2205 | 2401 | 2625 | 2835 | 3087 | 3125 | 3375 | 3645 | 3675 | 3969 | 4375 | 4725 | 5103 | 5145 | 5625 | 6075 | 6125 | 6561 | 6615 | 7203 | 7875 | 8505 | 8575 | 9261 | 9375 | 10125 | 10935 | 11025 | 11907 | 12005 | 13125 | 14175 | 15309 | 15435 | 15625 | 16807 | 16875 | 18225 | 18375 | 19683 | 19845 | 21609 | 21875 | 23625 | 25515 | 25725 | 27783 | 28125 | 30375 | 30625 | 32805 | 33075 |
* 2018 Paper 1 Question 2
** Question
We have a 2-player game in which players A and B take turns to remove either the
leftmost or rightmost coin from of a row of coins of varying values. When no coins
are left, the player with the higher total value wins.
Example: For a row of coins with values given by the list [20, 40, 30, 15], player A
must select the rightmost coin (with value 15) in order to win with a total amount
of 55, leaving player B with a total amount of 50.
(a) You are given three helper functions. The first function, poplast, takes a list
and returns the list without its last element. The second function, last, takes
a list of integers and returns the last value of that list. The third function, max,
takes two integers and returns the larger of the two values.
Using these helper functions, write a recursive function winning diff that takes
a list of integers (representing the row of coins), and that returns the final
difference of amounts between players A and B, assuming that player A goes
first, and that player B plays optimally. If the difference is positive, player A
wins, if it is negative, B wins. [8 marks]
(b) We are interested in implementing a functional deque that computes poplast
and last in amortised constant time and that also enables access to the first
element in amortised constant time. Write the code for the data type, and
functions poplast and last. You may also need to code a function norm that
guarantees amortised constant time in all circumstances. [8 marks]
(c) Consider the complexity of your algorithm for winning diff for Part (a). For
this question, assume that the three helper functions compute in constant
time.
(i) Give the recurrence relation T (n) for the running time of your algorithm,
where n is the number of coins in the row.
(ii) State the complexity of the algorithm in O-notation.
** Solution
(a)
#+BEGIN_SRC ocaml
let poplast;; (* also called *)
let last;;
let max;;
#+END_SRC
#+RESULTS:
: Line 1, characters 7-9:
: 1 | let max;;;;
: ^^
: Error: Syntax error
#+BEGIN_SRC ocaml
let rec diff = function
| [] -> 0
| x :: xs -> max (x - diff xs)
(let l = last xs in l - poplast (x :: xs))
#+END_SRC
#+RESULTS:
: Line 3, characters 45-49:
: 3 | | x :: xs -> max (x - diff xs) (let l = last xs in l - poplast (x :: xs));;
: ^^^^
: Error: Unbound value last
(b)
#+BEGIN_SRC ocaml
type deq = Deque of int list * int list
(*
The deq (xs, ys) represents the list xs @ reverse ys
,*)
let norm : deq -> deq = function
| Deque (xs , []) -> Deque ([] , List.rev xs)
| d -> d
let dpoplast (d : deq) : deq =
match norm d with
Deque (xs , y :: ys) -> Deque (xs , ys)
let dlast (d : deq) : int =
match norm d with
Deque (xs , y :: ys) -> y
#+END_SRC
#+RESULTS:
: <fun>
(c.i)
Let $n$ be the size of the deque.
\[T(n) = 1 + 2T(n - 1)\]
(c.ii)
The solution to this recurrence relation is
\[T(n) = O(2^{n})\]
* 2019 Paper 1 Question 1
** Question
Three alternative representations for non-negative integers, n, are:
Peano: values have the form S(... S(Z) ...), applying S n times to Z where
S and Z are constructors or constants of some data type.
Binary: values are of type bool list with 0 being represented as the empty
list, and the least-significant bit being stored in the head of the list.
Church: values have the form fn f => fn x => f(... f(x) ...), applying
f n times to x
(a) Write ML functions for each of these data types which take the representation
of an integer n as argument and return n as an ML int. [6 marks]
(b) Write ML functions for each of these data types which take representations of
integers m and n and return the representation of m + n. Your answers must
not use any value or operation on type int or real. [Hint: you might it useful
to write a function majority: bool*bool*bool -> bool (which returns true
when two or more of its arguments are true) and to note that the ML inequality
operator ‘<>’ acts as exclusive-or on bool.] [10 marks]
(c) Letting two and three respectively be the Church representations of integers 2
and 3, indicate whether each of the following ML expressions give a Church
representation of some integer and, if so what integer is represented, and if not
giving a one-line reason.
(i) two three
(ii) three two
(iii) two ◦ three
(iv ) three ◦ two
** Solution
* 2020 Paper 1 Question 2
(a)
#+BEGIN_SRC ocaml
let church_to_int n = n (succ) (0)
#+END_SRC
#+RESULTS:
: <fun>
#+BEGIN_SRC ocaml
let bool_to_int : bool -> int = function
| false -> 0
| true -> 1
let rec bin_to_int : bool list -> int = List.fold_left (fun acc a -> bool_to_int a + 2 * acc) 0
#+END_SRC
#+RESULTS:
: <fun>
#+BEGIN_SRC ocaml
type peano = Z | S of peano
let rec peano_to_int = function
| Z -> 0
| S x -> succ (peano_to_int x)
#+END_SRC
#+RESULTS:
: <fun>
(b)
#+BEGIN_SRC ocaml
let add_church m = m succ
#+END_SRC
#+RESULTS:
: <fun>
#+BEGIN_SRC ocaml
let half_add a b = (a <> b , a && b)
let full_add a b c =
let (s ,c') = half_add a b in
let (s' ,c_out) = half_add s c in
(s' , c' || c_out)
let rec add_bins_acc (acc : bool) : bool list * bool list -> bool list = function
| x , [] -> x
| [] , y -> y
| a :: atail , b :: btail ->
let (res, carry) = full_add a b acc in
res :: add_bins_acc carry (atail , btail)
let add_bins = add_bins_acc false;;
#+END_SRC
#+RESULTS:
: <fun>
#+BEGIN_SRC ocaml :exports both
(*5 + 4 = 1*)
add_bins ([true ; false ; true] , [false ; false ;true])
#+END_SRC
#+RESULTS:
| true | false | false |
#+BEGIN_SRC ocaml
let rec add_peano x = function
| Z -> x
| S y -> S (add_peano x y)
#+END_SRC
#+RESULTS:
: <fun>
(c.i)
\begin{align}
&two three f x\\
&= three (three f) x \\
&= nine f x
\end{align}
(c.ii)
\begin{align}
&three two f x\\
&= two (two (two f)) x \\
&= eight f x
\end{align}
(c.iii)
\begin{align}
&(two \circ three) f x \\
&= two (three f) x \\
&= six f x
\end{align}
(c.iv )
\begin{align}
& three \circ two f x \\
&= three (two f) x \\
&= six f x
\end{align}
** Question
In this exercise, we will develop a game engine to play a simplified version of the
game of Mastermind.
In simplified Mastermind, player A selects a list of n colours among 3 possible colours:
Red, Green and Blue (e.g., [Red; Red; Green; Blue] if n = 4). Player B has to guess
player A’s list of colours by proposing lists of colours in sequence until she finds the
list proposed by player A. Every time player B proposes a list of colours, she gets
feedback in the form of a number x. (x is the number of colours that are in the
correct position). For example, if player A’s list is [Red; Red; Green; Blue] and player
B guessed [Red; Green; Green; Red], then x = 2 (the first Red and second Green are
at the right positions). Note that x ≤ n.
(a) Define a type colour to represent a colour. [2 marks]
(b)Given two colour lists, write a function feedback that returns x. The first
argument a is the list of player A, and the second argument b is a list of player B.
Raise a SizeMismatch exception if the lengths of both lists do not match.
You may need to introduce a helper function. [4 marks]
(c) Using currying, define a test function that takes a list proposed by player B
and returns x. This function should assume that player A’s list is [Blue; Green;
Red]. [2 marks]
(d ) What is the type of test in Part (c)? [2 marks]
(e) Write a function generate lists that generates all possible colour lists of a
given length n. The function takes a single argument n. You may use the
concatenation operation @ and List.map function. Tip: generate 2 should
output 32 = 9 lists. [6 marks]
(f ) Given a colour list of player B and a feedback x, write a function valid lists
that takes two arguments b and x and returns all possible lists that player A
could have chosen (such that they match the feedback given to player B). You
may use generate lists, feedback, List.length and/or List.filter
** Solution
(a)
#+BEGIN_SRC ocaml
type color =
| Red
| Green
| Blue
#+END_SRC
#+RESULTS:
: type color = Red | Green | Blue
(b)
#+BEGIN_SRC ocaml
let kroenecker_delta a b = if a = b then 1 else 0
let score_guess secret guess = List.fold_left
(fun acc (a ,b) -> acc + kroenecker_delta a b)
0
(List.combine secret guess)
#+END_SRC
#+RESULTS:
: <fun>
(c)
#+BEGIN_SRC ocaml
let test : color list -> int = score_guess [Blue; Green;Red]
#+END_SRC
#+RESULTS:
: <fun>
(d)
color list -> int
(e)
#+BEGIN_SRC ocaml
let rec all_guesses : int -> color list list = function
| 0 -> [[]]
| n -> List.concat_map (fun c -> [Red :: c ; Blue :: c ; Green :: c]) (all_guesses (n - 1))
#+END_SRC
#+RESULTS:
: <fun>
(f)
#+BEGIN_SRC ocaml
(*
Given a colour list of player B and a feedback x, write a function valid lists
that takes two arguments b and x and returns all possible lists that player A
could have chosen (such that they match the feedback given to player B). You
may use generate lists, feedback, List.length and/or List.filter
,*)
let valid_lists (secret : color list) (feedback : int) : color list list
= List.filter
(fun guess -> score_guess secret guess = feedback)
(all_guesses (List.length secret))
#+END_SRC
#+RESULTS:
: <fun>