Homework 1 COSE212, Fall 2020
Hakjoo Oh
Due: 9/30, 24:00
Academic Integrity / Assignment Policy
• All assignments must be your own work.
• Discussion with fellow students is encouraged including how to approach
the problem. However, your code must be your own.
– Discussion must be limited to general discussion and must not involve details of how to write code.
– You must write your code by yourself and must not look at someone else’s code (including ones on the web).
– Do not allow other students to copy your code.
– Do not post your code on the public web.
• Violating above rules gets you 0 points for the entire HW score.
Problem 1 The Fibonacci numbers can be defined as follows:
0 fib(n) = 1
fib(n−1)+fib(n−2) Write in OCaml the function
fib: int -> int
if n = 0 if n = 1 otherwise
that computes the Fibonacci numbers.
Problem 2 Consider the following triangle (it is called Pascal’s triangle):
1
11 121 1331 14641 ···
1
where the numbers at the edge of the triangle are all 1, and each number inside the triangle is the sum of the two numbers above it. Write a function
pascal: int * int -> int
that computes elements of Pascal’s triangle. For example, pascal should behave
as follows:
pascal (0,0) = 1
pascal (1,0) = 1
pascal (1,1) = 1
pascal (2,1) = 2
pascal (4,2) = 6
Problem 3 Write a function
prime: int -> bool
that checks whether a number is prime (n is prime if and only if n is its own smallest divisor except for 1). For example,
prime 2 = true
prime 3 = true
prime 4 = false
prime 17 = true
Problem 4 Write a function
dfact : int -> int
that computes double-factorials. Given a non-negative integer n, its double- factorial, denoted n!!, is the product of all the integers of the same parity as n from 1 to n. That is, when n is even
n/2
n!!= (2k)=n·(n−2)·(n−4)···4·2
k=1
and when n is odd,
n!!= (2k−1)=n·(n−2)·(n−4)···3·1
k=1
For example, 7!! = 1 × 3 × 5 × 7 = 105 and 6!! = 2 ∗ 4 ∗ 6 = 48.
Problem 5 Consider the task of computing the exponential of a given number. We would like to write a function that takes as arguments a base b and a positive integer exponent n to compute bn. Read the remaining problem description carefully and devise an algorithm that has time complexity of Θ(log n).
One simple way to implement the function is via the following recursive
definition:
b0 = 1
bn = b·bn−1
which translates into the OCaml code: 2
(n+1)/2
let rec expt b n =
if n = 0 then 1
else b * (expt b (n-1))
However, this algorithm is slow; it takes Θ(n) steps.
We can improve the algorithm by using successive squaring. For instance,
rather than computing b8 as b·(b·(b·(b·(b·(b·(b·b))))))
we can compute it using three multiplications as follows:
b2 = b·b b4 = b2·b2 b8 = b4·b4
This method works only for exponents that are powers of 2. We can generalize the idea via the following recursive rules:
bn = (bn/2)2 if n is even bn = b·bn−1 if n is odd
Use the rules to write a function fastexpt that computes exponentials in Θ(log n) steps:
fastexpt: int -> int -> int Problem 6 Define the function binarize:
binarize: int -> int list
that converts a decimal number to its binary representation. For example,
binarize 2 = [1; 0]
binarize 3 = [1; 1]
binarize 8 = [1; 0; 0; 0]
binarize 17 = [1; 0; 0; 0; 1]
Problem 7 Define the function iter:
iter : int * (int -> int) -> (int -> int)
such that
iter(n, f ) = f ◦ · · · ◦ f .
n
When n = 0, iter(n,f) is defined to be the identity function. When n > 0, iter(n,f) is the function that applies f repeatedly n times. For instance,
evaluates to 2 × n.
iter(n, fun x -> 2+x) 0
3
Problem 8 Natural numbers are defined inductively: n
0 n+1
In OCaml, the inductive definition can be defined by the following a data type:
type nat = ZERO | SUCC of nat
For instance, SUCC ZERO denotes 1 and SUCC (SUCC ZERO) denotes 2. Write two
functions that add and multiply natural numbers:
natadd : nat -> nat -> nat
natmul : nat -> nat -> nat
For example,
# let two = SUCC (SUCC ZERO);;
val two : nat = SUCC (SUCC ZERO)
# let three = SUCC (SUCC (SUCC ZERO));;
val three : nat = SUCC (SUCC (SUCC ZERO))
# natmul two three;;
– : nat = SUCC (SUCC (SUCC (SUCC (SUCC (SUCC ZERO)))))
# natadd two three;;
– : nat = SUCC (SUCC (SUCC (SUCC (SUCC ZERO))))
Problem 9 Binary trees can be defined as follows:
type btree =
Empty
|Node of int * btree * btree
For example, the following t1 and t2
let t1 = Node (1, Empty, Empty)
let t2 = Node (1, Node (2, Empty, Empty), Node (3, Empty, Empty))
are binary trees. Write the function
mem: int -> btree -> bool
that checks whether a given integer is in the tree or not. For example,
evaluates to true, and evaluates to false.
mem 1 t1
mem 4 t2
4
Problem 10 Consider the following propositional formula:
Write the function
type formula =
| True
| False
| Not of formula
| AndAlso of formula * formula
| OrElse of formula * formula
| Imply of formula * formula
| Equal of exp * exp
and exp =
| Num of int
| Plus of exp * exp
| Minus of exp * exp
eval : formula -> bool
that computes the truth value of a given formula. For example,
eval (Imply (Imply (True,False), True))
evaluates to true, and
eval (Equal (Num 1, Plus (Num 1, Num 2)))
evaluates to false.
Problem 11 Write two functions
max: int list -> int
min: int list -> int
that find maximum and minimum elements of a given list, respectively. For example max [1;3;5;2] should evaluate to 5 and min [1;3;2] should be 1.
Problem 12 Write a higher-order function
drop : (’a -> bool) -> ’a list -> ’a list
which removes elements of a list while they satisfy a predicate. For example,
drop (fun x -> x mod 2 = 1) [1;3;5;6;7] evaluates to [6;7] and
evaluates to [1;3;7].
drop (fun x-> x > 5) [1;3;7]
5