Solution to Exercise 1.12:
(define (pascal row col)
(cond ((or (= 0 col) (= row col)) 1)
(else (+ (pascal (- row 1) (- col 1))
(pascal (- row 1) col)))))
Solution to Exercise 1.12:
(define (pascal row col)
(cond ((or (= 0 col) (= row col)) 1)
(else (+ (pascal (- row 1) (- col 1))
(pascal (- row 1) col)))))
Solution to Exercise 1.11:
A recursive process:
(define (fr n)
(cond ((< n 3) n)
(else (+ (fr (- n 1))
(* 2 (fr (- n 2)))
(* 3 (fr (- n 3)))))))
An iterative one:
(define (fi n)
(define (f-iter i f-i-1 f-i-2 f-i-3)
(if (> i n)
f-i-1
(f-iter (+ i 1)
(+ f-i-1 (* 2 f-i-2) (* 3 f-i-3))
f-i-1
f-i-2)))
(if (< n 3)
n
(f-iter 3 2 1 0)))
Paul Graham has written a brief essay on writing essays:
I think it’s far more important to write well than most people realize. Writing doesn’t just communicate ideas; it generates them. If you’re bad at writing and don’t like to do it, you’ll miss out on most of the ideas writing would have generated.
Every time I read one of Paul’s essays I feel inspired to write one myself. It’s a pity I have the attention span of a gold fish.
I heard back from city hall about the permit:
A building permit is required to finish a basement when you are creating a bedroom, doing any plumbing work (including a rough-in or bar sink) or making any structural changes (including new exterior openings, moving posts/beams etc.). A permit is not required if you are installing fixtures on an existing rough-in. Electrical permits are done through the electrical safety authority, you can contact them at 746-3040.
No bedrooms. No plumbing. No structural changes. No permit required.
According to a New Scientist story, global warming could trigger ant invasions:
The study of 665 ant colonies in environments ranging from tropical rainforests to frozen tundra suggests that in warmer environments the ants’ body size shrinks, on average, while the number of individuals in the colony booms.
Global warming might shrink ant workers by as much as a third, says Michael Kaspari at the University of Oklahoma, US, and the Smithsonian Tropical Research Institute in Panama, who carried out the study: “And since ant species with small workers appear to be particularly successful at invading, ant invasions – already destructive – may become more common in a warming world.”
I’m looking forward to reading the inevitable query letter.
A few weeks ago Mandy and I decided to start renovating part of our basement. Our 30,000ft plan is to transform about a third of the basement into a rec room, into which we’ll move the big screen. The family room, which currently houses the TV, will become a reading room/office, a more appropriate function considering all the built-in oak cabinetry.
I like to think of myself as a fairly handy guy, so I’m planning to do most of the work myself. From what I’ve read, doing it myself should cut the cost of the reno in half. I don’t have much direct experience in many aspects of a basement reno — I’ve never framed a wall, added new wiring, or hung drywall before, for example — so I expect I will have a lot to learn in the process.
My first adventure in renovation education was a trip to our local Rona store in early February. They had advertised a session on framing a basement for the Saturday morning, and a related session on wiring in the afternoon. I showed up for the morning session only to find, after waiting for an hour, that the instructor was not able to attend. While I waited a took a look around the store and jotted down some prices for materials and browsed through their book section, which clued me into the idea that an instructed session was a waste of time. I should just order a book on basement renovations that teaches me what I need to know.
When I got home, I surfed Amazon until I found Remodeling a Basement: Expert Advice from Start to Finish, which seemed to have the most favourable reviews, and ordered it. It arrived a few days later. For the next few weeks I didn’t make any noticeable progress on the basement. I was just reading through the book.
The next step was drawing up a plan for the basement. This turned out to be more work than I expected, especially considering how simple our plans are — basically just closing in an open space. I found one very helpful tip in the book for this step. Make a scale drawing of the existing layout on a piece of grid paper first. Photocopy it. Then draw your design in pencil on the copy. With the existing layout in permanent ink, it is easy to try different ideas and erase the duds without having to redraw everything.
With a plan in hand, I finally got started on some actual work last weekend: demolition! This was almost entirely brain-dead grunt work, something I’ve discovered to quite enjoy. I lifted some tired old carpet, dismantled a wall removed a bunch of drywall around the stairway.
On my day off last Friday, I rerouted some central vac conduit. I had to go to a local vacuum store to pick up the necessary fittings; Canadian Tire does not carry them because, according to a salesperson there, they vary in size from brand to brand.
Now I’m all ready to start framing. Well… almost ready. I don’t have a building permit yet, and I’m not sure that I need one. I emailed city hall yesterday and unsurprisingly haven’t heard back from them yet.
I’m hoping to get some quotes and place an order for the lumber this week. Trying to price this stuff online is hopeless. Home Depot doesn’t even acknowledge that they sell lumber on their website.
If I can get the permit and lumber lined up by Wednesday, I can start working on Thursday, which I’ll be taking off. I’ll try to keep track my progress here more regularly in the future.
Solution to Exercise 1.10:
> (A 1 10)
1024
> (A 2 4)
65536
> (A 3 3)
65536
(f n) computes 2n.
(g n) computes 2n for n>0. For n=0, it is 0.
(h n) computes h(n) such that if n=0, h(0)=0; otherwise h(n)=2h(n-1).
Solution to Exercise 1.9:
The first procedure follows a recursive process:
(+ 4 5)
(inc (+ (dec 4) 5))
(inc (+ 3 5))
(inc (inc (+ (dec 3) 5)))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ (dec 2) 5))))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ (dec 1) 5)))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9
The second follows an iterative one:
(+ 4 5)
(+ (dec 4) (inc 5))
(+ 3 6)
(+ (dec 3) (inc 6))
(+ 2 7)
(+ (dec 2) (inc 7))
(+ 1 8)
(+ (dec 1) (inc 8))
(+ 0 9)
9
Solution to Exercise 1.8:
(define (square x)
(* x x))
(define (cube x)
(* x x x))
(define (cbrt-iter guess prev-guess x)
(if (good-enough? guess prev-guess)
guess
(cbrt-iter (improve guess x)
guess
x)))
(define (improve guess x)
(/ (+ (/ x (square guess))
(* 2 guess))
3))
(define (good-enough? guess prev-guess)
(< (/ (abs (- guess prev-guess))
guess)
0.001))
(define (cbrt x)
(cbrt-iter 1.0 0.0 x))
This solution uses the guess evaluation strategy of Exercise 1.7.
It seems to give reasonable results:
> (cbrt 8)
2.000000000012062
> (cbrt 27)
3.0000005410641766
> (cbrt 64)
4.000000000076121
Solution to Exercise 1.7:
The results for small values become very inaccurate. For example, the root of the square of 0.001, which we might expect to be itself is found to be off by a factor of ~31.3 times.
> (sqrt (square 0.001))
0.031260655525445276
As the values grow larger, the precision of the guess comes into play. Eventually the computer becomes unable to represent the guess to a precision of 0.001. In such cases, the program can endlessly alternate between two guesses that are more than 0.001 away from the true square root. On my x86 machine with DrScheme, this can be seen with the following expression
> (sqrt 1e13)
Here is an implementation of good-enough/ that follows the alternative strategy given in the exercise
(define (good-enough? guess prev-guess)
(< (/ (abs (- guess prev-guess))
guess)
0.001))
The x parameter is replaced by prev-guess, which necessitates a change to sqrt-iter and sqrt, as shown here:
(define (sqrt-iter guess prev-guess x)
(if (good-enough? guess prev-guess)
guess
(sqrt-iter (improve guess x)
guess
x)))
(define (sqrt x)
(sqrt-iter 1.0 0.0 x))
I’ve used an initial prev-guess of zero, which ensures that the initial guess of one is never good enough, thus forcing at least one iteration of the algorithm.
This implementation performs much better on the two troublesome examples given above:
> (sqrt (square 0.001))
0.0010000001533016628
> (sqrt 1e13)
3162277.6640104805