CS51 & CSCI E-250 Mid-Term Examination

Spring 2013
This is a closed book, no-computer, no calculator, no smart-phone exam. Write your
answers in the provided books (or if you’re taking the exam with a proctor, use whatever
paper you brought with you.) Make sure to write your name on each bookthat you use
to record your answers. Good luck!

1. [40 points total, 5 points each] For each of the following OCaml expressions, explain
   what value we get when we evaluate the expression, or why the expression makes no
   sense. Be careful – some of these expressions may not type-check.
   1. let f = fun x y -> x + y in
let g = f 10 in
g 32
      Answer: 42
   2. let f = fun x y -> x + y in
f 42
      Answer: int->int= ; fun y = (42 + y)
   3. let rec reduce f u xs =
match xs with
| [] -> u
| h::t -> f h (reduce f u t) in
let a = [1 ; 2 ; 3 ; 4] in
reduce (fun a b -> a + 1) 0 a
      Answer: 2
   4. let f g = fun f -> fun x -> f (g x) in
let f = f (fun f -> 1+f) in
let f = f (fun f -> 42) in
f 3
      Answer: 42
   5. let rec f x y =
match y with
| [] -> x
| (a,b)::t -> (b,a) :: (f y t)
in
f [1;2;3] [4;5;6]
      Answer: Wrong Type, Our function pattern matches tuple lists while we pass in an int list.
   6. let rec reduce f u xs =
match xs with
| [] -> u
| h::t -> f h (reduce f u t) in
let g = reduce (fun a b -> a::b) in
g [1;2;3] [4;5;6]
      Answer: [4;5;6;1;2;3];
   7. let x = 0 in
let f = (fun _ -> x) in
let x = 42 in
f 42
      Answer: 0
   8. let fst p = let (x,_) = p in x in
let snd p = let (_,y) = p in y in
let vs = [(1,2) ; (3,4); (5,6)] in
(List.map snd vs, List.map fst vs)
      Answer: ([2;4;6], [1;3;5]);
2. [24 points total, 6 points each] Recall Ke$ha's favorite function:
   let rec reduce f u xs =
match xs with
| [] -> u
| h::t -> f h (reduce f u t)
   For each of the following function definitions, rewrite the definition using reduce and
   without any other recursive function. Keep your definitions as simple, clean, and
   elegant as possible.
   1. let rec sum xs =
match xs with
| [] -> 0
| h::t -> h + (sum t)
      Answer: let sum = reduce (+) 0
   2. let rec map f xs =
match xs with
| [] -> []
| h::t -> (f h)::(map f t)
      Answer: let map f = reduce (fun x y = f x :: y)  []
   3. let rec foo p xs =
match xs with
| [] -> []
| h::t -> if p h then foo p t else h::(foo p t)
      Answer: let foo p = reduce (fun x y = if p x then y else x::y) []
   4. let rec split xs =
match xs with
| [] -> ([],[])
| h::t -> let (a,b) = split t in (b, h::a)
      Answer: let split = reduce (fun x (a,b) = (b, x::a)) ([],[])
3. [21 points total] Consider the following definitions:
   type set = Empty | Single of int | Union of set * set
let union (s1:set) (s2:set) : set = Union (s1, s2)
let rec member (x:int) (s:set) : bool =
match s with
| Empty -> false
| Single y -> x = y
| Union (s1, s2) -> member x s1 || member x s2
let rec intersect (s1:set) (s2:set) : set =
match s1 with
| Empty -> Empty
| Single x -> if member x s2 then s1 else Empty
| Union (t1, t2) -> union (intersect t1 s1) (intersect t2 s2)
   1. a. [5 points] What advantage does this representation of sets have over simply using
      lists of integers?
      Answer: The advantage of using this representation of sets is that our union functions run in constant time, as opposed to the linear time we would have if we were working with lists.
   2. b. [4 points] Write recurrence equations that describe the running time of member as
      a function of the number of nodes (i.e., Empty, Single, or Union constructors) in
      the representation of set s.
      Answer:

       as a function of the number of nodes

      T_member(1) = C;

      T_member(n) = C + T_member(n') + T_member(n-n') where n is odd
   3. c. [4 points] Simplify the recurrence equations to come up with a big-O worst case
      running time for member as a function of the number of nodes in the set s.
      Answer: T_member(n)=n
   4. d. [4 points] Write recurrence equations that describe the running time of
      intersect as a function of the number of nodes in the sets s1 and s2.
      Answer: 

      T_interesect(1, s2)=T_member(s2); 

      T_interesect(s1, s2) = Tinteresect(s1', s2) + T_instersect(s1-s1', s2) where n is greater than 0
   5. e. [4 points] Assuming that we intersect two sets with roughly the same number of
      nodes n, what is the big-O worst case running time as a function of n?
      Answer:

      Roughly the same number of nodes n. So it's basically the answer above but s1 ≈ s2 ?

      Tinteresect(1, s2)=Tmember(s2); 

      T_intersect(n, n') = T_intersect(m,n') + T_intersect(n-m, n') where n' is ≈ n and n is greater than 0;

      T_intersect(n, n') =  T_member(n')+Tmember(n')+Tmember(n')... + Tintersect(n-m, n')

      so we are basically checking for collisions on a square which is 

      T_intersect(n, n) = T_intersect(n²)

      Tintersect(n, n') ≈ Tintersect(n²) ???
4. [15 points total, 3 points each] Respond with true or false to each question.

    

   1. a. If function f runs in time O(n) and function g runs in time O(n²), then for a big
      enough value of n, we can expect that g runs faster than f.
      Answer: false
   2. b. The following definitions are equivalent:
      let f x y z = x*y-z ;;
let f x = fun y -> fun z -> x*y-z ;;
      Answer: true
   3. c. The following function is tail-recursive:
      let rec map f xs =
match xs with
| [] -> []
| h::t -> (f h)::(map f t)
      Answer: false
   4. d. The most general type of map is:
      (int -> int) -> int list -> int list
      Answer: false
   5. e. Using modules to build and enforce abstract data types means that we don't
      need to test whether clients are respecting our representation invariants.
      Answer: true