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