## CS 307: Study Guide for Exam 2

### All Material on Exam 1 Study Guide is Included for This Exam.

Hailperin, Chapter 8.

### Assignment:

Run at least two of the exam2 lessons on the Scheme Tutor; print out your results and hand them in on the day of the exam. The Tutor contains previous exam questions to help you to prepare for the exam.

### Lisp Topics:

• Recursion over binary trees.
• Destructive operations on lists.

### Lisp Functions:

You should know the following Lisp functions. Be able to give the result for a simple call to each function.
• Control:
```dotimes   dolist   while   every   some   map   for-each
```
• Special:
```eval    apply    lambda
```
• List Structure: Combinations of car and cdr.
```assoc      assq      assv      list-tail    list-ref
copy-tree  subst     sublis    set-car!     set-cdr!
nconc      nreverse
```
• Sets:
```subset?    intersection    union    set-difference    subset
```
• Predicates and Logical:
```string?           list?             vector?      char?
char-alphabetic?  char-numeric?     char=?       char<=?
char-lower-case?  char-whitespace?  char?
char-upper-case?  char>=?           char-ci=?    char-ci?         char-ci<=?        char-ci>=?   string=?
string?          string<=?    string>=?
string-ci=?       string-ci?  string-ci<=?
string-ci>=?
```
• Vectors, Characters, Strings:
```make-vector      vector          vector-ref      vector-set!
vector-length    vector->list    list->vector    vector-fill
char-upcase      char-downcase   char->integer   integer->char
make-string      string-length   string          string-ref
string-set!      string->list    list->string    string-fill!
string-copy      substring
```

### Programming:

Write Scheme programs for each of these:
• Given as input a list structure (tree) containing some numbers (and possibly other things), write a function to add up the cubes of all the numbers.
• Write a function (count lst tree) that will count the number of occurrences of items in the list lst in the list structure tree. The items in list lst will be simple items such as symbols, numbers, or boolean values. Example:
```   (count '(a 3) '((b 3 a) (c 3 (7 a))))  =  4
```
• Write a function that will return the sum of the even numbers in a list structure (tree) that may contain things that are not numbers.
• Write a function (total items prices) that will compute the total cost of a list of items. prices is a list ((item price) ...). Example:
```   (total '(bread milk) '((eggs .69) (milk 1.89) (bread 1.39)))
=  3.28
```
• Write a recursive function that translates a prefix expression (as in Lisp) to an infix expression (as in Pascal). Assume operators + - * / , where - can be either unary or binary. Example:
```   (infix '(+ a (* b c)))  =  (a + (b * c))
```
• Write a function (average lst wts) to compute a weighted average of grades. lst is a list of sublists (item grade). wts is a list of sublists (item weight) in arbitrary order. For each element of lst, look up the corresponding weight for that item, multiply the grade by it, and add to the total. Example:
```   (average '((midterm 80) (homework 75) (final 90))
'((homework .2) (final .5) (midterm .3)))
=  .3 * 80 + .2 * 75 + .5 * 90  =  84
```
• Write a function (weight tree lst) to compute the "weight" of a tree structure. Each pair has a weight of 2. Symbols that are in lst have a weight of 3. All other items have a weight of 0. Example:
```   (weight '((a 3) (b c d)) '(a b))  =  20
```
• Write a function (path goal tree) that will return the list of successive car's and cdr's necessary to reach the first occurrence of the simple item goal in the structure tree. If goal does not occur in tree, return #f. Example:
```   (path 'c '((a b) (c d)))  =  (cdr car car)
```
• Write a function (opposite lst opp) that returns a list of the opposite of each item in lst. opp is a list of sublists, ((item opposite) ...). If an item in lst does not have an opposite, nothing is included in the output for it. Example:
```(opposite '(up cat ernie) '((ernie bert) (up down)))
=  (down bert)
```
• A student likes Scheme so much that he writes his grocery list as an expression using the operators + and *. Write a function (cost groceries prices) to calculate the cost of the groceries given a list of dotted pairs ((item . price) ...). Example:
```(cost '(+ bread (* 2 milk) (+ nuts (* 2 (* 6 beer))))
'((beer . 0.8) (milk . 1.2)(nuts . 2)(bread . 1.5)))
=  15.50
```
• Write a function (largest tree) that finds the largest number in a tree. The tree contains at least one number. You may assume that all the numbers are positive. Example:
```(largest '((+ a 7) b (11 c)))  =  11
```
• A mobile is a symbol, a number, or a list of two mobiles. A mobile is balanced if it is a symbol or a number, or if it is a list, its sub-mobiles are balanced, and its sub-mobiles weigh the same. Symbols have a weight of 1; numbers weigh the amount of the number, and other things weigh nothing. Write a function (balanced m) to determine whether a mobile m is balanced; write other functions if needed. Example:
```(balanced '((1 A) 2) )  =  #t
```
• Write a function (total items bargains prices) as follows. items is a list ((quantity item) ...) giving items purchased. bargains is a list (item ...) of items that are on sale for 1.00 . prices is a list ((item price) ...) of item prices. Any item that is not in bargains or prices is free. Compute the total cost of all items purchased. Example:
```(total '((6 beer) (1 milk) (1 bag)) '(beer nuts bread)
'((oats 2.00) (milk 1.69) (apple .50)))
=>  7.69
```
• Write a function (weight tree) to compute the weight of a tree structure. Each pair has a weight of 2. symbols have a weight of 1. numbers have a weight equal to the number value. Anything else weighs 0. Example:
```  (weight '((a 3) 7))  =>  19  ; 4 pairs, 1 sym, 3, 7
```
• A family tree is a list (mother name father) where mother and father are family trees (or #f if unknown) and name is a symbol. Write a function (relative tree name) that returns a list giving the relation of name to the person whose family tree is given by the argument tree. Examples:
```  (relative '(#f john #f) 'john)  =>  ()    ; john himself
(relative '((#f mary (#f bill #f)) john (#f fred #f))
'bill)
=>  (mother father)  ; bill is john's mother's father
```
• A car approaching an intersection can go one of three ways: left, straight, or right. An intersection is represented as a list (left straight right) of possibilities. Each possibility is an intersection or a destination (non- pair). Write a function (follow int directions), where int is an intersection, that will follow the list of directions (each of which is L, S, or R) and return the subtree or destination denoted by the directions. If the directions continue past the intersection lists, return #f. Examples:
```  (follow '(a b c) '(r))  =>  c  ; right turn goes to c
(follow '(a (b c (d e f)) g) '(s r l))  =>  d
; straight to (b c (d e f)), right to (d e f), left to d
```

### Box Diagrams:

Convert between list structure and box diagrams (both ways).

### Vocabulary:

You will be asked to write definitions for terms selected from the list below. Definitions are given at the back of the lecture notes.
```access time              alist               array
ASCII                    association list    atom
binary search            binary tree         byte
Caesar cipher            case insensitive    case sensitive
CD-ROM                   character           character code
code                     concatenation       cons cell
data abstraction         decryption          destructive operation
disk                     driver              dynamic
element                  encapsulation       encryption
enumerate                file                functional programming
garbage                  hiding              I/O
index                    initialize          input/output
interface                intersection        isomorphism
key                      mapping             nesting
polynomial               port                private
proper subset            public              public key