lambdaphant’s posterous

lambdaphant’s posterous

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

Filed under

sicp

See all posts on posterous with this tag ยป
Jan 14 / 10:36pm

SICP exercises 1.14 and 1.15 are now commited and other randomness

I did 1.14 in Open Office Draw, which turned out to be a bad idea. I really should have used graphviz to make the tree, and will probably go back and do it in graphviz anyways. Oh well. There are a lot of things I am not really liking about Draw and this problem would have been way easier to do in graphviz. A Draw like program for making diagrams and wireframes is nice sometimes, but Draw itself feels cumbersome. I will be in search of a better application for that purpose.
 
Today I realized that I need new music and in my search remembered http://www.thesixtyone.com/. Last year I signed up with an account and never used it. Now I've used the site a bit and so far I like it. The UI is a bit weird at first, and I was having trouble finding things. Some things about the site aren't really intuitive. I also don't like the modal box that pops up after ever new song when you are listening to songs on the rack. That being said so far the music is new and decent. I want to build up some status on the site to see what sort of recommendations I get. I've noticed that sites like last.fm (while a pretty awesome idea) recommend me stuff that I don't really like or I already listen to. Hopefully the sixty one will be better than that.
 
During my SICP quest I learned about successive squaring today. Successive squaring is defined as if n is even and if n is odd. This quickens things up when finding exponents.
Loading mentions Retweet
Filed under  //  math   music   SICP  

Comments (0)

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 10 / 5:25pm

SICP exercises now on Github

I've realized that blog posts are a less than ideal way to keep track of code exercises. This being the case I've decided to keep track of them with git. You can follow it at github if you like.
 
http://github.com/emkay/sicp-exercises/tree/master
 
git://github.com/emkay/sicp-exercises.git
Loading mentions Retweet
Filed under  //  github   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)

Jan 1 / 8:49pm

MIT Intro to Algorithms and SICP and the New Year

My goal is to complete both of these courses by May. That gives me a full 4 months. I haven't set out a complete schedule, and probably won't being that this time constraint isn't really definitive. If it takes me a little longer it isn't really that big of a deal, but I want to get them both done before we head over to Europe in June.
 
I have already started the SICP lectures and book. That is going well so far. The first lecture and subsequent parts of the book deal with the basics of scheme, which I already knew. Pretty quickly though they both start covering some really cool new stuff, and I am already learning a ton even though I just started. It is funny that these lectures were recorded in 1986 yet still are platinum lectures. These lectures make it rain.
 

 
Now I've had the MIT Intro to Algorithms book for about a year now. I've read chapters here and there. I think the beginning sorting ones and some others scattered throughout. I have done none of the exercises though, and haven't really understood very much of what is going on. The basic sorting stuff I get but anything more complex then that is over my head. Hopefully the lectures will help with that. The thing that worries me the most is my lack of math knowledge. I have had extremely little formal math training. I guess little non-formal math training too. I'm trying to find a decent free discrete math book to pick up while I am going though the lectures, but I'm also worried that this may be too much to handle all at once. Regardless I am going to have to buckle down and get my feet wet with discrete math before I fully understand algorithms.
 
The ultimate goal is to keep learning more and more about what interests me. I was not a computer science major, but rather a philosophy major. The highest math class I took was statistics. Thankfully during my employment as a programmer statistics and basic algebra is the only math that I have used. Still though I want to improve myself and keep going full speed with CS.
 
This month I will have officially have been working in the technology field for 10 years. I never really planned on being a programmer as a career but now I couldn't imagine being anything else. The truth is that I love programming and program even when I'm not working. I've also learned a lot in 10 years about unix(linux, bsd), programming language, markup languages, security, networking, telephony, version control, and all kinds of things.
 
I'm thinking of starting a book list this year too. I read quite a lot of books last year and would like to start keeping track of them. Maybe I will post here whenever I finish a book.
 
I'm excited for the new year and am ready to get reading/lecture watching/learning.
Loading mentions Retweet
Filed under  //  Algorithms   Make it rain   SICP  

Comments (0)