Your name: 	

1

A


CS 3 (Clancy)	Exam 2
November 9, 1992
This exam has answers displayed.
Read and fill in this page now.
Do NOT turn the page until you are told to do so.
Your name:		
	(please printÑlast name, first name)
Your lab section day and time:		
Your lab t.a.:		
Name of the person sitting to your left:		
Name of the person sitting to your right:		
Problem 0			Total:  	/30
Problem 1							Problem 3		
Problem 2							Problem 4		
This is an open-book test. You have approximately fifty minutes to 
complete it. You may consult any books, notes, or other inanimate objects 
available to you. To avoid confusion, read the problems carefully. If you find it 
hard to understand a problem, ask us to explain it. If you have a question 
during the test, please come to the front or the side of the room to ask it.
This exam comprises 15% of the points on which your final grade will 
be based. Partial credit will be given for wrong answers. 
You are not to use setf within functions. Any other Lisp construct 
described in Touretzky chapters 1-8, either part of the ÒDifference Between 
DatesÓ case study, the ÒStatisticsÓ case study, the supplementary reading on 
applicative operators, or ÒInteger Division and its UsesÓ is ok, though, except 
where otherwise specified. 
Your exam should contain 5 problems (numbered 0 through 4) on 8 
pages. Please write your answers in the spaces provided in the test; in partic-
ular, we will not grade anything on the back of an exam page unless we are 
clearly told on the front of the page to look there. 
RelaxÑthis exam is not worth having heart failure about.

Problem 0 (2 points)
Put your name on each page. Also make sure you have provided the 
information requested on the first page.
Review of material from homework assignment 8
Recall that homework assignment 8 involved the processing of a 
transaction list. Each element of the transaction listÑa transactionÑwas a 
two-element list whose first element was a date in 1992 and whose second 
element was an amount (negative for a withdrawal, positive for a deposit). 
Transaction lists were allowed to be empty, and to have more than one 
transaction on a given date. The order of transactions within a transaction 
list was not specified. Here was an example:
(((january 1) -10)
 ((june 1) -10)
 ((june 2) 30)
 ((january 1) 5))

Problem 1 (6 points, 10 minutes)
Each of the functions below takes two inputs: the first is a predicate 
whose single input is a single transaction in the format used in homework 
assignment 8, and the second is a list of transactions. Indicate for each of the 
functions below which of the following it returns:
A.	a list of transactions
B.	a single transaction
C.	a list of dates
D.	a single date
E.	none of the above
function	type of value
returned by
the function
(defun mystery1 (pred trans-list)
	(defun later (tr1 tr2)
		(if (> (days-between (first tr1) (first tr2)) 0)
			tr1 tr2)
	(reduce #'later trans-list) )	
2 pts
transaction
(B)
(defun mystery2 (pred trans-list)
	(mapcar #'first (remove-if-not pred trans-list)) )	2 pts
date list (C)
(defun mystery3 (pred trans-list)
	(mapcar #'first (find-if pred trans-list)) )	2 pts
none (E)

Problem 2 (12 points, 20 minutes)
Part a
The function large-transactions below is given three inputs: a list of 
transactions, a month name, and a numeric amount. It is intended to return 
a list of all the transactions in the given list that occurred in the given month 
and that involved an amount larger than the given amount. For example, the 
call
(large-transactions
	'(((may 1)  27) ((june 4)  27) ((may 3)  28)
	  ((may 1) -28) ((june 3)  28) ((june 2) -28))
	'may
	27)
should return
(((may 3) 28) ((may 1) -28))
Provide a body for the large-in-month? function so that large-
transactions works as intended.
(defun large-transactions (trans-list month-name amount)
	(defun large-in-month? ( 	 )
			 )
	(remove-if-not #'large-in-month? trans-list) )

4 points (-1 per bug)

(defun large-and-in-month? (trans)
	(and (equal (first (first trans)) month-name)
		(> (abs (second trans)) amount) ) )

Part b
A common bug is to accidentally use the wrong function in oneÕs code, 
for instance, by substituting remove-if for remove-if-not, and for or, or < for >. 
Describe, by filling in the blanks below, such a substitution in the function 
you wrote for part a for which the call
(large-transactions
	'(((may 1)  27) ((june 4)  27) ((may 3)  28)
	  ((may 1) -28) ((june 3)  28) ((june 2) -28))
	'may
	27)
would return an incorrect result, but the call
(large-transactions
	'(((may 1)  10) ((june 4)  20) ((april 3)  30)
	  ((may 1) -40) ((june 3)  50) ((april 2) -60))
	'may
	27)
would return the correct result.
Replacing the function name 	
by the function name 	
in my answer to part a would cause the behavior just specified.

2 points (probably all or none)

Using >= for < would produce the specified behavior.

Part c
Another way to write the large-transactions function is to filter the 
transaction list twice, first isolating the transactions in the proper month, 
then isolating those with sufficiently large amounts. The diagram below 
illustrates this approach, applied to the example given in part a.
                                        
Rewrite the large-transactions function to apply this approach. You may 
supply auxiliary functions; indicate clearly whether they are defined inside or 
outside large-transactions.
(defun large-transactions (trans-list month-name amount)
)

6 points: -1 for bad parentheses, -3 for applying #'large? 
and #'in-month? out of order, -2 for using (first trans) 
instead of (first (first trans)), for confusing remove-if 
for remove-if-not or some other one-word bug, or for most 
other small bugs

(defun large-transactions (trans-list month-name amount)
	(defun large? (trans)
		(> (abs (second trans)) amount) )
	(defun in-month? (trans)
		(equal (first (first trans)) month-name) )
	(remove-if-not
		#'large?
		(remove-if-not #'in-month? trans-list) ) )

Problem 3 (6 points, 10 minutes)
Consider now a new format for a transaction, namely a three-element 
list, whose elements are (1) a date, (2) either the atom WITHDRAW or the 
atom DEPOSIT, and (3) a positive numeric amount. In the new format, the 
transaction list on page 2 would appear as
(((january 1) WITHDRAW 10)
 ((june 1) WITHDRAW 10)
 ((june 2) DEPOSIT 30)
 ((january 1) DEPOSIT 5))
Write a function old-to-new that takes as input a transaction list in the 
old formatÑi.e. in the format used in homework assignment 8Ñand returns a 
list in the new format that represents the same sequence of transactions. Do 
not use recursion. You may supply auxiliary functions; indicate clearly 
whether they are defined inside or outside old-to-new.
You may find Common LispÕs abs function useful. Given a number as 
input, abs returns the absolute value of the number (the result of discarding 
the minus sign if the number is negative). 
(defun old-to-new (old-trans-list)
)

6 points (-1 for bad parentheses, -2 for each other small 
bug)

(defun old-to-new (old-trans-list)
	(mapcar
		#'(lambda (trans)
			(if (< (second trans) 0)
				(list (first trans) 'WITHDRAW (abs (second trans)))
				(list (first trans) 'DEPOSIT (second trans)) ))
		old-trans-list ) )

Problem 4 (4 points, 10 minutes)
The incomplete recursive function below is intended to return the 
smallest number in its input, a nonempty list of numbers. Fill in the blanks 
to complete the function. (You will need to complete one cond clause, and 
perhaps add another.)
; Given a nonempty list L of numbers, return the
; smallest value in the list. I.e. return the same
; thing that (reduce #'min L) would return.
(defun my-min (L)
	(cond
		( 	
		  	
		  	
				(first L) )
		( T (my-min (rest L))) ) )

4 points (-1 for bad parentheses, -2 for each other bug)

(defun my-min (L)
	(cond
		((= (length L) 1) (first L))
		((< (first L) (my-min (rest L))) (first L))
		( T (my-min (rest L))) ) )