### Practice Problems (not for submission)

1. Understanding Mathematical Induction

• Find the flaw in the following proof:

Theorem:  All horses are of the same color.

Proof  Let there be n horses. We proceed by induction on n. If n=1, there is nothing to prove. So assume that n>1 and that the theorem holds for any group of n-1 horses. From the given n horses discard one, say the first one. Then all the remaining n-1 horses are of the same color by the induction hypothesis. Now put the first horse back and discard another, say the last one. Then the first n-1 horses have the same color again by the induction hypothesis. So all the n horses must have the same color as the ones that were not discarded either time. QED

• Consider the following puzzle given in pseudocode:
   Let n be an odd positive integer.
Initialize C to the collection of integers 1,2,...,2n.
while (C contains two or more elements) {
Randomly choose two elements from the collection, call them a and b.
Remove these elements from C.
Add the absolute difference |a-b| to C.
}


For every iteration of the loop, two elements are removed and one element is added, so the size of the collection reduces by 1. After 2n-1 iterations the collection contains a single integer, call it t, and the loop terminates. Prove that t is odd. (Hint: Try to locate a delicate loop invariant.)

You may want to write an Ocaml function to verify the claim.

• The following program claims to compute the number of trailing zeros in n ! For example 5! = 120 has one trailing 0. How will you prove it ?

let rec trailzero n = if n < 5 then 0 else (n/5) + trailzero (n/5) ;;


2. Write a function that given an integer n in base 10 , prints out the equivalent integer in base b (for an arbitrary natural number b.

3. Bertrand's postulate

Write a function to find out the number of primes between a given number n and 2n.

4. Extended Euclid

Given two positive integers m and n determine two integers i and j such that i.m + j.n = gcd (m,n) where gcd (m,n) is the greatest common divisor of m and n.

5. Bisection method

You are given an interval [a, a+b], where the value of a function f is initially positive (starting from a) and then it becomes negative for some a < c <= b, and remains negative, i.e. f(b) is negative. Write ocaml function that computes the first negative occurence in [a, a+b] using a halving method. Given an interval [ a, a+b], it computes the sign of f at the midpoint a + b/2 and if it is positive then it recursively searches the interval beginning at a +b/2 (since the sign change must occur in the interval to the right), else it searches the lower interval.

6. We want to multiply two non-negative integers m , n using the following algorithm. If n is an even number then we halve n and double m and compute their product otherwise we decrement n by 1 and add m to the product of m and n-1. Write an OCAML function Mult(m, n) to implement the above algorithm. () Write an OCAML function Mult(m, n) to implement the above algorithm

7. List programming

• Generating lists ----------------
. Write functions

ccinterval (m, n): int -> int list

which yields an empty list if m int list

which generates "open-open", "open-closed" and "closed-open" intervals
(m,n), (m,n] and [m, n) respectively. Under what conditions should each
of them generate empty lists?


• Getting information from lists.
Note that the "first" element of a list has position 0 and for a list of
length n > 0, the position of the last element is (n-1).

. Write the following functions.

length -- to compute the length of a list
last   -- to obtain the value of the last element of the list
middle -- to obtain the value of the middle element if the length is
is odd and otherwise the value of the last element in the
first half of the list.
nth    -- to obtain the nth element of a list
fst_p  -- to obtain the value of the first element which satisfies a
property p
lst_p  -- to obtain the value of the last element which satisfies a
property p
exst_p -- to determine whether there is any element which satisfies the
property p
fstpos -- to obtain the position of the first element that satisfies
a property p
lstpos -- to obtain the position of the last element that satisfies
a property p
nondes -- to determine whether each element is no greater
than the next element in the list
nonasc -- to determine whether each element is no smaller than the
next element.
sorted -- yields ~1 if the list is nondes, +1 if the list is nonasc
and 0 otherwise. Do not use the functions "nondes" and
"nonasc" to determine this. Program this function
independently since that is more efficient.

a) What is the type of the function in each case?
b) When (if necessary) should an exception be raised in each case?



• New lists from old
. Write the following functions (What is the type of each function?)

del_nth -- delete the nth element of a list
rep_nth -- replace the nth element by a another element
add_end -- add a new element to the end of the list
ins_nth -- insert a new element after the nth element of the list
del_p  	-- delete from the list all elements which satisfy a property p
oddpos  -- deletes all elements in even positions from a list
evenpos -- deletes all elements in odd positions from a list

a) What is the type of the function in each case?
b) When (iif necessary) should an exception be raised in each case?



• Functions with many lists
.  Write a function that returns a list of elements that
are smaller (less than or equal to) the first element of the input list.
The output list should not contain the first element.

. (Multiset to set )Write a program that given a list returns
exactly one instance
of any element in a given list.

. Write a function

partition: int * int list -> (int list * int list)

which for any integer m and int list L, yields two lists M and N
where M consists of elements of L that are smaller than m and N
consists of all the other elements in L (such that the order of
occurrence of elements in L is preserved in both M and N).

. Write function

interleave: int list * int list -> int list

which yields a new list N of length 2n (n >= 0) from given lists L
and M (each of length n) such that the element in the kth position
in L (for 0<=k < n) is in the 2kth position in N and the element in
the kth position in M is in the (2k+1)th position in N.

.Write a recursive function flatten that takes as input a list of
lists and returns a single list of all elements from the lists.
For example flat [[1;3]; [5]; []; [8;2;1]] should return
[ 1;3;5;8;2;1 ]



• More complex problems
. Write a function

merge : int list * int list -> int list

which takes two sorted lists L, M and yields a a new list N which is
sorted "nondes"

. The Sieve of Eratosthenes: You must have studied this method in your early
school mathematics to find the list of prime numbers.

Write  a function

sieve : int -> int list

which for any integer n >= 2 deletes all the composite numbers in the closed
interval [2,n]. A postiive integer n is composite iff it  has at least one
divsisor in the open-open interval (2, n).

. Write a function

primes_upto : int -> int list

which generates the list of all primes in the closed interval [2,n] from first
principles (do not use the "sieve" method)

. Consider the following two ocaml functions

let rec f1 lst = match lst with
[x]  ->  x |
a :: b -> let temp = f1 b in if a < temp then a else temp ;;

let rec f2 lst = match lst with
[x]  ->  x |
a :: b -> if a < f2 b then a else f2 b;;

For a list of length n, how many comparison
operations (as a function of n)
do f1 and f2 execute ? Provide justifications.

Write a  program that deletes a given element from
a list (if it exists). If there are multiple occurrences, only one
is removed.

Using the above function write a program that given
two lists l1 and l2, returns the difference l1 - l2,
i.e., the elements in l1 that do not belong to l2.

A point (x,y) is dominated by (x' , y') if x <= x' and y <= y'.
Given a set S of n points ( xi , yi), a point
p in S is maximal if it is not dominated by and other point in S.
For example among (3,4) (2,1) (4,0), (2,1) is not maximal. Assuming that the
input is given in reverse sorted order of the x coordinates, write a program
that produces all the maximal points.
Hint: By scanning the points in decreasing orders of x coordinates, a given
point is not maximal if any point to its right has a larger y coordinate.

• Higher order functions using lists


. Define your own list_map function that applies a given function f to
all the elements of the list and returns the mapped list.

. Many of the list functions follows a common structure. For the base
case we return a special value e, otherwise the list
can be viewed as hd::tail and we compute the function recursively on the
tail and returns a value that combines hd and the value returned by the
recursive call.
Define a function called list_iter that takes three parameters, e , a
combination function f and the list itself.

Try out this generic function to define

(i) list minimum

(ii) list reversal

.
let comp a b = function x -> a ( b x) ;;

let rec selfcomp f n = if n = 0 then (function x -> x) else
function x -> f ( selfcomp f (n-1) x) ;;

let rec fastselfcomp f n = if n =0 then (function x -> x ) else
if (n mod 2 = 0) then let half = (fastselfcomp f (n/2) )
in function x ->  half (half x)
else comp f (fastselfcomp f (n-1)) ;;

Compare the two functions for composing a function with itself -
selfcomp and fastselfcomp. Which one will you use and Why ?