Week 5 Discussion/Lab Notes

Administrivia

• Project 2 is due Tuesday (2-22). It does not require a transcript.
• Midterm 1 is on Wednesday (2-23). Remember that it's a week later than usual this semester, so it will cover a bit more material than in past semesters.
• This coming Monday (2-21) is a holiday, so Lab 6 will be optional. If you decide to do it, feel free to e-mail me your answers anytime next week for credit.
• I'll devote at least half of discussion next week to answering any eleventh hour questions.

Discussion Outline

• redundant code
• (if pred #t #f)
• (equal? pred #t)
• (lambda (x) (car x))
• lab5
• 2.55 (car ''abracadabra)
  • is quote a special form?
• 2.28 deep-reverse
• hw5
• 2.29 mobiles
• DAV errors
• 2.54 equal?
• arguments might not be lists
• check if something is a pair before taking its car/cdr
• more box-and-pointer examples
• pointer equality vs. value equality
• eq? : equal? :: memq : member
• trees
• depth
• binary trees
• searching
• post-order, pre-order, in-order traversals
• tree-recursion
• trees are well suited for recursion
• subtrees = subproblems
• two common base cases
• examples
• count-change
• mergesort

Pointers

If you're an experienced C programmer, you probably know all about pointers already and can probably skip reading this part. If not...

A pointer is a basically a memory address; it is a reference to some location in the computer's memory to some piece of data.

Whenever we call cons, we create a new pair structure in memory. The return value of cons is a pointer to that structure--the memory address where that structure is located.

(This applies whenever we create pairs, whether by cons, list, creating quoted lists, etc.. The pairs have to be located somewhere in memory. How can we access them? We locate them using pointers.)

This is one reason why the initial arrow to a box-and-pointer diagram is important. It represents the pointer that's returned form calling cons (or list, etc.) and is our starting point. (If you think that it's pretty obvious where the starting point is anyway, this necessity will become clearer during week 9.)

Knowing this, what happens when we say: (define x (cons 'a 'b))? This means: create a pair and bind its memory address to the variable x. Thus, x becomes a pointer to that pair.

Pointer Equality versus Value Equality

As their names imply: Pointer equality checks if two things point to the same location in memory. Value equality checks if two things have the same value.

For example, most people call me James. A few people call me Jimmy. Do they refer to the same person? Yes. They're just two different names for the same physical entity. That's what pointer equality is all about.

Another example: I make 30 photocopies of a quiz. Are they the same? The copies aren't physically the same, but they all have the same content. That's what value equality is all about.

We sometimes call the notion of pointer equality as being shallow (we don't have to do much work to determine if two things are pointing to the same memory address) and valuel equality as being deep (we do have to do some footwork to figure out if two things have the same values in the same structure).

In Scheme, we have a procedure eq? that checks for pointer equality, and a procedure equal? that checks for value equality. Some examples:

   > (eq? '(a b) '(a b)) ;; whenever we use cons, list, or create a
   #f                    ;; quoted list, we create a new structure
                         ;; in memory

   > (equal? '(a b) '(a b))
   #t

   > (define foo '(a b))
   > (define bar foo)    ;; two different names for the same thing
   > (eq? foo bar)
   #t

Would we ever want to use eq? instead of equal?? Actually, yes, for some situations. Again, more on this in week 9. Generally, keep in mind what kind of equality testing you want to perform and use the appropriate procedure.

Trees

I assume everyone knows what a tree is. I also everyone knows what a balanced tree is (even if I obviously can't explain it). Moving along...

The fundamental property of a balanced tree is that the depth is proportional to log N, where N is the number of nodes in the tree. This is useful in algorithms such as binary search; given a binary search tree we can easily determine if the tree has a certain value in Theta(log N) time.

There are three ways we can traverse a tree:

• pre-order: visit the current node first, then perform a pre-order traversal on each of the children (conventionally done in left-to-right order)
• post-order: perform a post-order traversal on each of the children, then visit the current node
• in-order (binary trees only): perform an in-order traversal on the left child, visit the current node, then perform an in-order traversal on the right child

Knowing these isn't too important for this class (you'll see much more of them in 61B), but you should know the differences anyway, just in case.

Using the tree above, what are the pre-, post-, and in-order traversals?

Answer:
Pre: ABDECFG
Post: DEBFGCA
In: DBEAFCG

Note that the post-order traversal is not merely the pre-order traversal backwards. (Why not?)

Tree Recursion

Trees lend themselves very well to recursion. Every child of a tree is the root of another tree. Subtrees are like subproblems; subtrees have the same structure as the original tree, just as subproblems in a recursive process have the same structure as the original problem. That's what recursion is all about: breaking a problem into smaller, similar subproblems. Eventually you can't break the problem up any more (the base case(s)), which is like reaching the leaves of a tree.

A tree recursive procedure is one in which we recursively call the procedure more than once during each loop.

There are typically (but not always) two base cases for tree recursive procedures:

1. are there any trees left to handle? This is often (null? ...)
2. are we at a leaf? This is often (not (pair? ...))

The order of the base cases can be important (e.g. the cc procedure for count-change). Remember, the empty list is not a pair! It can satisfy both of those cases, so be careful.

Exercise: Write a procedure flatten that takes an ordered binary tree (each left child contains only values less than that of the parent; each right child contains only values greater than that of the parent) as its argument and returns a list of all the elements in increasing order. At your disposal you have the predicate leaf? and tree selectors datum, left-branch, and right-branch.

The tree is not necessarily balanced. A missing branch will be represented with a false value #f.

(Hijacked without permission from Wilson Cheung's discussion notes.)