1.16: The goal is to use the algorithm of fast-exp on page 45, but avoid using the recursive call as an argument to something else. The hint tells us to use an extra variable, a, which will contain part of the result. (define (fast-exp b n) (define (iter a b n) (cond ((= n 0) a) ((even? n) (iter a (square b) (/ n 2))) (else (iter (* a b) b (- n 1))))) (iter 1 b n)) We're supposed to keep the quantity a*b^n constant in all the invocations of ITER for any specific problem. If n is even, we square b and divide n by 2, so we have a * (b^2)^(n/2) which is indeed equal to a*b^n. If n is odd, we have (a * b) * b^(n-1) which is also equal to a*b^n. So each invocation does keep the overall value constant. When we get to n=0, therefore, the value of a must be the original value of b^n. It's important to pay attention to what the problem says about invariants; that's what this problem is about! 1.37: Recursive version: (define (cont-frac n d k) (define (helper i) (if (> i k) 0 (/ (n i) (+ (d i) (helper (+ i 1)))))) (helper 1)) This says that helper(1) = N(1)/[D(1)+helper(2)] helper(2) = N(2)/[D(2)+helper(3)] and so on, until we reach the Kth term: helper(K) = N(K)/[D(K)+0] In the iterative version, we first compute x = N(k)/D(k), then use that to compute N(k-1)/[D(k-1)+x], and so on until we reach the outermost fraction. Iterative version: (define (cont-frac n d k) (define (iter k result) (if (= k 0) result (iter (- k 1) (/ (n k) (+ (d k) result))))) (iter k 0)) Now for the computation of phi: (define (phi k) (/ 1 (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) k)) > (phi 12) 1.61805555555556 > (phi 13) 1.61802575107296 1.38: The numerator function is just (lambda (i) 1). The denominator function must return 1 most of the time, but one out of three times it returns a computed even number instead. (define (e k) (+ 2 (cont-frac (lambda (i) 1.0) (lambda (i) (if (= (remainder (- i 2) 3) 0) (* 2 (+ 1 (quotient (- i 2) 3))) 1)) k))) > (e 9) 2.71828358208955 2: Recursive version: (define (count-occur-r wd sent) (cond ((empty? sent) 0) ((equal? wd (first sent)) (+ 1 (count-occur-r wd (bf sent)))) (else (count-occur-r wd (bf sent))))) Iterative version: (define (count-occur-i wd sent) (define (helper wd sent total) (cond ((empty? sent) total) ((equal? wd (first sent)) (count-occur-i wd (bf sent) (+ 1 total))) (else (count-occur-i wd (bf sent) total)))) (helper wd sent 0)) In both cases, everytime you find the word in the sentence, you add 1. In the recursive version, you add one to the answer to the smaller sentence. In the iterative version, you keep passing along a running total. 3: 1+ : O(1) Adding 1 takes constant time many+ : O(n) You add 1 n number of times foo : O((2^n) * n) This is quite tricky and we got this wrong the first time around too. many+ is linear time with respect to the input. When we put ((repeat many+ n) n), that is equivalent to (many+ (many+ (many+ ... (many+ n)))) where many+ is called n times on n. However, many+ returns 2n. Thus, the first many+ takes O(n) operations, the second many+ takes O(2n) operations, the third many+ takes O(4n) operations, etc. etc. Since we apply many+ n times, the last many+ will get input 2^(n-1) * n and overall, the whole procedure takes O(2^n * n) time. bar : O(2^(2^n * n) * (2^n * n)) The first foo call will take O(2^n * n) time to finish and return the number 2^n * n. The second foo call is linear with respect to the input so the second foo call will take time O(2^(2^n * n)*(2^n * n)) where we substitute the n inside the expression O(2^n * n) with the input size (2^n * n) 4: all-pair-sum will take O(n^2). For each element in sent1, you will iterate through all elements of sent2. Is there a smarter way? Nope, because the output will always be of size n^2. So no matter how your program runs, it will still have to ouput all the pairs. 2.17: (define (last-pair lst) (if (null? (cdr lst)) lst (last-pair (cdr lst)))) Pretty self-explanatory 2.20: The easiest thing to do is to define a helper procedure that expects a list of numbers as its one argument. An advantage is that we can then separate out the first number, which is always accepted, as a special case: (define (same-parity tester . others) (define (helper numlist) (cond ((null? numlist) nil) ((equal? (even? tester) (even? (car numlist))) (cons (car numlist) (helper (cdr numlist)))) (else (helper (cdr numlist))))) (cons tester (helper others))) Once we know about higher-order functions, there's an even easier solution: (define (same-parity tester . others) (cons tester (filter (lambda (num) (equal? (even? tester) (even? num))) others))) 2.22: What's wrong with iterative square-list? I've sort of answered this already, in talking about 2.18 (iterative reverse). A list (as opposed to an arbitrary list structure) MUST be made with (cons new-member rest-of-list) and not the other way around. That's why Louis's second try fails; he's making something that isn't a list, even though he does have the members in correct left-to-right order. He gets ((((() . 1) . 4) . 9) . 16) instead of (1 4 9 16), which in dotted representation would be (1 . (4 . (9 . (16 . ())))) Louis's first try fails because he starts by consing the square of 1 onto the empty list, etc. Here's an iterative square-list: (define (square-list x) (define (iter list answer) (if (null? list) answer (iter (cdr list) (cons (square (car list)) answer)))) (reverse (iter x nil))) In this version, iter is O(n) time and O(1) space, as desired. If we use the iterative definition of reverse, it too is O(n) time and O(1) space. So the whole thing is reasonably efficient in both time and space, even though it has what seems to be a redundant pass through the list to reverse it. If you're dealing with very large lists on very small computers, this is sometimes the only way to get an answer at all. 2.24: (list 1 (list 2 (list 3 4))) The printed result is (1 (2 (3 4))). The box and pointer diagram (in which XX represents a pair, and X/ represents a pair whose cdr is the empty list): --->XX--->X/ | | | | V V 1 XX--->X/ | | | | V V 2 XX--->X/ | | | | V V 3 4 [NOTE: The use of XX to represent pairs, as above, is a less-readable form of box-and-pointer diagram, leaving out the boxes, because there's no "box" character in the ASCII character set. This is okay for diagrams done on a computer, but when you are asked to *draw* a diagram, on a midterm exam for example, you should use actual boxes, as in the text and the reader.] The tree diagram: + / \ / \ 1 + / \ / \ 2 + / \ / \ 3 4 2.26: Finger exercises. Given (define x (list 1 2 3)) (define y (list 4 5 6)) > (append x y) (1 2 3 4 5 6) > (cons x y) ((1 2 3) 4 5 6) ;; Equivalent to ((1 2 3) . (4 5 6)) but that's not how ;; it prints! > (list x y) ((1 2 3) (4 5 6)) 2.29: Mobiles. Many people find this exercise very difficult. As you'll see, the solutions are quite small and elegant when you approach the problem properly. The key is to believe in data abstraction; in this problem some procedures take a MOBILE as an argument, while others take a BRANCH as an argument. Even though both mobiles and branches are represented "below the line" as two-element lists, you won't get confused if you use the selectors consistently instead of trying to have one procedure that works for both data types. (a) Selectors. They give us the constructor (define (make-mobile left right) (list left right)) The corresponding selectors have to extract the left and right components from the constructed list: (define (left-branch mobile) (car mobile)) (define (right-branch mobile) (cadr mobile)) Note that the second element of a list is its CADR, not its CDR! Similarly, the other selectors are (define (branch-length branch) (car branch)) (define (branch-structure branch) (cadr branch)) (b) Total weight: The total weight is the sum of the weights of the two branches. The weight of a branch may be given explicitly, as a number, or may be the total-weight of a smaller mobile. (define (total-weight mobile) (+ (branch-weight (left-branch mobile)) (branch-weight (right-branch mobile)) )) (define (branch-weight branch) (let ((struct (branch-structure branch))) (if (number? struct) struct (total-weight struct) ))) The LET isn't entirely necessary, of course; we could just say (branch-structure branch) three times inside the IF. (c) Predicate for balance. It looks like we're going to need a function to compute the torque of a branch: (define (torque branch) (* (branch-length branch) (branch-weight branch) )) Here we have used the BRANCH-WEIGHT procedure from part (b) above. Now, they say a mobile is balanced if two conditions are met: The torques of its branches must be equal, and its submobiles must be balanced. (If a branch contains a weight, rather than a submobile, we don't have to check if it's balanced. This is the base case of the recursion.) (define (balanced? mobile) (and (= (torque (left-branch mobile)) (torque (right-branch mobile)) ) (balanced-branch? (left-branch mobile)) (balanced-branch? (right-branch mobile)) )) (define (balanced-branch? branch) (let ((struct (branch-structure branch))) (if (number? struct) #t (balanced? struct) ))) If you find yourself wondering why we aren't checking the sub-sub-mobiles, the ones two levels down from the one we were asked about originally, then you're missing the central point of this exercise: We are doing a tree recursion, and these procedures will check the balance of all the smaller mobiles no matter how far down in the tree structure. (d) Changing representation. We change the two constructors to use CONS instead of LIST. The only other required change is in two of the selectors: (define (right-branch mobile) (cdr mobile)) (define (branch-structure branch) (cdr branch)) We're now using CDR instead of CADR because the second component of each of these data types is stored in the cdr of a pair, rather than in the second element of a list. Nothing else changes! The procedures we wrote in parts (b) and (c) don't include any invocations of CDR or CADR or anything like that; we respected the abstraction barrier, and so nothing has to change "above the line." 2.30: The non-MAP way: (define (square-tree tree) (cond ((null? tree) '()) ((number? tree) (* tree tree)) (else (cons (square-tree (car tree)) (square-tree (cdr tree)))))) The MAP way: (define (square-tree tree) (if (number? tree) (* tree tree) (map square-tree tree))) I'm not saying more about this because we talked about these programs in lecture. See the lecture notes! But NOTE that what the book calls a "tree" in this section is what I've called a "deep list," reserving the name "tree" for an abstract data type. 2.32: subsets (define (subsets s) (if (null? s) (list nil) (let ((rest (subsets (cdr s)))) (append rest (map (LAMBDA (SET) (CONS (CAR S) SET)) rest))))) Explanation: The subsets of a set can be divided into two categories: those that include the first element and those that don't. Each of the former (including the first element) consists of one of the latter (without the first element) with the first element added. For example, the subsets of (1 2 3) are not including 1: () (2) (3) (2 3) including 1: (1) (1 2) (1 3) (1 2 3) But the "not including 1" ones are exactly the subsets of (2 3), which is the cdr of the original set. So the LET uses a recursive call to find those subsets, and we append to them the result of sticking 1 (the car of the original set) in front of each. Note: It's really important to put the recursive call in a LET argument rather than use two recursive calls, as in (append (subsets (cdr s)) (map (lambda (set) (cons (car s) set)) (subsets (cdr s)))) because that would take Theta(3^n) time, whereas the original version takes Theta(2^n) time. Both are slow, but that's a big difference. 8. ;; Step 5. (define (engelbart ls) (flatten2 ls (make-info "" 1 #t))) ;; Step 1+2. ;; THIS flatten2 is the heart of the program (define (flatten2 ls info) (cond ((null? ls) '()) ((atom? ls) (operate info ls)) (else (se (flatten2 (car ls) (car-update info)) (flatten2 (cdr ls) (cdr-update info)))))) ;; Step 3. (define (make-info label index use-num) (list label index use-num)) (define (get-label info) (car info)) (define (get-index info) (cadr info)) (define (get-use-num info) (caddr info)) (define (operate ls info) (word (get-label info) '. ls)) (define (car-update info) (make-info (update-label (get-label info) (get-index info) (get-use-num info)) 1 (not (get-use-num info)))) (define (cdr-update info) (make-info (get-label info) (+ 1 (get-index info)) (get-use-num info))) ;; Step 4. (define (update-label old-label index use-num) (if use-num (word old-label index) (word old-label (num->alpha index)))) (define alphabets 'ABCDEGFHIJKLMNOPQRSTUVWXYZ) ;; Helpers for turning number into alphabets, this is ;; NOT the important part of the program. (define (num->alpha index) (get-n-alpha index alphabets)) (define (get-n-alpha index alphas) (cond ((= index 0) (first alphas)) ((< index 27) (get-n-alpha (- index 1) (bf alphas))) (else (word (get-n-alpha (div index 26) alphas) (get-n-alpha (remainder index 26) alphas))))) (define (div dividend divisor) (if (< dividend divisor) 0 (+ 1 (div (- dividend divisor) divisor)))) (define (remainder dividend divisor) (if (< dividend divisor) dividend (remainder (- dividend divisor) divisor))) To understand this program, it's best to understand the thought process I used to write this program. The big idea in computer science: it is easier to solve many small problems than to solve one big problem. We want to eliminate details and try to solve many simpler problem; so we separate the problem into easier steps. Step 1. A highly related but easier task is to simply flatten a deep-list into a sentence so '((1 (2)) 3) becomes '(1 2 3). That can be done with (define (flatten ls) (cond ((null? ls) '()) ((atom? ls) ls) (else (se (flatten (car ls)) (flatten (cdr ls)))))) This flatten procedure is the critical part of the program. Now, all we need to do is to attach a prefix to every element in the list. Step 2. Each prefix require some information to create. Thus, we give our flatten procedure an extra variable to carry the information. These information must be updated at every recursive call. So we can generalize the flatten procedure as such: (define (flatten2 ls info) (cond ((null? ls) '()) ((atom? ls) (operate info ls)) (else (se (flatten2 (car ls) (car-update info)) (flatten2 (cdr ls) (cdr-update info)))))) Step 3. Now we have to determine what information we need and how to update it. We have some flexibility in deciding what information to include. I use the following: information will have 1) the current label, 2) the index of the current element, 3) whether we should use number or letter for the NEXT level So, we will think of the info as an ADT implemented as a list of those three elements and now we can define the operate and update procedures. However, the one caveat is that when we are doing the car-update on the information, we must update the label also. Let's assume we have a procedure for doing that already call "update-label" ;; info ADT implementations (define (make-info label index use-num) (list label index use-num)) (define (get-label info) (car info)) (define (get-index info) (cadr info)) (define (get-use-num info) (caddr info)) ;; operate, update (define (operate ls info) (word (get-label info) '. ls)) (define (car-update info) (make-info (update-label (get-label info) (get-index info) (get-use-num info)) 1 (not (get-use-num info)))) (define (cdr-update info) (make-info (get-label info) (+ 1 (get-index info)) (get-use-num info))) Step 4. All we have to do now is to define update-label. The hardest part of this procedure is to get letters to act as numbers. I must emphasize again however that this is NOT the important part of this program. (define (update-label old-label index use-num) (if use-num (word old-label index) (word old-label (num->alpha index)))) (define alphabets 'ABCDEGFHIJKLMNOPQRSTUVWXYZ) (define (num->alpha index) (get-n-alpha index alphabets)) (define (get-n-alpha index alphas) (cond ((= index 0) (first alphas)) ((< index 27) (get-n-alpha (- index 1) (bf alphas))) (else (word (get-n-alpha (div index 26) alphas) (get-n-alpha (remainder index 26) alphas))))) (define (div dividend divisor) (if (< dividend divisor) 0 (+ 1 (div (- dividend divisor) divisor)))) (define (remainder dividend divisor) (if (< dividend divisor) dividend (remainder (- dividend divisor) divisor))) Step 5. Now we are ready to make our final engelbart call (define (engelbart ls) (flatten2 ls (make-info "" 1 #t))) === Side Note: Experience programmers will skip many of the steps we described here in their code and get something like this: (define (engelbart ls) (engelbart-helper ls "" 1 #t)) (define (engelbart-helper ls old-label index num-phase) (cond ((null? ls) '()) ((atom? ls) (word old-label '. ls)) (else (se (engelbart-helper (car ls) (update-label old-label index num-phase) 1 (not num-phase)) (engelbart-helper (cdr ls) old-label (+ 1 index) num-phase))))) (define (update-label old-label index num-phase) (if num-phase (word old-label index) (word old-label (num->alpha index)))) (define alphabets 'ABCDEGFHIJKLMNOPQRSTUVWXYZ) (define (num->alpha index) (get-n-alpha index alphabets)) (define (get-n-alpha index alphas) (cond ((= index 0) (first alphas)) ((< index 27) (get-n-alpha (- index 1) (bf alphas))) (else (word (get-n-alpha (div index 26) alphas) (get-n-alpha (remainder index 26) alphas))))) (define (div dividend divisor) (if (< dividend divisor) 0 (+ 1 (div (- dividend divisor) divisor)))) (define (remainder dividend divisor) (if (< dividend divisor) dividend (remainder (- dividend divisor) divisor))) However, the thought process is still the same. The program above, though short, is harder to understand, debug, and modify.