SICP

Exercise 3.17.   Devise a correct version of the  count-pairs  procedure of exercise  3.16  that returns the number of distinct pairs in any structure. (Hint: Traverse the structure, maintaining an auxiliary data structure that is used to keep track of which pairs have already been counted.) SOLUTION The code is here: Exercise 3.17 correct count-pairs The explanation and the box-and-pointer diagram is here: Diagram

Exercise 3.16.   Ben Bitdiddle decides to write a procedure to count the number of pairs in any list structure. ``It's easy,'' he reasons. ``The number of pairs in any structure is the number in the  car  plus the number in the  cdr  plus one more to count the current pair.'' So Ben writes the following procedure: (define (count-pairs x)   (if (not (pair? x))       0       (+ (count-pairs (car x))          (count-pairs (cdr x))          1))) Show that this procedure is not correct. In particular, draw box-and-pointer diagrams representing list structures made up of exactly three pairs for which Ben's procedure would return 3; return 4; return 7; never return at all. SOLUTION The code is here: Exercise 3.16 count-pairs The box-and-pointer ...

Exercise 3.15.   Draw box-and-pointer diagrams to explain the effect of  set-to-wow!  on the structures  z1  and  z2  above. The box-and-pointer diagrams are here: Page 1 Page 2

Exercise 3.14.   The following procedure is quite useful, although obscure: (define (mystery x)   (define (loop x y)     (if (null? x)         y         (let ((temp (cdr x)))           (set-cdr! x y)           (loop temp x))))   (loop x '())) Loop  uses the ``temporary'' variable  temp  to hold the old value of the  cdr  of  x , since the  set-cdr!  on the next line destroys the  cdr . Explain what  mystery  does in general. Suppose  v  is defined by  (define v (list 'a 'b 'c 'd)) . Draw the box-and-pointer diagram that represents the list to which  v  is bound. Suppose that we now evaluate  (d...

Exercise 3.13.    Consider the following  make-cycle  procedure, which uses the  last-pair  procedure defined in exercise  3.12 : (define (make-cycle x)   (set-cdr! (last-pair x) x)   x) Draw a box-and-pointer diagram that shows the structure  z  created by (define z (make-cycle (list 'a 'b 'c))) What happens if we try to compute  (last-pair z) ? SOLUTION The code is here: Exercise 3.13 make-cycle The box-and-pointer diagrams are here:

Exercise 3.12.    The following procedure for appending lists was introduced in section  2.2.1 : (define (append x y)   (if (null? x)       y       (cons (car x) (append (cdr x) y)))) Append  forms a new list by successively  cons ing the elements of  x  onto  y . The procedure  append!  is similar to  append , but it is a mutator rather than a constructor. It appends the lists by splicing them together, modifying the final pair of  x  so that its  cdr  is now  y . (It is an error to call  append!  with an empty  x .) (define (append! x y)   (set-cdr! (last-pair x) y)   x) Here  last-pair  is a procedure that returns the last pair in its argument: (define (last-pair x)   (if (...

Exercise 3.11.    In section  3.2.3  we saw how the environment model described the behavior of procedures with local state. Now we have seen how internal definitions work. A typical message-passing procedure contains both of these aspects. Consider the bank account procedure of section  3.1.1 : (define (make-account balance)   (define (withdraw amount)     (if (>= balance amount)         (begin (set! balance (- balance amount))                balance)         "Insufficient funds"))   (define (deposit amount)     (set! balance (+ balance amount))     balance)   (define (dispatch m)     (cond...

Exercise 3.10.   In the  make-withdraw  procedure, the local variable  balance  is created as a parameter of  make-withdraw . We could also create the local state variable explicitly, using  let , as follows: (define (make-withdraw initial-amount)   (let ((balance initial-amount))     (lambda (amount)       (if (>= balance amount)           (begin (set! balance (- balance amount))                  balance)           "Insufficient funds")))) Recall from section  1.3.2  that  let  is simply syntactic sugar for a procedure call: (let ((< var > < exp >)) < body >) is interprete...

Exercise 3.9.    In section  1.2.1  we used the substitution model to analyze two procedures for computing factorials, a recursive version (define (factorial n)   (if (= n 1)       1       (* n (factorial (- n 1))))) and an iterative version (define (factorial n)   (fact-iter 1 1 n)) (define (fact-iter product counter max-count)   (if (> counter max-count)       product       (fact-iter (* counter product)                  (+ counter 1)                  max-count))) Show the environment structures created by ...

Exercise 3.8.    When we defined the evaluation model in section  1.1.3 , we said that the first step in evaluating an expression is to evaluate its subexpressions. But we never specified the order in which the subexpressions should be evaluated (e.g., left to right or right to left). When we introduce assignment, the order in which the arguments to a procedure are evaluated can make a difference to the result. Define a simple procedure  f  such that evaluating  (+ (f 0) (f 1))  will return 0 if the arguments to  +  are evaluated from left to right but will return 1 if the arguments are evaluated from right to left. SOLUTION The code is here: Exercise 3.8 evaluation order Everything is good but the state variables are not properly encapsulated. Spent some time on this but could not find a way to hide them.

Exercise 3.7.    Consider the bank account objects created by  make-account , with the password modification described in exercise  3.3 . Suppose that our banking system requires the ability to make joint accounts. Define a procedure  make-joint  that accomplishes this.  Make-joint  should take three arguments. The first is a password-protected account. The second argument must match the password with which the account was defined in order for the  make-joint  operation to proceed. The third argument is a new password.  Make-joint is to create an additional access to the original account using the new password. For example, if  peter-acc  is a bank account with password  open-sesame , then (define paul-acc   (make-joint peter-acc 'open-sesame 'rosebud)) will allow one to make transactions on  peter-acc  using the name  paul-acc  and the password  rosebud . Yo...

Exercise 3.6.    It is useful to be able to reset a random-number generator to produce a sequence starting from a given value. Design a new  rand  procedure that is called with an argument that is either the symbol  generate or the symbol  reset  and behaves as follows:  (rand 'generate)  produces a new random number;  ((rand 'reset) < new-value >)  resets the internal state variable to the designated < new-value >. Thus, by resetting the state, one can generate repeatable sequences. These are very handy to have when testing and debugging programs that use random numbers. SOLUTION The code is here: Exercise 3.6 reset random number generator.rkt

Exercise 3.5.    Monte Carlo integration  is a method of estimating definite integrals by means of Monte Carlo simulation. Consider computing the area of a region of space described by a predicate  P ( x ,  y ) that is true for points ( x ,  y ) in the region and false for points not in the region. For example, the region contained within a circle of radius 3 centered at (5, 7) is described by the predicate that tests whether ( x  - 5) 2  + ( y  - 7) 2 <  3 2 . To estimate the area of the region described by such a predicate, begin by choosing a rectangle that contains the region. For example, a rectangle with diagonally opposite corners at (2, 4) and (8, 10) contains the circle above. The desired integral is the area of that portion of the rectangle that lies in the region. We can estimate the integral by picking, at random, points ( x , y ) that lie in the rectangle, and testing  P ( x ,  y ) for each point to determine w...

Exercise 3.4.   Modify the  make-account  procedure of exercise  3.3  by adding another local state variable so that, if an account is accessed more than seven consecutive times with an incorrect password, it invokes the procedure  call-the-cops . SOLUTION I converted the explicit 'dispatch' procedure into a lambda function. This made it more elegant. The code is here: SICP Exercise 3.4 call-the-cops

Exercise 3.3.    Modify the  make-account  procedure so that it creates password-protected accounts. That is,  make-account  should take a symbol as an additional argument, as in (define acc (make-account 100 'secret-password)) The resulting account object should process a request only if it is accompanied by the password with which the account was created, and should otherwise return a complaint: ((acc 'secret-password 'withdraw) 40) 60 ((acc 'some-other-password 'deposit) 50) "Incorrect password" SOLUTION The code is here: SICP Exercise Exercise 3.3 password protected account

Exercise 3.2.   In software-testing applications, it is useful to be able to count the number of times a given procedure is called during the course of a computation. Write a procedure  make-monitored  that takes as input a procedure,  f , that itself takes one input. The result returned by  make-monitored  is a third procedure, say  mf , that keeps track of the number of times it has been called by maintaining an internal counter. If the input to  mf is the special symbol  how-many-calls? , then  mf  returns the value of the counter. If the input is the special symbol  reset-count , then  mf  resets the counter to zero. For any other input,  mf  returns the result of calling  f on that input and increments the counter. For instance, we could make a monitored version of the  sqrt  procedure: (define s (make-monitored sqrt)) (s 100) 10 (s 'how-many-calls?) 1 S...

Exercise 3.1.   An  accumulator  is a procedure that is called repeatedly with a single numeric argument and accumulates its arguments into a sum. Each time it is called, it returns the currently accumulated sum. Write a procedure  make-accumulator  that generates accumulators, each maintaining an independent sum. The input to  make-accumulator  should specify the initial value of the sum; for example (define A (make-accumulator 5)) (A 10) 15 (A 10) 25 SOLUTION The code is here: SICP Exercise 3.1 make-accumulator

All Generic Operations Problems in One Program (Look at the bottom part for results from all the tests from Exercise 2.77 to Exercise 2.97)

Thus, here is how to reduce a rational function to lowest terms: Compute the GCD of the numerator and denominator, using the version of  gcd-terms  from exercise  2.96 . When you obtain the GCD, multiply both numerator and denominator by the same integerizing factor before dividing through by the GCD, so that division by the GCD will not introduce any noninteger coefficients. As the factor you can use the leading coefficient of the GCD raised to the power 1 +  O 1  -  O 2 , where  O 2  is the order of the GCD and  O 1  is the maximum of the orders of the numerator and denominator. This will ensure that dividing the numerator and denominator by the GCD will not introduce any fractions. The result of this operation will be a numerator and denominator with integer coefficients. The coefficients will normally be very large because of all of the integerizing factors, so the last step is to remove the redundant factors by computing the (i...

Exercise 2.96. a.    Implement the procedure  pseudoremainder-terms , which is just like  remainder-terms  except that it multiplies the dividend by the integerizing factor described above before calling  div-terms . Modify  gcd-terms to use  pseudoremainder-terms , and verify that  greatest-common-divisor  now produces an answer with integer coefficients on the example in exercise  2.95 . b.    The GCD now has integer coefficients, but they are larger than those of  P 1 . Modify  gcd-terms  so that it removes common factors from the coefficients of the answer by dividing all the coefficients by their (integer) greatest common divisor. SOLUTION The code is here: Exercise 2.96 pseudoremainder Both part a and b of the exercise are verified in the tests. The final result is equal to polynomial P1 from exercise 2.95.