Stop learning alone!

Learn faster and stay on-track by joining this free class with other self-learners.

Register for Structure and Interpretation of Computer Programs now.

Structure and Interpretation of Computer Programs

Class length: 13 weeks. Start anytime.

Creator: kday

Status: Established

 Join this class!
Lesson 11: Modeling with Mutable Data » Assignment 1

Lesson 11: Assignment 1

Do the odd problems in section 3.3 of SICP. Total of 12 problems.

Homework Submissions

1 total

bhrgunatha (Self-grade: Pretty good)
Submitted 1 year ago | Permalink

3.13

Diagram Try to execute (last-pair z) will never return.

3.15

Diagram

3.17

See below

3.19

This is an old interview question. See below.

3.21

The queue is actually a pair of pointers - to the start and end of the queue - the actual items in the queue are in the list in the car of the queue itself. See below for print-queue.

3.23

See below

3.25

See below

3.27

Since memo-fib only calculates each (fib k) once and saves the result in its table, each call to (fib k) is constant (assuming a table structure has constant lookup time – for example a hash table.) In the memo-fib call tree each value of k is calculated (and saved) while evaluating the first branch of the tree, and so when evaluating the second branch of the tree, the result will already be available and so is constant. Looking at the call tree for the first branch show that the first actual value to be calculated at the leaf level (and stored in the table) is (fib 1) – which is constant. Next is (fib 0), which is also constant. After that comes (fib 2) which is now constant due to (fib 1) and (fib 0) being in the table… and so on until we reach the root of the tree. Since each step has been constant the result is therefore O(n). Of course, this is the best case where the table used for storing values has constant lookup time. So far the book has only introduced tree structures which has growth O(logn), but by choosing something like a hash-table we can get very close to constant time.

3.29

x?y = ¬(¬x ? ¬y) see below for code. Since the signals on a1 and a2 can be set simultaneously the resulting signals inverting both will both be set simultaneously i.e. after the delay of inverter. The overall delay or-gate-delay = and-gate-delay + 2 inverter-delay

3.31

When adding the action to the wire, without executing the procedure immediately the system would never actually start – nothing would be added to the agenda, no actions would occur and no signals would propagate.

3.33

See below

3.35

See below

3.37

See below

;; Exercise 3.17
(define count-pairs
  (let ((seen null))
    (lambda (x)
      (cond ((not (pair? x)) 0)
            ((memq x seen) 0)
            (else (set! seen (cons x seen))
                  (+ (count-pairs (car x))
                     (count-pairs (cdr x))
                     1))))))


;; Exercise 3.19
(define (has-cycle? xs)
  (define (seen-last-pair? x)
    (or (null? x) (null? (cdr x))))
  (define (chase turtle rabbit)
    (cond ((or (null? turtle) (null? rabbit)) #f)
           ((eq? (car turtle) (car rabbit)) #t)
           ((seen-last-pair? (cdr rabbit)) #f)
           (else (chase (cdr turtle) (cddr rabbit)))))
  (if (seen-last-pair? xs)
      #f
      (chase xs (cdr xs))))


;; Exercise 3.21
(define (print-queue q)
  (display (front-ptr q))
  (newline))


;; Exercise 3.23
(define (make-deque)
  (define front null)
  (define rear null)

  (define (set-front! item) (set! front item))
  (define (set-rear! item)  (set! rear item))
  (define (empty-deque?) (null? front))
  (define (insert-front! item)
    (let ((new-front (cons (cons item null) front)))
      (cond ((empty-deque?) (set-front! new-front)
                            (set-rear!  new-front)
                            dispatch)
            (else (set-cdr! (car front) new-front)
                  (set-front! new-front)
                  dispatch))))
  (define (insert-rear! item)
    (let ((new-rear (cons (cons item rear) null)))
      (cond ((empty-deque?) (set-front! new-rear)
                            (set-rear!  new-rear)
                            dispatch)
            (else (set-cdr! rear new-rear)
                  (set-rear! new-rear)
                  dispatch))))
  (define (delete-front!)
    (cond ((empty-deque?) (error "DELETE-FRONT! called on empty queue" front))
          (else (set-front! (cdr front))
                (unless (empty-deque?)
                  (set-cdr!  (car front) null))
                dispatch)))
  (define (delete-rear!)
    (cond ((empty-deque?) (error "DELETE-REAR! called on empty queue" front))
          (else (set-rear! (cdar rear))
                (if (null? rear)
                    (set-front! null)
                    (set-cdr! rear null))
                dispatch)))
  (define (print-queue)
    (define (print-end) (display ")") (newline))
    (display "(")
    (let print-next ((next front))
      (cond ((null? next) (print-end))
            ((null? (cdr next)) (display (caar next))
                                 (print-end))
            (else (display (caar next))
                  (display " ")
                  (print-next (cdr next))))))
  (define (dispatch m)
    (cond ((eq? m 'insert-front!) insert-front!)
          ((eq? m 'insert-rear!)  insert-rear!)
          ((eq? m 'delete-front!) (delete-front!))
          ((eq? m 'delete-rear!)  (delete-rear!))
          ((eq? m 'front)         front)
          ((eq? m 'rear)          rear)
          ((eq? m 'print)         (print-queue))
          (else (error "DEQUEUE -- Unknown instruction" m))))
  dispatch)


;; Exercise 3.25
(define (make-table)
  (define local-table (list '*table*))

  (define (assoc key records)
    (cond ((null? records) #f)
          ((equal? key (caar records)) (car records))
          (else (assoc key (cdr records)))))

  (define (lookup keys)
    (let ((record (assoc keys (cdr local-table))))
      (if record
          (cdr record)
          #f)))

  (define (insert! keys value)
    (let ((record (assoc keys (cdr local-table))))
      (if record
          (set-cdr! record value)
          (set-cdr! local-table (cons (cons keys value) (cdr local-table))))))

  (define (dispatch m)
    (cond ((eq? m 'lookup) lookup)
          ((eq? m 'insert!) insert!)
          (else (error "Unknown operation -- TABLE" m))))
  dispatch)


;; Exercise 3.29
(define (or-gate a1 a2 output)
  (define (or-action-procedure)
    (let ((~a1 (make-wire))
          (~a2 (make-wire))
          (~a1^~a2 (make-wire)))
      (inverter a1 ~a1)
      (inverter a2 ~a2)
      (and-gate ~a1 ~a2 ~a1^~a2)
      (inverter ~a1^~a2 output)))
  (add-action! a1 or-action-procedure)
  (add-action! a2 or-action-procedure)
  'ok)


;; Exercise 3.33
(define (averager a b average)
  (let ((summed (make-connector))
        (two (make-connector)))
    (constant 2 two)
    (adder a b summed)
    (multiplier two average summed)))

;; Exercise 3.35
(define (squarer a b)
  (define (process-new-value)
    (if (has-value? b)
        (if (< (get-value b) 0)
            (error "square less than 0 -- SQUARER" (get-value b))
            (set-value! a (sqrt (get-value b)) me))
        (set-value! b (* (get-value a) (get-value a)) me)))
  (define (process-forget-value) 
    (forget-value! a me)
    (forget-value! b me)
    (process-new-value))
  (define (me request) 
    (cond ((eq? request 'I-have-a-value)
           (process-new-value))
          ((eq? request 'I-lost-my-value)
           (process-forget-value))
          (else
           (error "Unknown request -- SQUARER" request))))
  (connect a me)
  (connect b me)
  me)


;; Exercise 3.37
(define (c+ x y)
  (let ((z (make-connector)))
    (adder x y z)
    z))

(define (c* x y)
  (let ((z (make-connector)))
    (multiplier x y z)
    z))

(define (c/ x y)
  (let ((z (make-connector)))
    (multiplier z y x)
    z))

(define (c- x y)
  (let ((z (make-connector)))
    (multiplier z y x)
    z))

(define (cv x)
  (let ((z (make-connector)))
    (constant x z)
    z))

(define (celsius-fahrenheit-converter x)
  (c+ (c* (c/ (cv 9) (cv 5))
          x)
      (cv 32)))
Back to top

No comments. Sign up or log in to comment