Concrete Abstractions: Chapter 12

Exercise 12.4: Draw a tree, analogous to Figure 4.4 on page 92, showing how the value of C(4, 2) is computed by choose. Your tree should have C(4, 2) at the root and six 1s as its leaves.
Solution:

Exercise 12.6: Using these procedures, write
a. A procedure called table-fill! that takes a table and an element and sets every entry in the table to the given element. For example, (table-fill! table 0) would have a similar effect to that of zero-out-vector! in Section 11.6.
b. A procedure called display-table that nicely displays its table parameter.

Solution:

(define table-fill!
  (lambda (table value)
    (define loop-row
      (lambda (row column)
        (if (= column (table-width table))
            'done
            (begin
              (table-set! table row column value)
              (loop-row row (+ column 1))))))
    (define loop
      (lambda (row)
        (if (= row (table-height table))
            'done
            (begin
              (loop-row row 0)
              (loop (+ row 1))))))
    (loop 0)))

(define display-table
  (lambda (table)
    (define show-row
      (lambda (row column)
        (if (= column (table-width table))
            (newline)
            (begin
              (display (table-ref table row column))
              (display " ")
              (show-row row (+ column 1))))))
    (define show
      (lambda (row)
        (if (= row (table-height table))
            (newline)
            (begin
              (show-row row 0)
              (show (+ row 1))))))
    (show 0)))

Exercise 12.31: Imagine the following game: You are given a path that consists of white and black squares. The exact configuration of white and black squares varies with the game. You start on the leftmost square (which we’ll call square 0), and your goal is to move off the right end of the path in the least number of moves. However, the rules stipulate that:
If you are on a white square, you can move either 1 or 2 squares to the right.
If you are on a black square, you can move either 1 or 4 squares to the right. […]
Write a memoized version of fewest-moves.
Solution:

(define fewest-moves-mem
  (lambda (path)
    (let ((table (make-vector (vector-length path))))
      (define fewest-moves-f
        (lambda (path i)
          (cond ((>= i (vector-length path))
                 0)
                ((equal? (vector-ref path i) 'white)
                 (+ 1 (min (fewest-moves-sub path (+ i 1))
                           (fewest-moves-sub path (+ i 2)))))
                (else
                 (+ 1 (min (fewest-moves-sub path (+ i 1))
                           (fewest-moves-sub path (+ i 4))))))))

      (define fewest-moves-sub
        (lambda (path i)
          (ensure-in-table! path i)
          (vector-ref table i)))

      (define ensure-in-table!
        (lambda (path i)
          (if (vector-ref table i)
              'done
              (store-in-table! table i))))

      (define store-in-table!
        (lambda (table i)
          (vector-set! table i (fewest-moves path i))))

      (vector-fill! table #f)

      (fewest-moves-f path 0))))

Exercise 12.33: The function h(n) is defined for nonnegative integers n as follows:
$h(n) = \begin{cases} 1 & \text{ if } n<2\\ h(n-1) + h(n-2) & \text{ if n } < \text{2 and n is odd}\\ h(n-1) + h(n/2) & \text{ if n } \geq \text{2 and n is even}\\ \end{cases}$
a. Write a dynamic programming procedure for efficiently calculating $h(n).$
b. Is it possible to modify the procedure so that it stores all the values it needs in a vector of fixed size, as walk-count can be modified to store the values it needs in a two-element vector? (A vector of “fixed size” is one with a size that does not depend on the parameter, n.) Justify your answer.
Solution: a & b. I implemented b directly into the code.

(define h
  (lambda (n)
    (let ((vector (make-vector (+ n 1))))
      (define calc-h
        (lambda (n)
          (cond ((< n 2) 1)
                ((odd? n) (+
                           (calc-h-sub (- n 1))
                           (calc-h-sub (- n 2))))
                (else (+
                       (calc-h-sub (- n 1))
                       (calc-h-sub (/ n 2)))))))

      (define calc-h-sub
        (lambda (n)
          (vector-ref vector n)))

      (from-to-do 0 n
                  (lambda (i)
                    (vector-set! vector i (calc-h i))))

      (calc-h n))))

Concrete Abstractions: Chapter 9

Exercise 9.2: The sequences we just described are restricted to consecutive increasing sequences of integers (more precisely, to increasing arithmetic sequences where consecutive elements differ by 1). We can easily imagine similar but more general sequences such as <6, 4, 3, 2> or <5, 5.1, 5.2, 5.3, 5.4, 5.5>—in other words, general arithmetic sequences of a given length, starting value, and increment (with decreasing sequences having a negative increment value).
a. Write a procedure sequence-with-from-by that takes as arguments a length, a starting value, and an increment and returns the corresponding arithmetic sequence. Thus, (sequence-with-from-by 5 6 -1) would return the first and (sequence-with-from-by 6 5 .1) would return the second of the two pre- ceding sequences. Remember that sequences are represented as procedures, so your new sequence constructor will need to produce a procedural result.
b. The procedure sequence-from-to can now be rewritten as a simple call to sequence-with-from-by. The original sequence-from-to procedure made an empty sequence if its first argument was greater than its second, but you should make the new version so that you can get both increasing and de- creasing sequences of consecutive integers. Thus, (sequence-from-to 3 8) should return <3, 4, 5, 6, 7, 8>, whereas (sequence-from-to 5 1) should return <5, 4, 3, 2, 1>.
c. Write a procedure sequence-from-to-with that takes a starting value, an ending value, and a length and returns the corresponding arithmetic sequence. For example, (sequence-from-to-with 5 11 4) should return <5, 7, 9, 11>.

Solution:

; a.
(define sequence-with-from-by
  (lambda (start len inc)
    (lambda (op)
      (cond ((equal? op 'empty-sequence?)
              (= len 0))
            ((equal? op 'head)
               start)
            ((equal? op 'tail)
               (sequence-with-from-by (+ start inc) (- len 1) inc))
            ((equal? op 'sequence-length)
               len)
            (else
               (error "illegal operation" op))))))

; b.
(define sequence-from-to
  (lambda (a b)
    (if (< a b)
      (sequence-with-from-by a (+ (- b a) 1) 1)
      (sequence-with-from-by a (+ (- a b) 1) (- 1)))))

; c.
(define sequence-from-to-with
  (lambda (start end len)
   (sequence-with-from-by start len (/ (+ (- end start) 2) len))))

Exercise 9.6: Write the sequence constructor sequence-map, that outwardly acts like the list procedure map. However unlike map, which applies the procedural argument to all the list elements, sequence-map should not apply the procedural argument at all yet. Instead, when an element of the resulting sequence (such as its head) is accessed, that is when the procedural argument should be applied.

Solution:

(define sequence-map
  (lambda (sequence f)
   (lambda (op)
     (cond
       ((equal? op 'empty-sequence?)
         (empty-sequence? sequence))
       ((equal? op 'head)
         (f (head sequence)))
       ((equal? op 'tail)
         (sequence-map (tail sequence) f))
       ((equal? op 'sequence-length)
         new-length)
       ((equal? op 'sequence-ref)
        (lambda (n)
         (if (= n 0)
           head
           (sequence-ref tail (- n 1)))))
       (else (error "illegal sequence operation" op))))))

Exercise 9.: One way we can represent a set is as a predicate (i.e., a procedure that returns true or false). The idea is that to test whether a particular item is in the set, we pass it to the procedure, which provides the answer. For example, using this representation, the built-in procedure number? could be used to represent the (infinite) set of all numbers.
a. Implement element-of-set? for this representation. It takes two arguments, an element and a set, and returns true or false depending on whether the element is in the set or not.
b. Implement add-to-set for this representation. It takes two arguments, an ele- ment and a set, and returns a new set that contains the specified element as well as everything the specified set contained. Hint: Remember that a set is represented as a procedure.
c. Implement union-set for this representation. It takes two arguments—two sets— and returns a new set that contains anything that either of the provided sets contains.

Solution:

; a
(define element-of-set?
  (lambda (element set)
   (set element)))

; b.
(define add-to-set
  (lambda (element set)
    (lambda (ele)
      (if (equal? ele element)
        #t
        (set ele)))))

; c.
(define union-set
  (lambda (set1 set2)
    (lambda (ele)
      (or (set1 ele) (set2 ele)))))

Exercise 9.: Assume that infinity has been defined as a special number that is greater than all normal (finite) numbers and that when added to any finite number or to itself, it yields itself. Now there is no reason why sequences need to be of finite length. Write a constructor for some interesting kind of infinite sequence.

Solution:

; Ex 9.22
(define sequence-from-to-inf
  (lambda (from)
    (lambda (op)
     (cond ((equal? op 'head)
        from)
           ((equal? op 'tail)
        (sequence-from-to-inf (+ 1 from)))
           ((equal? op 'sequence-length)
         +inf.0)
           (else
         (error "operation not found" op))))))</code>

; Interesting application
(define display-even-sequence
  (lambda (seq)
    (if (even? (head seq))
        (display (head seq))
        (display " "))
        (display-even-sequence (tail seq))))

(define display-f-sequence
  (lambda (seq f)
    (display (f (head seq)))
    (display " ")
    (display-f-sequence (tail seq) f)))

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