SICP Exercise 2.67 use of decode

Exercise 2.67.  Define an encoding tree and a sample message:

(define sample-tree
  (make-code-tree (make-leaf 'A 4)
                  (make-code-tree
                   (make-leaf 'B 2)
                   (make-code-tree (make-leaf 'D 1)
                                   (make-leaf 'C 1)))))

(define sample-message '(0 1 1 0 0 1 0 1 0 1 1 1 0))

Use the decode procedure to decode the message, and give the result.

SOLUTION

 The code and tests are here.

Comments

Post a Comment

Popular posts from this blog

SICP Exercise 2.18 reverse

Exercise 2.18.   Define a procedure  reverse  that takes a list as argument and returns a list of the same elements in reverse order: (reverse (list 1 4 9 16 25)) (25 16 9 4 1) SOLUTION The code and tests are here .
Read more

SICP Exercise 1.45 multi average damp

Image
Exercise 1.45.   We saw in section  1.3.3  that attempting to compute square roots by naively finding a fixed point of  y     x / y  does not converge, and that this can be fixed by average damping. The same method works for finding cube roots as fixed points of the average-damped  y     x / y 2 . Unfortunately, the process does not work for  fourth roots -- a single average damp is not enough to make a fixed-point search for  y     x / y 3 converge. On the other hand, if we average damp twice (i.e., use the average damp of the average damp of  y     x / y 3 ) the fixed-point search does converge. Do some experiments to determine how many average damps are required to compute  n th roots as a fixed-point search based upon repeated average damping of  y     x / y n -1 . Use this to implement a simple procedure for computing  n th roots using  fixed-point ,  averag...
Read more

SICP Exercise 2.96 pseudoremainder

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.
Read more