in Books, Concrete Abstractions, Doing Books

Concrete Abstractions: Chapter 4

Exercise 4.2 In this exercise you will show that this version of mod-expt does \Theta (e) multiplications, as we claimed.
a. Use induction to prove each of the following about this latest version of mod-expt:
(1) e is a nonnegative integer, (mod-expt b e m) does at least e multiplications.
(2) When e is a positive integer, (mod-expt b e m) does at most 2e – 1 multiplications.

Solution: At first I wrote the function mathematically. mod^* = m^*(x, y) = xy \text{ mod } m.
\text{mod-expt} = m(b, e, m)
m(b, 0, m) = 1
m(b, e, m) = \begin{cases} m^*(m(b, e/2, m), m(b, e/2, m) & \text{ if e is even}\\ m^*(m(b, e-1, m), b) & \text{ if e is odd }\\ \end{cases}

(1) Ok, now let’s start with the first assumption: m(b, e, m) does at least e multiplications. For e=0 follows that m(b, 0, m) = 1. So that’s true. Therefore we can assume that this holds to e+1.
If e+1 is odd:
m(b, e+1, m) = m^*(m(b, e, m), b), we assumed that m(b, e, m) does e multiplications. If we look back at the definition of m^*(x,y), we can see that there’s one multiplication. Therefore there are e + 1 multiplications. That was the best case, let’s look at the worst one.

(2) The assumption is that m(b, e, m) needs 2e-1 multiplications at most. Let’s check the base case for e=1. m(b, 1, m) = m^*(m(b, 0, m), b). Here we get one multiplication from m^*, so the maximum limit holds. If e+1 is even, it follows that:
m(b, e+1, m) = m^*(m(b, (e+1)/2, m), m(b, (e+1)/2, m)). Each nested m(b, (e+1)/2, m) needs at most 2* \frac{(e+1)}{2} -1 multiplications and we got another from m^*. That is, there are 2 * (2*\frac{(e+1)}{2} -1) + 1 = 2(e+1) - 1 multiplications.

You can check the even case in (1) and the odd case in (2) for yourself and see that these are bigger and respectively smaller than the other ones.

Exercise 4.11 Consider the following procedures:

(define factorial
  (lambda (n)
    (if (= n 0)
      1
      (* n (factorial (- n 1))))))

(define factorial-sum1 ; returns 1! + 2! + … + n!
  (lambda (n)
    (if (= n 0)
      0
      (+ (factorial n)
          (factorial-sum1 (- n 1))))))

(define factorial-sum2 ; also returns 1! + 2! + … + n!
  (lambda (n)
    (define loop
      (lambda (k fact-k addend)
       (if (> k n)
         addend
         (loop (+ k 1)
               (* fact-k (+ k 1))
               (+ addend fact-k)))))
     (loop 1 1 0)))

In answering the following, assume that n is a nonnegative integer. Also, justify your answers.
a. Give a formula for how many multiplications the procedure factorial does as a function of its argument n.
b. Give a formula for how many multiplications the procedure factorial-sum1 does (implicitly through factorial) as a function of its argument n.
c. Give a formula for how many multiplications the procedure factorial-sum2 does as a function of its argument n.

Solution:
a. \text{factorial}(0) = 1, \text{factorial}(n) = n * \text{factorial}(n-1)
What happens for n = 1, 2, 3,..? Let’s see:
\text{factorial}(1) = 1 * \text{factorial}(0) = 1 * 1
\text{factorial}(2) = 2 * \text{factorial}(1) = 2 * 1 * \text{factorial}(0) = 2 * 1 * 1
\text{factorial}(3) = 3 * \text{factorial}(2) = 3 * 2 * \text{factorial}(1)
= 3 * 2 * 1 * \text{factorial}(0) = 3 * 2 * 1 * 1
We can see that there are probably n+1 multiplications. We can prove that by induction.
\text{factorial}(n+1) = (n+1) * \text{factorial}(n). We assumed that \text{factorial}(n) multiplies (n+1) times. Therefore we have 1 + (n+1) = (n+1) + 1 multiplications.
b. And again written mathematically:
\text{factorial-sum1}(0) = 0
\text{factorial-sum1}(n) = \text{factorial}(n) + \text{factorial-sum1}(n-1)
So was happens here here for n = 1, 2, ..?
\text{factorial-sum1}(1) = \text{factorial}(1) + \text{factorial-sum1}(0)
= (1 * 1) + 0
\text{factorial-sum1}(2) = \text{factorial}(2) + \text{factorial-sum1}(1)
= (2 * 1 * 1) + \text{factorial}(1) + \text{factorial-sum1}(0)
= (2 * 1 * 1) + (1 * 1) + 0
For n=1 we need 2 multiplications, for n=2 we need 2 + 3 multiplications. In general we need \sum_{i=1}^n (i+1) multiplications. This can be simplified: \sum_{i=1}^n i + sum_{i=1}^n 1 = \frac{n(n+1)}{2} + n = \frac{n^2 + 3n}{2}.
c. This is pretty straight forward. You can see that each iteration k is increased by one. It starts at k = 1 and stops if k > n. So it runs n times.

Exercise 4.12 How many ways are there to factor n into two or more numbers (each of which must be no smaller than 2)? We could generalize this to the problem of finding how many ways there are to factor n into two or more numbers, each of which is no smaller than m. That is, we write

(define ways-to-factor
  (lambda (n)
   (ways-to-factor-using-no-smaller-than n 2)))

Your job is to write ways-to-factor-using-no-smaller-than.

Solution: An easy way to find factors is just to try every number if it divides n, starting with m. If a number divides n, take the division and find its factors.

(define ways-to-factor-using-no-smaller-than
  (lambda (n m)
    (define factor
      (lambda (x y)
        (if (> y (sqrt x))
          0
         (if (= (remainder x y) 0)
           (+ 1 (factor (/ x y) m))
            (factor x (+ y 1))))))
     (+ 1 (factor n m))))

Exercise 4.13 Consider the following procedure:

(define bar
  (lambda (n)
    (cond ((= n 0) 5)
          ((= n 1) 7)
          (else (* n (bar (- n 2)))))))

How many multiplications (expressed in \Theta notation) will the computation of (bar n) do? Justify your answer. You may assume that n is a nonnegative integer.

Solution: The definition of bar is:
\text{bar}(0) = 5
\text{bar}(1) = 7
\text{bar}(n) = n*\text{n-2}
For n = 0, 1, 2, 3, ... we get:
\text{bar}(0) = 5 \text{ | (0 multiplications)}
\text{bar}(1) = 7 \text{ | (0 multiplications)}
\text{bar}(2) = 2 * \text{bar}(0) = 2 * 5 \text{ | (1 multiplications)}
\text{bar}(3) = 3 * \text{bar}(1) = 3 * 7 \text{ | (1 multiplications)}
\text{bar}(4) = 4 * \text{bar}(2) = 4 * 2 * 5 \text{ | (2 multiplications)}
\text{bar}(5) = 5 * \text{bar}(3) = 5 * 3 * 7 \text{ | (2 multiplications)}
You can see that there are between \frac{n-1}{2} and \frac{n}{2} multiplications. Therefore there are \Theta(n) multiplications at general.

Exercise 4.14 Consider the following procedures:

(define foo
  (lambda (n) ; computes n! + (n!)^n
     (+ (factorial n) ; that is, (n! plus n! to the nth power)
        (bar n n))))

(define bar
  (lambda (i j) ; computes (i!)^j (i! to the jth power)
    (if (= j 0)
       1
       (* (factorial i)
  (bar i (- j 1))))))

(define factorial
  (lambda (n)
    (if (= n 0)
      1
      (* n (factorial (- n 1))))))

How many multiplications (expressed in \Theta notation) will the computation of (foo n) do? Justify your answer.

Solution: It’s basically the same schema as the other exercises. If we look at foo it looks like this:
\text{foo}(n) = \text{fac}(n) + \text{bar}(n, n) We already know that \text{fac}(n) needs (n+1) multiplications. If we look at bar, we can see how it works.
\text{bar}(i,j) = \text{fac}(i) * \text{bar}(i,j-1) we can simplify this because foo which calls bar only uses the argument n.
\text{bar}(n,n) = \text{fac}(n) * \text{bar}(n,n-1). Because we already know how many multiplications fac needs, we can concentrate on bar. Let’s see what it does for n = 1, 2, 3, ...:
\text{bar}(0, 0) = 1 \text{ | 0 multipl. }
\text{bar}(1, 1) = \text{fac}(1) * \text{bar}(0, 0) text { | 2 + 1 + 0 multipl.}
\text{bar}(2, 2) = \text{fac}(2) * \text{bar}(1, 1) \text { | 3 + 1 + (2 + 1) multipl.}
We can generalize this as \sum_{k=3}^{n+2} k = \sum_{k=1}^{n+2} - 3 which can be simplified as: \frac{(n+2)(n+3)}{2} - 3 = \frac{(n+2)(n+3) - 6}{2} = \frac{n^2 + 5n}{2} therefore we have \Theta(n^2) multiplications.

Exercise 4.17 Consider the following enumeration problem: How many ways can you choose k objects from n distinct objects, assuming of course that 0 \leq k \leq n? For example, how many different three-topping pizzas can be made if you have six toppings to choose from?
The number that is the answer to the problem is commonly written as C(n, k). Here is an algorithm for computing C(n, k): […]
Using this algorithm, write a tree-recursive procedure that calculates the numbers C(n, k) described above.

Solution:

(define C
  (lambda (n k)
    (if (or (= k 0) (= k n))
      1
      (+ (C (- n 1) (- k 1))
         (C (- n 1) k)))))

Exercise 4.18 One way to sum the integers from a up to b is to divide the interval in half, recursively sum the two halves, and then add the two sums together. Of course, it may not be possible to divide the interval exactly in half if there are an odd number of integers in the interval. In this case, the interval can be divided as nearly in half as possible.
a. Write a procedure implementing this idea.
b. Let’s use n as a name for the number of integers in the range from a up to b. What is the order of growth (in \Theta notation) of the number of additions your procedure does, as a function of n? Justify your answer.

Solution: a.

(define sum-integers
  (lambda (a b)
     (+ a (divide-to-sum a b))))

(define divide-to-sum
  (lambda (a b)
    (let ((interval (- b a)))
      (if (< interval 2)
       b
       (if (even? interval)
         (+ (divide-to-sum a (+ a (/ interval 2)))
         (divide-to-sum (+ a (/ interval 2)) b))
       (+ (divide-to-sum a (+ a (/ (+ interval 1) 2)))
           (divide-to-sum (+ a (/ (+ interval 1) 2)) b)))))))

b. It’s basically the same as in mod-expt because both split up the calculation in two branches each time. Therefore it needs \Theta(\text{log } n) additions.

Write a Comment

Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.