CS Musings

Stuff in this chapter i haven’t kept on my computer, this is largely a placeholder post until i get some time to come back to this.

Since I have more or less already done this chapter, I am going to lump the whole thing in one post.

Chapter was quite simple for me, since I have already finished HtDP for school. It is mostly a repeat of that book with some new problems, which I am going to present here.

I have skipped the exercises in Section 1.1 to go in to more interesting stuff, if I have time at the end, I will come back and do the exercises, but most people shouldn’t have problems with that section.

Section 1.2

Exercise 1.9:

Well this exercise should not cause too much problem, if you write it out, you will find that the version is recursive, and the second version is iterative.

Exercise 1.10:

This exercise practices the useful skill of tracing through the execution of a procedure more thoroughly, with multiple functions composed together, you can check the answer by running it through a scheme environment such as Dr Scheme.

Exercise 1.11:

Well the recursive process is straightforward, its just a translation of the definition, as follows:

(define (f-rec n)
  (if (< n 3)
      n
      (+ (f-rec (- n 1)) (* 2 (f-rec (- n 2))) (* 3 (f-rec (- n 3))))))

The iterative version is a bit more tricky, but still relatively easy if you study the iterative version for the Fibonacci numbers example. The basic idea behind the whole thing is that you are doing a lot of repeated work by translating straight from definition. For example, to calculate f(n), you will have to calculate f(n-1), f(n-2), f(n-3). Then when you go on to calculate 2f(n-1), without storing the value of f(n-1) somewhere, you will have to recalculate the whole thing again. So we will be creating some more parameters to store enough information to calculate f(n) without doing repeated work. A more general method to resolve this problem is called Dynamic Programming.
Anyways, without further ado, here is the code:

(define (f n)
  (f-iter 2 1 0 n))
 
(define (f-iter a b c count)
  (if (= count 0)
      c
      (f-iter (+ a (* 2 b) (* 3 c)) a b  (- count 1))))

Exercise 1.12

This exercise is to write a procedure to compute binomial coefficients, it is quite easy. We’ll have two parameters, one to denote the number of rows (first being 0), and the other denote the number of columns (first being 0):

(define (pascal-number row col)
  (cond
    [(= col 0) 1]
    [(= row 0) 0]
    [else (+ (pascal-number (- row 1) (- col 1))
             (pascal-number (- row 1) col))]))

Exercise 1.13

Skipped, due to it being a practice in induction proofs, and the actual process involved is quite nasty.

Exercise 1.14

Posted by Jason under Computer Science & SICP | No Comments »