Foundations of Computer Science 1

focs • supervision

A special thanks to Dima Szamozvancev for building a set of questions for the FoCS course. Questions from Dima (or inspired by) are marked with an asterisk (*).

Introduction

Concepts

1. Within the context of OCaml, give an example of a value, an expression and something with an "effect" ?

2. (*) Which of these is a valid OCaml expression and why? Assume that you have a variable x declared, e.g. with let x = 1.

• if x < 6 then x + 3 else x + 8
• if x < 6 then x + 3
• if x < 6 then x + 3 else "A"
• x + (if x < 6 then 3 else 8)

Recursion

Concepts

1. In your own words, briefly describe what a call stack is? Why is it important in terms of recursive functions?

2. Here are the types for three OCaml functions, give them plausible names and explain your reasoning.

val x : string -> string -> bool
val y : float -> int
val z : 'a list -> 'a

3. Pretend you are the OCaml type checker, what kind of error message would you give to the following expression? (Random.int x returns a random integer between [0, x) )

if Random.int 10 < 5 then "Less than 5" else 5

4. Use a recurrence relation to find an upper bound for the recurrence given by T (1) = 1 and T (n) = 2T (n/2) + 1. You should be able to find a tighter bound than O(n log n). Prove that your solution is an upper bound for all n using mathematical induction.

Problems

1. Write a recursive function that when given a height (of type int) prints a pyramid of that height. It can print any character you like (e.g. '*'). pyramid 3 should print something like:

  *
 ***
*****

You might find the String.make function useful which takes a length and a character and makes a string of that length.

# String.make 5 '+';;
- : string = "+++++"
# "Hello " ^ "World!";;
- : string = "Hello World!"
# print_endline "Taylor Swift";;
Taylor Swift
- : unit = ()

Have a go on paper first, but feel free to try it on the computer after.

2. How easily can you change your answer to (1) to print the pyramid upside-down? If you manage, briefly explain why your change works.

Lists

Concepts

1. Briefly describe what :: and @ mean as they relate to lists in OCaml ?

2. The following code tries to find all the numbers in a list less than some specified argument. It's correct, but could be improved?

let rec find_less_than i = function
  | [] -> []
  | x :: xs when x < i -> [ x ] @ find_less_than i xs
  | _ :: xs -> find_less_than i xs

And for example we can filter a list of elements greater than or equal to 3.

# find_less_than 3 [ 5; 4; 3; 2; 1 ];;
- : int list = [2; 1]

3. (*) We’ve seen how tail-recursion can make some list-processing operations more efficient. Does that mean that we should write all functions on lists in tail-recursive style?

Problems

This section is quite code-heavy, I would recommend jotting down outlines for solutions on paper first to practice for the exams. But then do try it out on a computer. Also feel free to do 2/3 of these questions as they're all a little similar.

1. (*) Code a function to return the last element of a non-empty list. How efficiently can this be done? See if you can come up with two different solutions.

2. (*) Code a function tails that returns all of the tails of its arguments. For example, given the list [1; 2; 3] it should give [[1; 2; 3]; [2; 3]; [3]; []].

3. Code a function partition that takes a list and a number n and partitions the list into groups of up to n elements (except the last group). For example, partition [1; 2; 3; 4; 5] 2 should return [[ 1; 2 ]; [ 3; 4 ]; [ 5 ]].

Optional

1. Sometimes your code has to check if a list is empty. There's a few ways we might go about this in OCaml. Briefly describe the differences between the two methods (List.length vs. the is_empty function). Which one do you think is more efficient? Hint: it might be interesting to read about how values are represented in memory in OCaml.

# let non_empty_list = [ 1; 2; 3 ]
val non_empty_list : int list = [1; 2; 3]
# List.length non_empty_list = 0;;
- : bool = false
# let is_empty = function
  | [] -> true
  | _  -> false;;
val is_empty : 'a list -> bool = <fun>
# is_empty non_empty_list;;
- : bool = false