CS 307 Midterm Exam 1 Study Guide
Date: Friday, October 5, 2001, in class.
Hailperin, Chapters 1, 2, 3, 4, 7.
- Lisp representation of programs and mathematical expressions.
- Recursion: with a counter, with a test, on a list. Tail recursion.
- Iteration: dotimes, while, do, dolist.
You should know the following Lisp functions. Be able to give the result
for a simple call to each function.
+ - * / max min abs modulo
gcd lcm expt exp sqrt sin cos tan
atan asin acos log
begin if cond case dotimes while do dolist
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?
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.
(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.
(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.
(profit '((garden 15000 10000) (kitchen 2000 1000)))
- 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.
(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.
(points '(pawn rook pawn)
'((queen 10) (rook 5) (pawn 1))) => 7
- The sine function can be computed from its Taylor
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.
(select 'cs 2000
'((john cs 1980) (mary math 1982) (jane cs 1982)))
=> ((john 20) (jane 18))
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
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
local variable loop Lovelace, Ada
machine language mantissa memory
mnemonic operation pair
parameter pointer predicate
procedure prompt quote
random-access memory RAM rational
read-eval-print loop real
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
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))
Give the list structure for each of these: