Assignment 2 (due date Jan 17)

Develop ML functions for the following problems.

  • Computing factorial of a given integer using both recursive and iterative procedures. For some inputs (from the domain of Integers) the computation may not terminate. Identify such inputs and provide reason for this non-termination.
  • Computing $x^n$. Write both recursive and iterative versions.
  • Computing the $n^{th}$ fibonacci number. First use the algorithm given by the following functional description: $fib(1) = 1; fib(2) = 1; fib(n) = fib(n-1)+fib(n-2)$ for $n > 2$. Also develop iterative algorithms for the same problem.
  • The integer square root of $n$ is the integer $k$ such that $k^2 \leq n < (k+1)^2$. The integer square root can be computed using the following inductive process:
    • Compute the integer square root $i$ of $m = n ,\mbox{div}, 4$ recursively. We then have that $i^2 \leq m < (i+1)^2$.
    • Since $m$ and $i$ are integers we have that $(m+1) <= (i+1)^2$. We thus have $(2i)^2 \leq 4m \leq n < 4m + 4 \leq (2i + 2)^2$. Hence we have that the integer square root of $n$ is either $2i$ or $2i+1$.
    • Write a recursive ML program corresponding to the above algorithm. Indicate the type of the function and derive the number of steps required.
  • Study the problem of computing perfect numbers from the the Lecture notes Example 3.13 and implement the ML program. Also study the following discussion on scope rules. You will be questioned on this problem during the demonstration.