Work, sicp, and management

Sometimes priorities have to kick in.

The reality of most workplaces is that management can be frustrating. So I'm putting sicp to the side for a week while I read up on management... In Japanese, courtesy of P.F.Druckers "Management"

Why in Japanese? One reason is that it meant I could pick it up straight away at the bookstore.
But more than that, by learning these concepts in Japanese, I hope to be able to also communicate them to coworkers and... managers.

This being said, I have no intent to stop at Drucker. I already have a preconceived notion against one of his principles, that of "management by objectives". While on paper it is a good and motivational idea, my experience of it as a software engineer is receiving objectives I have little to no ability to control(such as sales figures) or that are plainly delusional(timelines set by people with little experience of developing complex systems).

Should time be on my side, I hope to be able to put together notes of my thoughts in this blog for later perusing. After that I hope to work through Deming's Out of the crisis" which should include his 14 points.

Hopefully in a couple more weeks things at work can settle down and I can focus more on what I want to be doing rather than what I need to do to be able to do what I want to do in the future.

Busy week

I really wanted to get a lot more done this week, but final result is that still not done with chapter 2.2

Getting started during a holiday at least helped get some speed... Now I need another to maintain it.

Here's 2.41 just for the hell of it

(define (triples n)
    (flatmap (lambda (i)
               (map (lambda (j) (cons i j))
                    (unique-pairs (- i 1))))
             (enumerate-interval 1 n)))
(define (s-triples target max)
    (filter (lambda (x) (= target (accumulate + 0 x))) (triples max)))

Also some definitions that might be needed:

(define (unique-pairs n)
    (flatmap (lambda (i)
               (map (lambda (j) (list i j))
                    (enumerate-interval 1 (- i 1))))
               (enumerate-interval 1 n)))

(define (enumerate-interval start n)
    (define (enumerate x)
      (if (< n x)
          null
          (cons x (enumerate (+ 1 x)))))
    (enumerate start))

(define (filter predicate sequence)
  (cond ((null? sequence) null)
        ((predicate (car sequence))
         (cons (car sequence)
               (filter predicate (cdr sequence))))
        (else (filter predicate (cdr sequence)))))

Progress slowing down

A couple of hours and only managed to get 3 exercises done cleanly today... Bad day perhaps? Getting easily distracted. Solution to 2.35 just because it's really cool:

count-leaves as an accumulation:

(define (count-leaves t)
   (accumulate + 0 (map (lambda (x)
                          (if (pair? x)
                              (count-leaves x)
                              1))
                        t)))

And for reference, accumulate is:

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

Also an alternative map function from one of the other exercises:

(define (map p sequence)
    (accumulate (lambda (x y) (cons (p x) y)) nil sequence))

Mind-bending, but fun stuff.

Edit: well, I was going to sleep, but the next exercise looked interesting too, so I figured it out much quicker(finally getting the hang of using lambda?!)

sicp exercise 3.36:

(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      null
      (cons (accumulate op init (accumulate (lambda (x y) (cons (car x) y)) null seqs))
            (accumulate-n op init (accumulate (lambda (x y) (cons (cdr x) y)) null seqs)))))

Week 2 results

Finished up section 2.1 and working away through section 2.2, a long one.
I generally found section one tougher, probably just because the mathematical proofs which it's been a while since I did.

Next week there's no more golden week holidays so I'm just going to make sure I at least finish up 2.2, and if possible get some progress into 2.3

2.13

Pardon the lazy formatting(time spent writing blog = time not spent figuring stuff out!)

I've been using Ken's answers to check mine but unfortunately it turned out his answer for 2.13 was wrong(upon checking against real numbers). 
The resultant tolerance of two intervals is going to be

tab=(ta+tb)/(1+ta*tb)


Edit: as it turns out, the question is "Assuming small tolerances". Which means that ta*tb is close to 0 or negligible, which would of course mean that 
tab = ta + tb

I still think the way I figured it should be easier to follow so I'm going to leave this up

You can check it by just making a couple of intervals using the procedure from exercise 2.12, multiplying them and getting the percent:
> (define a (make-center-percent 10 20))
> (define b (make-center-percent 25 5)
> a
(8 . 12)
> b
(23 3/4 . 26 1/4)
> (define ab (mul-interval a b))
> ab
(190 . 315)
> (percent ab)
24 76/101

so we have 20 and 5 -> 24 76/101

(0.2+0.5)/(1+0.2*0.05)
->0.24752475247524752475247524752475


Here's what I figured for  exercise 2.13:

So long as percentage not over 100% All numbers stay +

int1 * int2
Result is:

lower: a-min * b-min               
upper: a-max * b-max

tolerance1 = (a-max - a-min)/2 / (a-max - (a-max-a-min)/2)
lets call (a-max - a-min)/2 the "variance"

tolerance = variance/(int-max - variance)

in resultant interval ab the interval is

(a-min * b-min   ,  a-max * b-max)

the variance is thus
(a-max*b-max - a-min*b-min)/2

and tolerance is 
((a-max*b-max - a-min*b-min)/2)  /  (a-max*b-max - ((a-max*b-max - a-min*b-min)/2)))


We can also say
a-max = center-a * (1+tolerance-a)
a-min = center-b * (1-tolerance-a)


So tolerance a*b is:

calling tolerance-a=ta  and tolerance-b=tb for simplicity

(removing center-a*center-b as everything shares it
((1+tolerance-a) * (1+tb) - (1-ta) * (1-tb) / 2)         /
       (1+ta) * (1+tb) - ((1+ta) * (1+tb) - (1-ta) * (1-tb) / 2))

just analyzing the top pert we get:

((1+ta) * (1+tb) - (1-ta) * (1-tb) / 2)

=> ((1 - 1) + (ta*tb - ta*tb) + ta + tb + ta + tb) /2
=> ta + tb

substituting back to full equation:

ta+tb / ((1+ta+tb+ta*tb) - (ta+tb))

=> ta+tb / (1+ta*tb)

Sicp exercise 2.11

I have no intention of posting all my solutions since I would prefer to spend the time figuring them out and studying over making them look pretty and understandable...
Anyone looking for solutions should check out one of the many other blogs that have solved this issue, such as Ken Dyck's
or (in progress) Bill the Lizard



That being said, my solution to exercise 2.11 is pretty convoluted, and I'm not too happy with Kens one either... If you have suggestion, comment!

(define (int-type x)
    (cond ((> (lower-bound x) 0) 1)
          ((< (upper-bound x) 0) -1)
          (else 0)))

(define (mul-interval x y)
    (let ((x-type (int-type x))
          (y-type (int-type y)))
      (cond ((and (= x-type 1) (= y-type 1))
             (make-interval (* (lower-bound x) (lower-bound y))
                            (* (upper-bound x) (upper-bound y))))
            ((and (= x-type 1) (= y-type 0))
             (make-interval (* (upper-bound x) (lower-bound y))
                            (* (upper-bound x) (upper-bound y))))
            ((and (= x-type 1) (= y-type -1))
             (make-interval (* (upper-bound x) (lower-bound y))
                            (* (lower-bound x) (upper-bound y))))
            ((and (= x-type 0) (= y-type 1))
             (make-interval (* (lower-bound x) (upper-bound y))
                            (* (upper-bound x) (upper-bound y))))
            ((and (= x-type 0) (= y-type 0))
             (let ((p1 (* (lower-bound x) (lower-bound y)))
                   (p2 (* (lower-bound x) (upper-bound y)))
                   (p3 (* (upper-bound x) (lower-bound y)))
                   (p4 (* (upper-bound x) (upper-bound y))))
               (make-interval (min p1 p2 p3 p4)
                              (max p1 p2 p3 p4))))
            ((and (= x-type 0) (= y-type -1))
             (make-interval (* (upper-bound x) (lower-bound y))
                            (* (lower-bound x) (lower-bound y))))
            ((and (= x-type -1) (= y-type 1))
             (make-interval (* (lower-bound x) (upper-bound y))
                            (* (upper-bound x) (lower-bound y))))
            ((and (= x-type -1) (= y-type 0))
             (make-interval (* (lower-bound x) (upper-bound y))
                            (* (lower-bound x) (lower-bound y))))
            ((and (= x-type -1) (= y-type -1))
             (make-interval (* (upper-bound x) (upper-bound y))
                            (* (lower-bound x) (lower-bound y))))
            (else (error "This shouldn't happen!")))))

Week 2

Going to get cracking on section 2 sicp, but take my time so I can catch up on some of the lecture notes and videos that I had to pass just to get through the content of the book.

Completing 2.1 is definite, with spare time it'd be good to get 2.2 done as well

Section 1: done

I certainly set a high bar for the first week and barely scraped through.

I also cheated slightly by skipping a couple of exercises (1.45 which I was just too tired to experiment with, and one of the math proofs)

Here's my programs for the final exercise

1.46:
(define (iterative-improve good-enough improve)
    (lambda (guess)
      (define (iter new-guess)
        (if (good-enough new-guess)
            new-guess
            (iter (improve new-guess))))
      (iter guess)))

(define (sqrt x)
    (define (good-enough guess)
      (display guess)
      (newline)
      (if (< (abs (- (square guess) x))
             0.001)
          true
          false))
    (define (improve guess)
      (average guess (/ x guess)))
    ((iterative-improve good-enough improve) x))

for fixed point:

(define (fixed-point f)
    (define tolerance 0.00001)
    (define (good-enough guess)
      (let ((new-guess (f guess)))
        (if (< (abs (- new-guess guess)) tolerance)
            true
            false)))
    (define (improve guess)
      ((average-damp f) guess))
    (iterative-improve good-enough improve))

(define (average-damp f)
    (lambda (x) (average x (f x))))

> ((fixed-point cos) 1.0)
0.7390885809390573
> (define (fixed-sqrt x)
    ((fixed-point (lambda (y) (/ x y)))
                  1.0))
> (fixed-sqrt 10)
3.162277665175675

It's been enjoyable, but considering the quantity of exercises, I really had to barge through it. I'm going to take the next week easier so I can review some of the lectures.

Posting next sundays target tomorrow.

Deadline approaching

Welp, I've cleared all the exercises up to and including 1.39

One subsection of 1.3 remains.

But before hitting that, I have to say I am impressed with scheme.

Procedures that return dynamically generated procedures!? That's just awesome. I've heard that MIT actually took scheme off the curriculum last year, which is a real pity. There's no doubt this stuff is difficult. Mapping out in my head how I'm going to put down an iterative process where each step depends on the previous step is interesting. The moment of realizing the solution is awesome.

In this particular case I'm referring to the iterative solution of 1.37: it involves implementing a function to calculate the k-term finite continued fraction and can be found here: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-12.html#%_sec_1.3

My solution:

N and D are procedures that should return the nth operands.

start at the end(where we have Nk/Dk), work backwards.

(define (cont-frac-iter n d k)
    (define (iter a result)
      (if (< a 0)
          result
          (iter (- a 1) (/(n a) (+ (d a) result)))))
    (iter k 0))

I don't think I'd use it for actual projects unless there are some far better tools and libraries out there. But while I was pretty confident in my programming abilities, this is making me think of all kind of fresh things. Awesome book.