Concrete Abstractions: Chapter 5

Exercise 5.6 Write a general purpose procedure, that when given two integers, low and high, and a procedure for computing a function f , will compute f(text{low}) + f(text{low} + 1) + f (text{low} + 2) + ... + f (text{high}). Show how it can be used to sum the squares of the integers from 5 to 10 and to sum the square roots of the integers from 10 to 100.

Solution: I wrote a iterative version of it because you have to directly apply the function to each number, i.e. it isn’t commutative.

(define add-integers 
  (lambda (f low high)
    (add-integers-iter f low high 0)))

(define add-integers-iter
  (lambda (f low high end)
    (if (= low high)
        (+ end (f low))
        (add-integers-iter f (+ low 1) high (+ end (f low))))))

; sum of squares from 5 to 10
(add-integers (lambda (x) (* x x)) 5 10)

; sum of square roots from 10 to 100
(add-integers (lambda (x) (sqrt x)) 10 100)

Exercise 5.11 Write a procedure make-verifier, which takes f and m as its two arguments and returns a procedure capable of checking a number. The argument f is itself a procedure, of course. Here is a particularly simple example of a verifier being made and used:

(define check-isbn (make-verifier * 11)) (check-isbn 0262010771)

The value #t is the “true” value; it indicates that the number is a valid ISBN.
As we just saw, for ISBN numbers the divisor is 11 and the function is simply f(i, d_i ) = i * di. Other kinds of numbers use slightly more complicated functions, but you will still be able to use make-verifier to make a verifier much more easily than if you had to start from scratch.

Solution:

(define make-verifier
  (lambda (f m)
    (lambda (n)
      (if (= (remainder 
              (map-f f n) 
              m) 0)
          #t
          #f))))


(define map-f
  (lambda (f n)
    (map-digit-f f n 0 1)))
     
(define map-digit-f
  (lambda (f n end i)
    (if (= n 0)
        end
        (map-digit-f f
                     (quotient n 10)
                     (+ end (f i (remainder n 10)))
                     (+ i 1)))))
    

Exercise 5.12 For UPC codes (the barcodes on grocery items), the divisor is 10, and the function f (i, d_i ) is equal to d_i itself when i is odd, but to 3d_i when i is even. Build a verifier for UPC codes using make-verifier, and test it on some of your groceries. (The UPC number consists of all the digits: the one to the left of the bars, the ones underneath the bars, and the one on the right.) Try making some mistakes, like switching or changing digits. Does your verifier catch them?

Solution: Yeah, the mistakes were caught. By the way you can see here how powerful high-order functions are.

(define UPC-f
  (lambda (i di)
    (if (odd? i)
        di
        (* 3 di))))

(define UPC-verifier
  (make-verifier UPC-f 10))

Exercise 5.13 Credit card numbers also use a divisor of 10 and also use a function that yields d_i itself when i is odd. However, when i is even, the function is a bit fancier: It is 2d_i if $latex d_i < 5$, and $latex 2d_i + 1$ if $latex d_i geq 5.$ Build a verifier for credit card numbers. In the dialog at the beginning of this section, did the order taker really mistype the number, or did the customer read it incorrectly? Solution: The credit card number was correct.

(define CC-f
  (lambda (i di)
    (if (odd? i)
        di
        (if (< di 5)
            (* 2 di)
            (+ (* 2 di) 1)))))

(define CC-verifier
  (make-verifier CC-f 10))

Exercise 5.13 The serial number on U.S. postal money orders is self-verifying with a divisor of 9 and a very simple function: f (i, d_i ) = di, with only one exception, namely, f (1, d_1 ) = -d_1. Build a verifier for these numbers, and find out which of these two money orders is mistyped: 48077469777 or 48077462766.
Actually, both of those money order numbers were mistyped. In one case the error was that a 0 was replaced by a 7, and in the other case two digits were reversed. Can you figure out which kind of error got caught and which didn’t? Does this help explain why the other kinds of numbers use fancier functions?

Solution: The reversal of digits, if the digit isn't the first one, isn't caught by this verification function. This is a reason for using fancier verification functions.

(define USPostal-f
  (lambda (i di)
    (if (= i 1)
        (- di)
        di)))

(define USPostal-verifier
  (make-verifier USPostal-f 9))

Exercise 5.17 Suppose you have a function and you want to find at what integer point in a given range it has the smallest value. For example, looking at the following graph of the function f (x) = x^2 - 2x, you can see that in the range from 0 to 4, this function has the smallest value at 1. We could write a procedure for answering questions like this; it could be used as follows for this example:

(integer-in-range-where-smallest (lambda (x) (- (* x x) (* 2 x)))
0 4)
1

Here is the procedure that does this; fill in the two blanks to complete it:

(define integer-in-range-where-smallest 
  (lambda (f a b)
    (if (= a b) 
        a
        (let ((smallest-place-after-a _________________________))
               (if __________________
                a 
                smallest-place-after-a)))))

Solution: I find it actually pretty hard to do fill in questions. Anyhow, here's the solution:

(define integer-in-range-where-smallest 
  (lambda (f a b)
    (if (= a b) 
        a
        (let ((smallest-place-after-a (integer-in-range-where-smallest f (+ a 1) b)))
               (if (< (f a) (f smallest-place-after-a))
                a 
                smallest-place-after-a)))))

Exercise 5.18 Consider the following definitions:

    (define make-scaled 
     (lambda (scale f)
      (lambda (x) 
       (* scale (f x)))))

    (define add-one 
     (lambda (x) 
      (+ 1 x)))
    (define mystery 
     (make-scaled 3 add-one))

For the following questions, be sure to indicate how you arrived at your answer:
a. What is the value of (mystery 4)?
b. What is the value of the procedural call ((make-scaled 2 (make-scaled 3 add-one)) 4)?

Solution: a. You can see that mystery gets a function from (make-scaled 3 add-one). This produces (lambda(x) (* 3 (add-one x))) which equals (lambda(x) (* 3 (+ 1 x))). Therefore the value is 15.
b. Let's take this call apart. (make-scaled 2 f) produces (lambda(x) (* 2 (f x)). Here f is (make-scaled 3 add-one) which produces the known (lambda(x) (* 3 (+ 1 x))) = 15 for x = 4. If you substitute this into (make-scaled 2 f) it becomes (lambda (x) (* 2 15)) = 30.

Exercise 5.20 Suppose the following have been defined:

    (define f 
     (lambda (m b)
      (lambda (x) (+ (* m x) b)))) 

    (define g (f 3 2))

For each of the following expressions, indicate whether an error would be signaled, the value would be a procedure, or the value would be a number. If an error is signaled, explain briefly the nature of the error. If the value is a procedure, specify how many arguments the procedure expects. If the value is a number, specify which number.
a. f
b. g
c. (* (f 3 2) 7)
d. (g 6)
e. (f 6)
f. ((f 4 7) 5)

Solution:
a. f is a procedure with two arguments.
b. g is a procedure returned by f with one argument.
c. (* (f 3 2) 7) evals to (* (lambda (x) (+ (* 3 x) 2) 7) = (* 23) which throws an error because * needs at least two arguments.
d. Here we got another value: (g 6) = ((f 3 2) 6) = (+ (* 3 6) 2) which equals 20.
e. f needs two arguments. So this throws an error.
f. (+ (* 4 5) 7) which equals 27.

Exercise 5.24 Consider the following procedure:

(define positive-integer-upto-where-smallest 
 (lambda (n f) ; return an integer i such that
  ; 1 <= i <= n and for all integers j
  ; in that same range, f(i) <= f(j) 
  (define loop
   (lambda (where-smallest-so-far next-to-try)
    (if (> next-to-try n)
     where-smallest-so-far
     (loop (if (< (f next-to-try)
                (f where-smallest-so-far))
            next-to-try
            where-smallest-so-far)
      (+ next-to-try 1)))))
  (loop 1 2)))

a. Write a mathematical formula involving n that tells how many times this procedure uses the procedure it is given as its second argument. Justify your answer.
b. Give a simple Theta order of growth for the quantity you determined in part a. Justify your answer.
c. Suppose you were to rewrite this procedure to make it more efficient. What (in terms of n) is the minimum number of times it can invoke f and still always determine the correct answer? Justify your answer. (You are not being asked to actually rewrite the procedure.)

Solution: a. If next > n then loop returns directly smallest-so-far, so there's no call of f. If next <= n then there are two calls in the if header. Therefore there are 2(n-1) function calls of f.
b. We can see that 2(n-1) = 2n - 2. 2n is the biggest term and 2 is just a factor, therefore \Theta(n).
c. We can save (f where-smallest-so-far) by adding it in the parameter list of loop. In the ideal case we just need to calculate (f where-smallest-so-far) one time and (f next-to-try) (n - 1) times. However, in the worst case there's no improvement.

SPOJ: 8060. Cookies Piles

The kids in my son’s kindergarten made Christmas cookies with their teacher, and piled them up in columns. They then arranged the columns so that the tops of the columns, going from shortest to tallest, were in a nice straight ramp. The cookies were all of uniform size. Given that there were A cookies in the shortest pile, that the difference in height between any two adjacent piles was D cookies, and that there were N piles, can you write a program to figure out how many cookies there were in total?

Problem: Sphere Online Judge (SPOJ) – Problem AMR10F

Solution: This is quite a nice and simple problem. The easiest solution is just to write a loop to calculate the amount of cookies. If you think one step further you can write a general formula for calculating this.
Let’s imagine three piles of cookies.

At the rightmost there are A cookies. The middle one got A + D cookies and the leftmost got A + 2D cookies. If we generalize this we get: \text{allCookies} = (A + 2 * D) + (A + 1 * D) + (A + 0 * D) which can be written as \sum_{i=0}^{N-1} (A + iD).
And thus can be simplified:

\sum_{i=0}^{N-1} A + D \sum_{i=0}^{N-1} i = NA + D\frac{(N-1)N}{2}.

T = int(raw_input())

for i in xrange(0, T):
    N, A, D = raw_input().split()
    
    N = int(N)
    A = int(A)
    D = int(D)

    print (N * A) + D * ( (N - 1) * N ) / 2

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.

SPOJ: 4301. Tables

Byteman works as a carpenter. He has just received an order for s pine-wood tables. Although he has plenty of pine-wood boards in his workshop, he has just run out of screws. Therefore he needs to walk to the warehouse and bring back some boxes with screws. What is the minimum number of boxes that he needs to bring in order to have enough screws to make the tables?

Problem: Sphere Online Judge (SPOJ) – Problem AE1B

Solution: That’s a nice application for an greedy algorithm, i.e. you grab the largest values successively. This yields the optimal solution in this case because we don’t need to find exactly X screws. It’s sufficient to find at least X screws.

inp1 = raw_input()
inp2 = raw_input()


numBoxes, screwsPerTable, tables = inp1.split()

boxes = inp2.split()

numBoxes = int(numBoxes)
screwsPerTable = int(screwsPerTable)
tables = int(tables)
boxes = map(int, boxes)

boxes.sort()
boxes.reverse()

needed = tables * screwsPerTable

i = 0
while needed > 0:
    needed -= boxes[i]
    i += 1

print i