SICP Exercise 2.66 lookup

Exercise 2.66.  Implement the lookup procedure for the case where the set of records is structured as a binary tree, ordered by the numerical values of the keys.

 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