Overview

• We do a quick overview of the quiz.
• You ask questions about the exam, I attempt to answer.
• You ask questions about quiz and recent concepts, I attempt to answer.
• We talk about the forthcoming quiz.

About the Quiz

Main topics:

• Pairs and pair structures.
• Trees.
• Deep recursion (recursion over trees): Key idea: Recurr over both the car and the cdr.
• Vectors (maybe)

Likely quiz questions:

• Interpret this code.
• Finish writing this code that is supposed to accomplish this task.
• Correct this code.
• Draw this expression.

Your Questions: Exam

Your Questions: Quiz (Pairs, Trees, Etc.)

Can we go over deep recursion a bit?

    (define ccc
      (lambda (t)
        (if (pair? t)
            (+ 1
               (ccc (car t))
               (ccc (cdr t)))
            0)))

    > (ccc (cons (cons (cons 6 1)
                       7)
            (cons (cons 1 9)
                  6)))
    5

Counts the number of pairs in a pair structure

Should we solve this by drawing out the tree or ...?

For some, drawing out the tree is good.

For others, working through the steps is good

    > (ccc (cons (cons (cons 6 1) 7) (cons (cons 1 9) 6)))
    > (+ 1 (ccc (cons (cons 6 1) 7)) (ccc (cons (cons 1 9) 6)))
    > (+ 1 (+ 1 (ccc (cons 6 1)) (ccc 7)) (ccc (cons (cons 1 9) 6)))
    ...

You might also try a smaller example.

On the exam, you may have to generate your own examples (problem 6?)

On the exam, you can also try running it.

What's the difference between a pair and a list?

Nonempty lists are composed of pairs. (That's why pairs are in Scheme.)

But we can build non-lists with pairs. For a pair structure to be a list, all the cdrs of the top-level elements have to be lists (either a pair that is a list or null)

We don't care whether the pairs within a list are themselves lists, only the "spine".

Can you draw (cons null (cons null null))

Yes, but only on the whiteboard.

When do you draw pair structures going across and when going downward?

If you're thinking about them as lists, draw across.

If you're thinking about them as trees, draw down.

But either is correct.

How do we recursively build a tree?

It depends a bit on the tree you want to build.

    (define build-tree
      (lambda (info)
        (if (simple? info)
            simple-tree
            (cons (build-tree (simplify1 info))
                  (build-tree (simplify2 info))))))

We have to write simple?, simple-tree, simplify1, and simplify2.

Color tree for an image

    ; Build a tree that describes the vertical segments of a
    ; tree
    (define build-color-tree
      (lambda (image left top width height)
        (if (most-of-the-pixels-are-the-same image left top width height)
            (color-of-the-pixels image left top width height)
            (cons (build-color-tree image left top (/ width 2) heihgt)
                  (build-color-tree image (+ left  (/ width 2))
                                          top (/ width 2) height)))))

Are vectors on the quiz?

Potentially.

Can we do the vector-rotate! problem from the extras?

Goal: Procedure that shifts everything left 1, moves leftmost value to the end.

Strategy:

    ; 1. Remember the leftmost value for using at the end
    ; 2. Recurse through the positions, moving things left
    ; 3. Put that stored value at the end.

    (define vector-rotate!
      (lambda (vec)
        (let ([save (vector-ref vec 0)]
              [last-index (- (vector-length vec) 1)])
          (let kernel ([i 0])
            (when (< i last-index)
               (vector-set! vec i (vector-ref vec (+ i 1)))
               (kernel (+ i 1))))
          (vector-set! vec last-index save))))

Sample Quiz Questions, Revisited

Draw '(1 2 3 . 4)

Draw '(1 (2 . 3) 4)

Draw '(1 (2 . 3) . 4)

Draw '(1 ((2 . 3) . 4))

Fill in the blanks in the following to get a working version of vector-rotate!

    (define vector-rotate!
      (lambda (vec)
        (let ([save _____________________]
              [last-index (- (vector-length vec) 1)])
          (let kernel ([i 0])
            (when (< i last-index)
               (vector-set! vec i _______________________)
               (kernel (+ i 1))))
          (vector-set! vec last-index save))))