HN reads SICP

exercise_1.1

2009-02-23T23:42:33+00:00

Below is a sequence of expressions. What is the result printed by the interpreter in response to each expression? Assume that the sequence is to be evaluated in the order in which it is presented. 10 (+ 5 3 4) (- 9 1) (/ 6 2) (+ (* 2 4) (- 4 6)) (define a 3) (define b (+ a 1)) (+ a b (* a b)) (= a b) (if (and (> b a) (< b (* a b))) b a) (cond ((= a 4) 6) ((= b 4) (+ 6 7 a)) (else 25)) (+ 2 (if (> b a) b a)) (* (cond ((> a b) a) ((< a b) b) (else -1)) (+…

exercise_1.19

2009-02-24T16:52:36+00:00

; T_pq_(a,b): a' <- bq + aq + ap, b' <- bp + aq ; T_pq_(a',b'): b'' <- p(bp + aq) + q(bq + aq + ap) ; <- bpp + apq + bqq + aqq + apq ; <- (pp + qq)b + (2pq + qq)a ; look for p' = (pp + qq), q' = (2pq + qq) ; a'' <- (bpq + aqq) + (q + p)(bq + aq + ap) ; <- bpq + aqq + bqq + aqq + apq + bpq + apq + app ; <- b(2pq + qq) + a(2pq + qq) + a(…

exercise_1.29

2009-02-25T00:17:31+00:00

I don't like this one, I want to see someone post a better version: ;Simpson's rule ;integral of f between a & b = h/3[y0 + 4y1 + 2y2 + 4y3 + ... + yn] ; h = (b-a)/n, yk = f(a + kh) ; endpoints multiplied by 1 ; odd #s * 4, evens * 2. (define (simpsons-rule f a b n) (let ((h (/ (- b a) n))) (define (coef k) (cond ((= 0 (modulo k 2)) 2) (else 4))) (define (term k) (* (coef k) (f (+ a (* k h))))) (defi…

exercise_1.30

2009-03-02T00:19:23+00:00

Exercise 1.30. The sum procedure above generates a linear recursion. The procedure can be rewritten so that the sum is performed iteratively. Show how to do this by filling in the missing expressions in the following definition: (define (sum term a next b) (define (iter a result) (if (> a b) result (iter (next a) (+ (term a) result)))) (iter a 0))

exercise_1.31

2009-03-02T01:02:48+00:00

a. The sum procedure is only the simplest of a vast number of similar abstractions that can be captured as higher-order procedures. Write an analogous procedure called product that returns the product of the values of a function at points over a given range. Show how to define factorial in terms of product. Also use product to compute approximations to using the formula:

exercise_1.32

2009-03-02T01:06:21+00:00

Exercise 1.32. a. Show that sum and product (exercise 1.31) are both special cases of a still more general notion called accumulate that combines a collection of terms, using some general accumulation function: (accumulate combiner null-value term a next b)

exercise_1.33

2009-03-02T00:51:06+00:00

Exercise 1.33. You can obtain an even more general version of accumulate (exercise 1.32) by introducing the notion of a filter on the terms to be combined. That is, combine only those terms derived from values in the range that satisfy a specified condition. The resulting filtered-accumulate abstraction takes the same arguments as accumulate, together with an additional predicate of one argument that specifies the filter. Write filtered-accumulate as a procedure. Show how to express the followi…

exercise_1.34

2009-03-02T01:32:46+00:00

Suppose we define the procedure (define (f g) (g 2)) Then we have (f square) 4 (f (lambda (z) (* z (+ z 1)))) 6 What happens if we (perversely) ask the interpreter to evaluate the combination (f f)? Explain. Answer: Failure, because (f f) evaluates to (f 2), but then we get (2 2); the first 2 is not a function so the interpreter fails.

exercise_1.35

2009-03-02T01:46:52+00:00

Show that the golden ratio ϕ (section 1.2.2) is a fixed point of the transformation x ↦ 1 + 1/x, and use this fact to compute ϕ by means of the fixed-point procedure. (define ϕ (/ (+ 1 (sqrt 5)) 2)) (+ 1 (/ 1 ϕ)) ; => ϕ = 1.618033988749895 (define tolerance 0.00001) (define (fixed-point f first-guess) (define (close-enough? v1 v2) (< (abs (- v1 v2)) tolerance)) (define (try guess) (let ((next (f guess))) (if (close-enough? guess next) next (try next))))…

exercise_1.36

2009-03-02T01:32:12+00:00

Exercise 1.36. Modify fixed-point so that it prints the sequence of approximations it generates, using the newline and display primitives shown in exercise 1.22. Then find a solution to xx = 1000 by finding a fixed point of x log(1000)/log(x). (Use Scheme's primitive log procedure, which computes natural logarithms.) Compare the number of steps this takes with and without average damping. (Note that you cannot start fixed-point with a guess of 1, as this would cause division by log(1) = 0.)

exercise_1.37

2009-02-26T23:11:16+00:00

a. An infinite continued fraction is an expression of the form N₁ f = ————————————————— N₂ D₁ + —————————— N₃ D₂+ ———————— D₃+ ...

exercise_1.38

2009-03-02T01:51:22+00:00

Exercise 1.38. In 1737, the Swiss mathematician Leonhard Euler published a memoir De Fractionibus Continuis, which included a continued fraction expansion for e - 2, where e is the base of the natural logarithms. In this fraction, the Ni are all 1, and the Di are successively 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, .... Write a program that uses your cont-frac procedure from exercise 1.37 to approximate e, based on Euler's expansion.

exercise_1.39

2009-02-27T00:13:19+00:00

A continued fraction representation of the tangent function was published in 1770 by the German mathematician J.H. Lambert: x tan x = ————————————— x² 1 − ————————— x² 3 − ——————— 5 − ⋱

exercise_1.40

2009-03-02T00:37:01+00:00

Exercise 1.40. Define a procedure cubic that can be used together with the newtons-method procedure in expressions of the form (newtons-method (cubic a b c) 1) to approximate zeros of the cubic x3 + ax2 + bx + c. (define (cubic a b c) (lambda (x) (+ (cube x) (* a (square x)) (* b x) c))) (define (cube x) (* x x x)) (newtons-method (cubic a b c) 1)

exercise_1.41

2009-03-02T00:38:14+00:00

Exercise 1.41. Define a procedure double that takes a procedure of one argument as argument and returns a procedure that applies the original procedure twice. For example, if inc is a procedure that adds 1 to its argument, then (double inc) should be a procedure that adds 2. What value is returned by

exercise_1.42

2009-03-02T00:39:58+00:00

Exercise 1.42. Let f and g be two one-argument functions. The composition f after g is defined to be the function x f(g(x)). Define a procedure compose that implements composition. For example, if inc is a procedure that adds 1 to its argument, ((compose square inc) 6) 49 (define (compose f g) (lambda (x) (f (g x)))) ((compose square inc) 6)

exercise_1.43

2009-03-07T08:49:25+00:00

Exercise 1.43. If f is a numerical function and n is a positive integer, then we can form the nth repeated application of f, which is defined to be the function whose value at x is f(f(...(f(x))...)). For example, if f is the function x ↦ x + 1, then the nth repeated application of f is the function x ↦ x + n. If f is the operation of squaring a number, then the nth repeated application of f is the function that raises its argument to the 2ⁿth power. Write a procedure that takes as input…

exercise_1.44

2009-03-02T00:42:12+00:00

Exercise 1.44. The idea of smoothing a function is an important concept in signal processing. If f is a function and dx is some small number, then the smoothed version of f is the function whose value at a point x is the average of f(x - dx), f(x), and f(x + dx). Write a procedure smooth that takes as input a procedure that computes f and returns a procedure that computes the smoothed f. It is sometimes valuable to repeatedly smooth a function (that is, smooth the smoothed function, and so on…

exercise_1.45

2009-03-08T23:10:51+00:00

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². 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³ converge. On the other hand, if we average damp twice (i.e., use the average damp of the …

exercise_1.46

2009-03-07T09:39:38+00:00

Several of the numerical methods described in this chapter are instances of an extremely general computational strategy known as iterative improvement. Iterative improvement says that, to compute something, we start with an initial guess for the answer, test if the guess is good enough, and otherwise improve the guess and continue the process using the improved guess as the new guess. Write a procedure iterative-improve that takes two procedures as arguments: a method for telling whether a…

exercise_2.16

2009-03-13T00:17:24+00:00

Explain, in general, why equivalent algebraic expressions may lead to different answers. Can you devise an interval-arithmetic package that does not have this shortcoming, or is this task impossible? (Warning: This problem is very difficult.) As seen in Exercise 2.14, most of the algebraic identities that hold on operations over real numbers do not hold on the analogous operations over intervals.

exercise_2.6

2009-03-07T09:25:59+00:00

In case representing pairs as procedures wasn't mind-boggling enough, consider that, in a language that can manipulate procedures, we can get by without numbers (at least insofar as nonnegative integers are concerned) by implementing 0 and the operation of adding 1 as

start

2009-03-07T09:19:25+00:00

This wiki is created by the HN-reads-SICP group, for posting solutions and discussion on the SICP exercises. Please add your own solutions or thoughts once you have done each exercise. Chapter 1. Building Abstractions with Procedures 1.1 The Elements of Programming Exercise 1.1