CS61A Summer 2011                        Homework 5

Topic:  Hierarchical data

Reading: Abelson & Sussman, Section 2.2.2--2.2.3, 2.3.1, 2.3.3


Some of these exercises are harder than they look; don’t give up in frustration if your early attempts fail.


Abelson & Sussman,  exercises 2.24 (you can submit a jpg file or a pdf with your homework), 2.26

Good tree recursion practice: (Not a warm-up)

Abelson & Sussman,  exercises 2.30, 2.31, (Optional) 2.54

[Hint: Basically for 2.30: Define square-tree two ways: one using HOFs and one without using HOFs]

Mobiles (The answers should be short (but will take a long time)! HINT: Trust the abstraction!)

Abelson & Sussman,  exercise 2.29

[Hint: in case you’re not familiar with torque you can use the following helper functions in your code:

(define (torque branch)

 (* (branch-length branch)

     (branch-weight branch) ))



Abelson & Sussman,  exercises 2.36, 2.38

Examples and Applications (Optional)

Abelson & Sussman,  exercises (Optional) 2.32, (Optional) 2.37

Dessert - calc (don’t try these until you understand how the calc program works)

Extend the calculator program from lecture to include words as data, providing the operations first, butfirst, last, butlast, and word. Unlike Scheme, your calculator should treat words as self-evaluating expressions except when seen as the operator of a compound expression. That is, it should work like these examples:

calc: foo


calc: (first foo)


calc: (first (butfirst hello))


The program  is in ~cs61a/lib/calc.scm

Extra for experts:

Read section 2.3.4 and do exercises 2.67–2.72.

Programming by example: In some programming systems, instead of writing an algorithm, you give examples of how you’d like the program to behave, and the language figures out the algorithm itself:

> (define pairup (regroup ’((1 2) (3 4) ...)))

> (pairup ’(the rain in spain stays mainly on the plain))

 ((the rain) (in spain) (stays mainly) (on the))

Write regroup.  Read ~cs61a/lib/regroup.problem for details.


Unix feature of the week: head, tail, more, cat


Emacs feature of the week: M-x search-forward-regexp, M-xquery-replace-regexp