Midterm #1

Midterm #1 will be held on Friday, 10/20.
The midterm will cover chapters 1 through 3 of the book.
There will be an in-class review on Wednesday, 10/18.

The first question will be just like a quiz, with problems similar to the problems on the first three quizzes. At least two questions will ask you to write some short Scheme procedures similar to those on the homework assignments. In particular, you may be sure that at least one of the procedures-- if not all --will involve recursion. In addition, there could be one short answer question.

Here are some concepts to emphasize in your studying:

Expressions vs. Values
Application Evaluation Algorithms
   Eager, Lazy, Short Circuit, Conditional, Sequential
   Special Forms: if, cond, and, or, begin, begin0
Polymorphism vs. Monomorphism
Data Abstraction (constructors, selectors, & recognizers)
Coercions
Data Flow Diagrams
Equivalence Predicates
List Processing
   Association Lists
   assoc, assq, assv, member, memv, memq
Tracing Here are some sample problems:
1. Write a scheme procedure called count that has two parameters: val (any Scheme value) and vals (any list of Scheme values):
(define (count val vals) ???)
This procedure returns the number of occurances of val in vals. For example:
-> (count 0 '(2 3 0 4 0 5 0 6))
3
-> (count 4 '())
0
Hint: use map and apply.

2. Write a Scheme procedure called hyper-exp that has a single parameter: num ( a natural number):

(define (hyper-exp n) ???)
This procudure computes 2^(2^(... (2^1)... )), where 2^n = (expt 2 n). For example:
-> (hyper-exp 0)
1  ; by definition
-> (hyper-exp 1)
2  ; = 2^1
-> (hyper-exp 2)
4  ; = 2^(2^1) = 2^2
-> (hyper-exp 3)
16 ; = 2^(2^(2^1)) = 2^4
-> (hyper-exp 4)
about 64000 = 2^16
-> (hyper-exp 5)
HUGE!!!
Hint: use recursion and (expt 2 n).