CS 307 Midterm Exam 1 Study Guide

Date: Friday, October 5, 2001, in class.

Hailperin, Chapters 1, 2, 3, 4, 7.

Lisp Topics:

• Lisp representation of programs and mathematical expressions.
• Recursion: with a counter, with a test, on a list. Tail recursion.
• Iteration: dotimes, while, do, dolist.

Lisp Functions:

You should know the following Lisp functions. Be able to give the result for a simple call to each function.
• Arithmetic:
```+        -      *      /     max     min     abs     modulo
gcd      lcm    expt   exp   sqrt    sin     cos     tan
atan     asin   acos   log
```
• Control:
```begin   if   cond   case   dotimes   while   do   dolist
```
• Special:
```define      let      let*      quote      set!
```
• List Structure:
```car       cdr       cadr      caddr     cons      list
append    reverse   length    memq      memv      member
assoc     assq      assv
```
• Predicates and Logical:
```and        or        not        =           <=          <
>=         >         zero?      positive?   negative?   odd?
even?      number?   integer?   rational?   real?       list?
boolean?   symbol?   pair?      null?       eq?         eqv?
equal?     exact?    inexact?
```

Programming:

Write Scheme programs for each of these:
• Given as input a list of numbers, add up the squares of the numbers.
• Write a function that counts the number of symbols at the top level of a list l. Example:
```(countsymbols '(a b 7 (peas) #f carrots))  =  3
```
• You are given as input a list of items, some of which are numbers and some of which may not be numbers. Write function(s) to compute the average of the numbers in the list (at top level).
• Write function(s) that count the number of "interesting" symbols in a list lst, given a list int of interesting symbols. It should be (define (int-count int lst) ...), e.g.:
```(int-count '(big dog) '(a big dog has a big appetite))  =  3
```
• Write a function as follows: The inputs are a list, lst, of positive integers and a positive nonzero integer n. The output should be a list containing those elements that are exactly divisible by n. Example:
```(divideby '(3 4 6 17 21 0) 3)  =  (3 6 21 0)
```
• Write a function as follows: The input is a list, lst, consisting of a student's last name followed by a series of sublists, (item points). The function should return the sum of the points. Example:
```(addpoints '(smith (exam 33) (lab 40) (extra 10)))  =  83
```
• Write a function as follows: The input is a list of sublists; each sublist has the form (department sales costs). Profit for a department is sales minus costs. Find the total profit across all departments in the list. Example:
```(profit '((garden 15000 10000) (kitchen 2000 1000)))
=  6000
```
• Write a function as follows: The input is an association list of sublists containing a name and a phone number. The output should be an association list containing sublists containing a phone number followed by a name. Example:
```(invert '((john 3271234) (mary 4449876)) )
=  ((3271234 john) (4449876 mary))
```
• Write a function (points lst pts) as follows: lst is a list of symbols, and pts gives the number of points for each kind of symbol. Compute the total number of points for all the symbols in lst. Example:
``` (points '(pawn rook pawn)
'((queen 10) (rook 5) (pawn 1)))  =>  7
```
• The sine function can be computed from its Taylor series expansion:
```          1    3    5    7    9
x    x    x    x    x
sin(x) = -- - -- + -- - -- + -- - ...
1!   3!   5!   7!   9!
```
Write a function (sine x) to compute sine using this series. You may not use the functions expt or factorial; instead, write a tail-recursive auxiliary function to compute each term of the series from the previous term and add it to the sum. Stop after the 21st power of x. Hint: write down how each term of the series differs from the previous term.
• Write a function (select major year lst) as follows: lst is a list of sublists of the form (name major birth-year) and year is the current year. The function should return a list of sublists of the form (name age) giving the name and age of each person with the specified major. Example:
```(select 'cs 2000
'((john cs 1980) (mary math 1982) (jane cs 1982)))

=>  ((john 20) (jane 18))
```

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.
``` actual parameter          algorithm             ALU
assignment statement      assignment            argument
auxiliary function        base case             bignum
big O() notation          binary                binding
bit                       Boole, George         Boolean
Boolean algebra           central processor     combination
compiler                  conditional           constant
count-controlled loop     CPU                   data type
dynamic type checking     dynamic storage       dotted pair
environment           evaluation
event-controlled loop     exact number          exponent
external representation   fixed-point           GIGO
floating-point number     formal parameter      function
high-level language       global variable       identifier
implicit begin            inexact number        infinite loop
internal representation   integer               interpreter
invariant                 invocation            iteration
lexical scoping           Lisp                  list
machine language          mantissa              memory
mnemonic                  operation             pair
parameter                 pointer               predicate
procedure                 prompt                quote
random-access memory      RAM                   rational
recursion                 register              Scheme
scope                     scope rules           S-expression
side effect               special form          stack frame
state                     subprogram            subroutine
symbol                    tail recursion        top level
top level of a list       type                  value
variable
```

Box Diagrams:

Give the box diagrams for each of these:
• (((a) b) c d)
• ((a (b)) ((c) d))
• ((((a) (b)) ((c) d) e) f)
• (((a) (b c)) (e (f (g))))
• (((a) (b (c)) d) (e (f)) (((g)) h))

Box Diagrams:

Give the list structure for each of these: