lambdaphant’s posterous

lambdaphant’s posterous

Michael Matuzak  //  Programmer by day, booze drinking calamari cruncher by night.

Filed under

scheme

See all posts on posterous with this tag ยป
Jan 11 / 8:58pm

Found a group on HN to go through SICP with

It is completely coincidence that I started going through the SICP course right before a group has been established on Hacker News. I'm really happy that people are interested in going through the course as a group. It's not really that I am unmotivated to work alone, but being able to talk to people who are around the same chapter and doing the same exercises should prove to be helpful.
 
It is my hope that after this course a similar group will form that wants to go through the MIT Intro to Algorithms course. There have been a couple people on the sicp irc channel that have expressed some interest, so hopefully we can make something of that.
 
What I really like about working in groups is that it also gives things a schedule. As nice as it is to work at your own pace having a schedule that you stick to can be useful as well. I'm ahead of the schedule now, and am going to try to stay ahead. I don't think I've ever been so excited to do homework before. Going through the exercises is pretty fun. I just finished up the Pascal's triangle one which took a bit of thinking. It ended up being really simple, but for some reason I was over thinking it. After some really bad attempts I had to stop myself and just let it sit for a while. I then went back to it today and read the mathematical instructions, and just transfered that over to Scheme. That took about 5 minutes. I guess when you have been working too hard you just need to let a problem sit instead of banging your head against the wall over and over. In this case the problem was really simple and I just was trying to rush through it.
 
Here is the answer that I came up with:
http://github.com/emkay/sicp-exercises/tree/master/chapter1/ex1-12.ss
Loading mentions Retweet
Filed under  //  programming   scheme   SICP  

Comments (0)

Jan 7 / 8:49pm

SICP Exercise 1.11

Recursive:
 
(define (rf n)
  (if (< n 3)
  n
  (+ (rf (- n 1))
   (* 2 (rf (- n 2)))
   (* 3 (rf (- n 3))))))
 
Iterative:
 
(define (f n)
  (if (< n 3)
  n
  (f-iter 0 1 2 n)))
 
(define (f-iter a b c counter)
  (if (= 0 counter)
  a
  (f-iter b c (+ c (* 2 b) (* 3 a)) (- counter 1))))
 
The iterative one took me a while to figure out. Every time I started I kept reverting back to recursive thinking.

Loading mentions Retweet
Filed under  //  programming   scheme   SICP  

Comments (0)

Jan 4 / 4:05pm

SICP Exercise 1.10


 
 > (A 1 10)
1024
 > (A 2 4)
65536
 > (A 3 3)
65536
 
(f n) computes 2n.
 
The next two problems I had trouble on. I am no math wizard. I initially came up with:
  (g n) computes to 2(A(1, n - 1))
and figured that I had the wrong notation and that the answer wasn't really completed because A(1, n -1) makes another recursive call. What I didn't intuitively realize was that this is really 2^n.
 
(h n)
Same thing with this one the answer is 2^h(n-1).
 
I found the answer to these both at: http://community.schemewiki.org/?sicp-ex-1.10
 
Although I am trying to go through these myself I had trouble grasping these ones, but now get it. I also got to read the Ackermann's function Wikipedia entry.

Loading mentions Retweet
Filed under  //  Ackermann's function   programming   scheme   SICP  

Comments (0)

Jan 4 / 1:40pm

SICP Exercise 1.9

(define (+ a b)
  (if (= a 0)
  b
  (inc (+ (dec a) b))))
 
(+ 4 5)
(inc (+ (dec 4) 5))
(inc (inc (+ (dec 3) 5)))
(inc (inc (inc (+ (dec 2) 5))))
(inc (inc (inc (inc (+ (dec 1) 5)))))
(inc (inc (inc (inc (inc (+ 0 5))))))
 
This process is recursive.
 
 
(define (+ a b)
  (if (= a 0)
  b
  (+ (dec a) (inc b))))
 
(+ 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
 
This process is iterative.
Loading mentions Retweet
Filed under  //  programming   scheme   SICP  

Comments (0)

Jan 3 / 5:21pm

SICP Exercises 1.6 - 1.8

1.6
IF is a special form, meaning that it does not apply the operator (IF) to all of the opperands. New-if however does apply the operator to all the operands and because of the recursive call to (sqrt-iter) it never ends.
 
1.7
Running (sqrt 1000000000000000) takes an extremely long time to finish (I stopped it so don't really know if it actually does finish). (sqrt 0.00001) produces the result 0.008235 when the correct answer is 0.003162. Changing good-enough? to
 
(define (good-enough? guess x)
  (< (abs (- guess (improve guess x))) .0001))
 
improves things with both large and small numbers and I get these results when plugging in the same numbers:
 
 > (sqrt 0.00001)
0.003172028655357483
 > (sqrt 1000000000000000)
31622776.601683907
 >
 
1.8
$ cat ex1-8.ss
(define (square x)
  (* x x))
 
(define (cube x)
  (* x x x))
 
(define (improve guess x)
  (/ (/ x (+ (square guess) (* 2 guess))) 3))
 
(define (good-enough? guess x)
  (< (abs (- (cube guess) x)) 0.0001))
 
(define (cubert-iter guess x)
  (if (good-enough? guess x )
   guess
   (cubert-iter (improve guess x)
   x)))
 
(define (cubert x)
  (cubert-iter 1.0 x))

Loading mentions Retweet
Filed under  //  programming   scheme   SICP  

Comments (0)

Jan 3 / 2:56pm

SICP Exercises 1.1 - 1.5

1.1 
10, 12, 8, 3, 6, a, b, 19, #f, 4, 16, 6, 16

1.2 
(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5)))))
(* 3 (- 6 2) (- 2 7)))

1.3 
$ cat ex1-5.ss 
(define (square x)
  (* x x))

(define (sum-of-squares x y)
  (+ (square x) (square y)))

(define (sum-of-squares-larger-nums x y z)
  (cond ((and (< x y) (< x z)) (sum-of-squares y z))
((and (< y z) (< y x)) (sum-of-squares x z))
((and (< z x) (< z y)) (sum-of-squares x y))))

1.4 
When b is greater than 0 the + operator is used, otherwise the - operator is used. 

1.5 
Because applicative-order evaluation evaluates the arguments and then applies them, the procedure p defined as (define (p) (p)) would call itself over and over when called with (test 0 (p)) where the procedure test is defined as (define (test x y) (if (= x 0) 0 y)). Normal-order evaluation however will not have this problem because it does not evaluate the arguments, but rather expands them and reduces them. (test 0 (p)) would simply return 0.

Notes: I see now that I could have simplified 1.3's sum-of-squares-larger-num to use min. It would have made what was going on clearer, but I wrote it using and's first and tested it out. It works so I just left it.
Loading mentions Retweet
Filed under  //  programming   scheme   SICP  

Comments (0)