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 ?