Alright, I’ve finished exercises 2.17-23, so here are my solutions.

Note, I’ve figured out how to get proper indentation in my posts, so hopefully it will be prettier :)

Exercise 2.17

(define (last-pair l)
  (if (null? (cdr l))
      l
      (last-pair (cdr l))))

Not much to say, it’s an iterative algorithm though and runs in O(n) time and O(1) space, where N is the length of the list l.

Exercise 2.18

I’ve written a recursive and iterative version of this.

(define (remove-last l)
  (if (null? (cdr l))
      (cdr l)
      (cons (car l) (remove-last (cdr l)))))

(define (reverse l)
  (if (null? l)
      l
      (cons (last-pair l) (reverse (remove-last l)))))

This is extraordinarily inefficent, because there are two extra recursive procedures being called each recursion. These being remove-last and last-pair. Because of this inefficiency, I’ve rewritten it using an iterative method, and getting rid of last-pair and remove-last.

(define (reverse l)
  (define (iter l r)
    (if (null? l)
        r
        (iter (cdr l) (cons r (car l))))
  (iter (cdr l) (car l)))

Exercise 2.19

Here are the definitions:

(define (except-first-denomination coins) (cdr coins))
(define (first-denomination coins) (car coins))
(define (no-more? coins) (null? coins))

No, the order doesn’t matter. I actually drew a tree diagram of the six permutations of (list 5 10 25) to make certain of this. I don’t think I’ll bother with the

24

permutations of (list 1 5 10 25). The order does not matter, because the algorithm checks every path possible, removing the denominations which could “block” further processing. eg. if we have (cc 25 (25 10 5)) the 25 branch immediately returns 1, but another branch is also started without 25, allowing processing of (10 5).

Exercise 2.20

(define (filter p? l)
  (cond ((null? l) l)
        ((p? (car l)) (cons (car l) (filter p? (cdr l))))
        (else (filter p? (cdr l)))))

(define (same-parity . a)
  (cond ((even? (car a)) (filter even? a))
        ((odd? (car a)) (filter odd? a))))

The pattern of computing in same-parity can be nicely expressed here using a function called filter, which filters a list for all elements for which a predicate is true of it.

Exercise 2.21
Here are the definitions, again this is pretty simple, “fill-in-the-blank” stuff.

(define (square x) (* x x))
(define (square-list items)
  (if (null? items)
      '()
      (cons (square (car items)) (square-list (cdr items)))))

(define (square-list items)
  (map square items))

Exercise 2.22
To show why not, lets take a simple example and go over it using the substitution model (my favourite tool :)
We’ll iterate over the (list 1 2 3)
We get:
(iter (list 1 2 3) nil)
(iter (list 2 3) (list 1))
(iter (list 3) (list 4 1))
(iter () (list 9 4 1))
(list 9 4 1)
As can be seen, Louis is adding the cdr of the list to the car of the list (the answer).
If he interchanges the arguments, he gets:
(iter (list 1 2 3) nil)
(iter (list 2 3) (list nil 1))
(iter (list 3) (list nil 1 4))
(iter () (list nil 1 4 9))
(list nil 1 4 9)
Which doesn’t work, because instead of consing single elements, this algorithm conses the answer to the result of applying square. That is, (cons (list nil 1) 4). This results in:
(cons (cons nil 1) 4)
Instead of the
(cons nil (cons 1 (cons 4 (cons 9))))
that Louis wants. One solution to his dilemna would be to simply reverse the list before or after iterating over it.

Exercise 2.23

(define (my-for-each op items)
  (if (null? items)
      true
      (begin 
        (op (car items))
        (my-for-each op (cdr items)))))

Nothing upsetting here…

These exercises have been pretty easy, I think they’re designed to get people used to the basics of list manipulation. Thankfully, because of my background in python, which also has a really good list data structure, I’m not finding this stuff too difficult.

I’ve been silent for the past couple days, but not without good reason :)

I decided to finish all my solutions to the interval arithmetic exercise
before posting, because I can share as much insight as I have gained, in one
hit. ;)

In this extended exercise, we are helping Alyssa P. Hacker
(note the pun :)  to develop an interval arithmetic system for
her fellow electrical engineering compatriots.

The answers to exercises 2.7 to 2.10 are fairly clear, so here they are:

Exercise 2.7

(define (make-interval a b) (cons a b))

(define (lower-bound i) (car i))
(define (upper-bound i) (cdr i))

Exercise 2.8

(define (sub-interval x y)
(make-interval (- (lower-bound x) (lower-bound y))
(- (upper-bound x) (upper-bound y))))

Exercise 2.9

Let’s add some intervals and note the relation between the width of the
operands and the width of the result.


(define a (make-center-width 5 1))
(define b (make-center-width 10 2))
(define x (mul-interval a b))
(width x) = 3

From this it is fairly obvious that the width of the result of addition can
be described like so:
w(x*y) = w(x)+w(y)

The inverse holds true of division:
w(x/y) = w(x)-w(y)

Hmm… anyone else see the relation to logarithms?

Exercise 2.10
This one is also fairly simple.


(define (zero-span? i)
(if (and (<= (lower-bound i) 0) (>= (upper-bound i) 0))
true
false))

(define (div-interval x y)
(if (zero-span? y)
(error "Attempt to divide by an interval that spans 0")
(mul-interval x
(make-interval (/ 1.0 (upper-bound y))
(/ 1.0 (lower-bound y))))))


Exercise 2.11

To be honest, I didn’t get Ben’s cryptic comment. After reading
Eli Bendersky’s post on the topic I understood, but previously I had
gone off on a wrong tangent.

Regarding this, let me state my policy regarding my completion of these exercises. I firmly believe that cheating cheats the cheater, and while it is not necessarily cheating to check an answer to get hints, this is usually not necessary. There have been a few exercises where I have encountered a mindblock, but my advice to others is to go do something else, completely unrelated to computing or using your brain. Hop on your bike, go for a run or eat a pie, whatever works for you :) Usually when you get a mindblock it shows that you’ve been working your brain too long, too hard, and you just need to let it relax. This also happens a bit in programming, at least when you’re starting out, and in “How To Think Like A Computer Scientist” the author also suggests taking a break when you get frustrated, as this can be a source of unpleasant code and bugs.

I tend to read Eli’s posts after completing a section, because they are quite enlightening and informative. There is nothing quite like a veteran hackers view of the topic :)

This leads me to a shout out to Eli. Thanks for writing such detailed, interesting, and informative posts! I believe that, along with watching the lectures, doing the exercises and reading the book, your posts are a very complementary aid in understanding the material.

Exercise 2.12


(define (make-center-percent c p)
(make-interval (- c (* c p))
(+ c (* c p))))

(define (percent i)
(/ (- (upper-bound i)
(center i))
(center i)))


Again, this is fairly simple. The percent selector may have caused
some trouble, but it’s not too hard to figure out.

Exercise 2.13

;;Let's try:
(define a (make-center-percent 1 .1))
(define b (make-center-percent 1 .2))
(define x (* a b))
(percent x)
.294

So we can indeed see that (percent x) ~= (percent a) + (percent b)
This follows from exercise 2.9, except here we see that the percentage
is only approximate.

Exercise 2.14

To show why, we will use:


(define A (make-center-percent 8 .01))
(define B (make-center-percent 9 .05))


We will process A/A by hand, in order to see what’s going on.

(mul-interval A (make-interval (/ 1 8.08) (/ 1 7.92)))
;;p1 = .980
;;p2 = 1
;;p3 = 1
;;p4 = 1.02


The result is: (make-interval .980 1.02)
Instead of (make-interval 1 1) which you might have expected.

Let’s also do (/ A B) as suggested

;;(mul-interval A (make-interval (/ 1 9.45) (/ 1 (8.55))))
;;p1 = .838
;;p2 = .926
;;p3 = .855
;;p4 = .945


So the result is: (make-interval .838 .945) instead of the more accurate
(make-interval .855 .926)

Here’s my explanation.

Interval A/A is not an interval spanning 1 <-> 1 as we would expect in normal arithmetic, but an interval spanning .980 <-> 1.02. The width of this interval is a factor of the initial uncertainty .01, where the new uncertainty is .04. Interval A/B is also not the .855 <-> .926 that we might expect, but instead .838 <-> .945. We can see from these examples that arithmetic operations increase the innacuracy/uncertainty of the answer. The error in the answer is therefore directly related to the uncertainty in the intervals given.

Exercise 2.15

She is correct. As stated above, the amount of error in the answer is directly related to the uncertainty in the intervals given. Because there are more intervals in par1, there is a higher error in the answer. That is why par2 is a better method.

Reading Eli’s solutions to this extended exercise also gives a different view on the matter, he talks about it in terms of the fact that interval arithmetic is not a one-to-one mapping of simple numerical arithmetic.

I’ve done a few exercises from chapter 2. This chapter has been a really enlightening one for me, as I’ve learned so much about abstraction that I’ll never even realized before.

;;Exercise 2.1

(define (make-rat n d)
  (let ((n (if (< d 0)
               (- n)
               n))
        (d (if (< d 0)
               (- d)
               d)))
    (let ((g (gcd n d)))
      (cons (/ n g) (/ d g)))))

;;Exercise 2.2
This one is just a gentle exercise, get us used to using lists, car, and cdr…

;;Segment constructor and selectors
(define (make-segment a b) (cons a b))
(define (start-segment s) (car s))
(define (end-segment s) (cdr s))
;;Point constructor and selectors
(define (make-point x y) (cons x y))
(define (x-point p) (car p))
(define (y-point p) (cdr p))

;;Midpoint
(define (midpoint-segment s)
  (make-point (/ (+ (x-point (start-segment s))
                    (x-point (end-segment s)))
                 2)
              (/ (+ (y-point (start-segment s))
                    (y-point (end-segment s)))
                 2)))

;;Exercise 2.3
This exercise introduces us to making good abstractions; if we do so, changing the base representation doesn’t need to change the predefined operators.

(define (make-dim l h) (cons l h))
(define (length-dim d) (car d))
(define (height-dim d) (cdr d))

;;First implementation of make-rect.
;;Represented as a top-left corner, and a height and length
(define (make-rect top-left dim) (cons top-left dim))
(define (top-left-rect r) (car r))
(define (dim-r r) (cdr r))
(define (length-rect r) (length-dim (dim-rect r)))
(define (height-rect r) (height-dim (dim-rect r)))

;;Second implementation of make-rect
;;Implemented as a top-left and bottom-right corner
(define (make-rect top-left bottom-right) (cons top-left bottom-right))
(define (top-left-rect r) (car r))
(define (bottom-right-rect r) (cdr r))
(define (length-rect r)
  (- (point-x (bottom-right-rect r))
     (point-x (top-left-rect r))))
(define (height-rect r)
  (- (point-y (bottom-right-rect r))
     (point-y (top-left-rect r))))
     
;;Area and perimeter of either rect
(define (area-rect r)
  (* (length-rect r) (height-rect r)))
(define (perimeter-rect r)
  (+ (* (length-rect r) 2)
     (* (height-rect r) 2)))

;;Exercise 2.4

(define (cons x y) (lambda (m) (m x y)))

(define (car z) (z (lambda (p q) p)))

The complimentary definition of cdr, is of course, obtained by replacing the p with q in the lambda expression in the car definition.

(define (cdr z) (z (lambda (p q) q)))

We can see why this works, by, as suggested by the authors, applying the substitution model:
Let’s apply car to (cons 4 8)

;;(car (cons 4 8))
;;(car (lambda (m) (m 4 8)))
;;((lambda (m) (m 4 8)) (lambda (p q) p))
;;((lambda (p q) p) 4 8)
;;4

Exercise 2.5
I really enjoyed exercise 2.5 :)

I sat down for about an hour, trying various calculations before I figured out a way to get the numbers back out of the expression. Here’s the code:

(define (divisible-by-2 x)
  (if (not (integer? x))
      false
      (= (remainder x 2) 0)))

(define (divisible-by-3 x)
  (if (not (integer? x))
      false
      (= (remainder x 3) 0)))

(define (int-cons a b)
  (* (expt 2 a)
      (expt 3 b)))

(define (int-car p)
  (define (try q n)
    (if (not (divisible-by-2 q))
        n
        (try (/ q 2) (+ n 1))))
  (try (/ p 3) 0))

(define (int-cdr p)
  (define (try q n)
    (if (not (divisible-by-3 q))
        n
        (try (/ q 3) (+ n 1))))
  (try (/ p 2) 0))

This is related to a method for encoding numbers known as “Gödelization”. This method was invented/(discovered) by Kurt Gödel, a famous logician/mathematician. It encodes numbers by raising sequences of prime numbers to them, and getting the product,in much the same way we have.

eg. (4,6,9,12) would become 2⁴*3⁶*5⁹*7¹² = 315321824047781250000

I found out about this method in the book “Computational Beauty of Nature”, a really great read for anyone who’s interested in math, computation, and the amazingness of nature (it’s a great book!), not just computer scientists. Eventually, I hope to implement a Gödelization algorithm, perhaps when we begin on actual lists, and not just conses.

For Christmas, my lovely Father, and my sister Aiesha (and her boyfriend) gave me a present. That present was the book, Structure and Interpretation of Computer Programs (SICP). I really like this book, because, after about two years of trying to gain programming knowledge from reading tutorials, I am finally learning some concrete ideas. So far, I’ve managed to go through Chapter 1, with just a few hiccups. I didn’t really understand all of the math behind the calculus related stuff, and so, for example, I didn’t manage to implement differentiation through the use of Simpson’s Rule. However, I ended up getting nicely to the end of Chapter 1, and I feel fairly confident about the concepts that I’ve learned.

I like math, especially geometry, because the euphoria you experience when you solve a particularly difficult problem (relative to your skill, of course) is simply awesome. I get the same euphoria when I hack a particularly nice solution. I was very happy when I finally figured out the iterative fast exponentiation procedure, and here it is :)


;;Exercise 1.16
;;Need to define even? and square
(define (even? x) (= (remainder x 2) 0))
(define (square x) (* x x))

(define (fast-expt b n a)
(cond ((= n 0) a)
((even? n) (fast-expt (square b) (/ n 2) a))
(else (fast-expt b (- n 1) (* a b)))))


One of the great things about this book, or at least about the problems in the first chapter, is that I was able to solve most of them by hand, using just pen and paper, and my graphical calculator. It’s nice to just lie in bed, mulling over a problem, and writing out epiphanies as they come (that’s what happened in the example above). Anyway, I’m quite happy with Chapter 1, and so, onto Chapter 2!

I’ve been mucking around a lot with SSH and SCP lately, and because of that I’ve found myself logging into the wireless router regularly to check the IP adress of my computers. My router happens to support telnet, so I began using that instead of wasting time with the web browser. Of course, this is just the sort of task that is asking to be automated. So, a quick google, and I found http://docs.python.org/library/telnetlib.html.

So I sat down, and wrote some code:
#!/usr/bin/env python
#List hosts connected to router
import os, sys
import telnetlib
CMD = "dhcpserver status"
USERNAME, PASSWORD = "admin", "******"
HOST, PORT = "192.168.1.254", 23
tn = telnetlib.Telnet(HOST, PORT)
tn.read_until("Login:")
tn.write(USERNAME + "\n")
tn.read_until("Password:")
tn.write(PASSWORD + "\n")
tn.read_until("admin>")
tn.write(CMD + "\n")
print tn.read_until("admin>")

This is pretty much just  a small modification of the example given on the telnetlib page, and for some reason, it didn’t actually work. After a couple minutes, I realised why. My router happens to use “\r\n” as it’s newline character, so a simple “\n” wasn’t actually pushing the username and password through. After adding “\r” where necessary, it worked quite nicely. Here’s the final code, and an example of it’s usage.

#!/usr/bin/env python
#Print output of command run on router
import os,sys
import telnetlib
CMD = " ".join(sys.argv[1:])
USERNAME, PASSWORD = "admin", "******"
HOST, PORT = "192.168.1.254", 23
tn = telnetlib.Telnet(HOST, PORT)
tn.read_until(":")
tn.write(USERNAME + "\r\n")
tn.read_until(":")
tn.write(PASSWORD + "\r\n")
tn.read_until(">")
tn.write(CMD + "\r\n")
print tn.read_until(">")


xavieran@tranquility:~/Code$ ./info.py dhcpserver status
DHCP Server Lease Status
Interface 'QS_PPPoE'
IP address | Client UID/hw addr | Client Host Name | Expiry
----------------+---------------------+------------------+---------------
No network topology given - unconfigured
------------------------------------------------------------------------
Interface 'iplan'
IP address | Client UID/hw addr | Client Host Name | Expiry
----------------+---------------------+------------------+---------------
192.168.1.4 | 00:1b:77:59:e6:2e | Tranquility | 10 hours
192.168.1.2 | 00:1c:df:08:16:2b | Le-Chateau | 6 hours
192.168.1.7 | 00:15:af:80:ca:8d | aiesha-laptop | Expired
192.168.1.6 | 01:00:0e:35:ab:97:61| NB0928 | Expired
192.168.1.5 | 01:00:11:25:44:97:c2| NB0928 | Expired
192.168.1.1 | 01:00:26:c6:72:dd:a0| R8WNVML | Expired
192.168.1.3 | 01:00:27:13:68:08:fc| R8WNVML | Expired