next up previous
Next: How to Run the Up: MP1 CS603 Organization of Previous: Purpose

Problem Description

Do Exercises 1-4 on page 18 of the textbook. These four exercises define some number-theoretic functions for you to program. Try to use recursion; it will be good practice for when we cover LISP.
  1. (sigma m n ) $= m + (m+1)+\ldots+n$

  2. (exp m n) $= m^{n}(m,n \ge 0)$. (log m n) = the least integer $l$ such that $m^{l+1}>n(m>1,n>0)$.

  3. (choose n k) is the number of ways of selecting $k$ items from a collection of $n$ items, without repetitions, $n$ and $k$ nonnegative integers. This quantity is called a binomial coefficient, and is notated $n\choose k$. It can be defined as $n!\over k!(n-k)!$, but the following identities are more useful computationally: ${n\choose 0} = 1
(n\ge0), {n\choose n} = 1 (n\ge0)$, and ${n\choose k} =
{{n-1}\choose k} + {{n-1} \choose {k-1}}(n,k>0)$.

  4. (fib $m$) is the $m$th Fibonacci number. The Fibonacci numbers are defined by the identities:
    (fib $0$)$= 0$, (fib $1$)$=1$, and for $m>1$, (fib $m$)$=$(fib $m-1$)$+$ (fib $m-2$).