:PROPERTIES: :ID: 1dbb5e3c-b468-4dd9-99e1-849b897de4b5 :mtime: 20231013112933 20231012032909 20231012001337 20231011020124 20231008091438 20231007034631 20231007001506 20231006231454 :ctime: 20231006231451 :END: #+title: Foundations of CS Supervision 1 Questions -- Atticus Kuhn #+filetags: :public:project: * Source of the Questions The questions can be found at https://www.cl.cam.ac.uk/teaching/2223/FoundsCS/materials.html * 1999 Paper 1 Question 1 ** Question A permutation of a list is any list that can be derived from it by re-arranging the elements. Write an OCaml function that returns the list of all the permutations of its argument. Explain your code clearly and carefully. For example, applied to the list [1; 2; 3], your function should return the list whose elements are [1; 2; 3], [2; 1; 3], [2; 3; 1], [1; 3; 2], [3,1,2] and [3,2,1]. You may assume that the elements of the argument are distinct. The elements of the result may appear in any order ** Solution Define a function called "insertInto", which inserts an element into a list. #+BEGIN_SRC ocaml :exports code let rec insertInto (x :'a) (xs : 'a list) : 'a list list = match xs with | [] -> [[x]] | h :: t -> (x :: xs) :: (List.map (fun x -> h :: x) (insertInto x t)) #+END_SRC #+RESULTS: : <fun> Use the function "insertInto" to recursively insert each element of the list, thus giving us all valid permutations. #+BEGIN_SRC ocaml :exports code let rec permutations (l : 'a list) : 'a list list = match l with | [] -> [[]] | h :: t -> List.concat_map (insertInto h) (permutations t) #+END_SRC #+RESULTS: : <fun> Let us test that "insertInto" has the correct behavior: #+BEGIN_SRC ocaml :exports both insertInto 6 [1 ; 2 ; 3] #+END_SRC #+RESULTS: | 6 | 1 | 2 | 3 | | 1 | 6 | 2 | 3 | | 1 | 2 | 6 | 3 | | 1 | 2 | 3 | 6 | Let us test that "permutations" has the correct behavior: #+BEGIN_SRC ocaml :exports both permutations [1 ; 2 ; 3 ; 4] #+END_SRC #+RESULTS: | 1 | 2 | 3 | 4 | | 2 | 1 | 3 | 4 | | 2 | 3 | 1 | 4 | | 2 | 3 | 4 | 1 | | 1 | 3 | 2 | 4 | | 3 | 1 | 2 | 4 | | 3 | 2 | 1 | 4 | | 3 | 2 | 4 | 1 | | 1 | 3 | 4 | 2 | | 3 | 1 | 4 | 2 | | 3 | 4 | 1 | 2 | | 3 | 4 | 2 | 1 | | 1 | 2 | 4 | 3 | | 2 | 1 | 4 | 3 | | 2 | 4 | 1 | 3 | | 2 | 4 | 3 | 1 | | 1 | 4 | 2 | 3 | | 4 | 1 | 2 | 3 | | 4 | 2 | 1 | 3 | | 4 | 2 | 3 | 1 | | 1 | 4 | 3 | 2 | | 4 | 1 | 3 | 2 | | 4 | 3 | 1 | 2 | | 4 | 3 | 2 | 1 | * 2006 Paper 1 Question 1 ** Question his question has been translated from Standard ML to OCaml Give an example of an OCaml function belonging to each of the following complexity classes: (a) O(1); (b) O(n); (c) O(n log n); (d ) O(n^2); (e) O(2^n). Each answer may contain code fragments (involving well-known functions) rather than self-contained programs, but must include justification. (The upper bound in each case should be reasonably tight.) ** Solution (a) The constant function is O(1) because it does no work. #+BEGIN_SRC ocaml let const x = 1 #+END_SRC (b) Adding one to each element of a list is O(n) because we must access each element of the list. #+BEGIN_SRC ocaml let addOne = List.map (fun x -> x + 1) #+END_SRC (c) Sorting a list using mergesort (This is what the Ocaml standard library uses, I looked in the documentation) is O(n ln n). The reason that mergesort is $O(n \log n)$ is that its work follows the recurrence relation $T(n) = 2T(n / 2) + M(n / 2 , n / 2)$, where $M(a , b) = a + b$. This means that $T(n) = O(n \log n)$. #+BEGIN_SRC ocaml let sort = List.sort #+END_SRC (d) These functions are from the lecture. "nsum" is $O(n)$ because for each of $n$ steps it does constant work. "nsumsum" is $O(n^2)$ because for each of $n$ steps it does linear work. #+BEGIN_SRC ocaml let nsum n = if n = 0 then 0 else n + nsum n - 1 let nsumsum n = if n = 0 then 0 else sum n + nsumsum n - 1 #+END_SRC (e) "slow" is $O(2^n)$ because its work satisfies the recurrence relation $T(n) = 1 + T(n-1) + T(n - 1)$. Let us assume our Ocaml implemenetation has no caching and no memoization. Solving this recurrence gives that $T(n) = O(2^n)$ #+BEGIN_SRC ocaml let rec slow n = if n < 0 then 1 else (slow n - 1) + (slow n - 1) #+END_SRC #+RESULTS: : <fun> * 2008 Paper 1 Question 1 ** Question The list l2 is a sublist of l provided there exist lists l1 and l3 such that l = l1@l2@l3. Write an OCaml function sublist to test whether one list is a sublist of another one. Include a clear explanation of how your code works ** Solution Since Ocaml is not as developed as Haskell, I had to define my own "take" and "drop" functions. #+BEGIN_SRC ocaml let rec drop n xs = match xs with | [] -> [] | h :: t -> if n = 0 then xs else drop (n - 1) t let rec take n xs = match xs with | [] -> [] | h :: t -> if n = 0 then [] else h :: take (n - 1) t #+END_SRC Using "take" and "drop", we can take out a "slice" from a list. #+BEGIN_SRC ocaml let slice list startIndex range = take range (drop startIndex list) #+END_SRC Here are some simple utility functions. "range" generates a list of numbers from 1 to n. "makeSlices" creates all slices of length b out of list a. #+BEGIN_SRC ocaml let range i = List.init i Fun.id let makeSlices a b = List.map (fun i -> slice a i (List.length b)) (range (List.length a - List.length b + 1)) #+END_SRC #+RESULTS: : <fun> And now we can define "isSublist", which checks if one list is a sublist of another list. #+BEGIN_SRC ocaml let isSublist a b = List.find_opt ((=) b) (makeSlices a b) #+END_SRC #+RESULTS: : <fun> #+BEGIN_SRC ocaml :exports both isSublist [1 ; 2 ; 3] [ 2 ; 3] #+END_SRC #+RESULTS: : Some [2, 3]