Your name: 	

	1



	1


CS 3 (Clancy)	Final exam
December 18, 1992

THIS COPY 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)
Name of the person sitting to your left:		
Name of the person sitting to your right:		
	Total:  	/60
Problem 0					Problem 3				
Problem 1							Problem 4				
											
Problem 2					Problem 5						
This is an open-book test. You have approximately three hours to 
complete it; time estimates accompanying each problem suggest a pace to 
finish in three hours. You may consult any books, notes, or inanimate 
objects other than Lisp interpreters 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 30% 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, any of the case studies, or any of the 
CSÊ3 handouts is ok, though. In particular, either recursion or applicative 
operators is allowed in a solution unless otherwise specified.
Anywhere you are directed to write a function, your solution may 
include auxiliary functions. You need not rewrite a function that appears 
in Touretzky, in any of the case studies, or in any of the CS 3 handouts; 
merely cite the page in Touretzky, the case study and page number or 
appendix, or the handout in which the function appears.
Your exam should contain 6 problems (numbered 0 through 5) on 14 
pages. Please write your answers in the spaces provided in the test; in par-
ticular, 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 (3 points, 5 minutes)
You earn the points for this problem if you have done the following:
¥	you have put your name on each page of this exam, and provided the 
information requested on the first page;
¥	you have completed and handed in the ÒCS 3 Final SurveyÓ (handed 
out in lecture; copies of the latter are available from Mike Clancy or 
the t.a.s);
¥	you have completed an interview.
Check with Mike Clancy or the t.a.s to make sure your survey submission 
and your interview have been recorded.

Problem 1 (35 points, 95 minutes)
A programmer for the U.S. government has written a function that 
returns a list of state election results. The list contains an element for each 
of the 50 states plus the District of Columbia; each element of the list is itself 
a three-element list of the following form:
¥	the first element is an atom, the name of the state (multi-word names 
are combined with hyphens, as in new-york or south-dakota);
¥	the second element is the number of electoral votes from the state 
(how many senators and congresspeople it has);
¥	the third element is an atom, the last name of the candidate that won 
the electoral votes from the state.
The programmerÕs function might have produced a list like the following 
for this yearÕs election:
((california 54 clinton)
 (new-york 33 clinton)
 (texas 32 bush)
 (illinois 22 clinton)
 (florida 25 bush)
 (ohio 21 clinton)
 (pennsylvania 23 clinton)
	... )
For this problem, you will write two versions of a function winner-
name that takes a list of state election results in the form just described, and 
returns the name of the winner. Your code must work for any collection of 
candidates; you may not assume that there are only two candidates. Parts a 
and b comprise a version of winner-name that uses applicative operators and 
not recursion; parts c, d, and e comprise an alternative version.

Part a (30 minutes)
Write a function called vote-total-list that, given a state election result 
list as input, returns a list, again with one element per state, that pairs the 
winner of the state with the total number of electoral votes won by the state 
winner. Your solution may use applicative operators but not recursion, and 
may include nonrecursive auxiliary functions.
Given the state election result list on the previous page, vote-total-list 
would produce the following list:
((california 54 clinton)
 (new-york 33 clinton)
 (texas 32 bush)
 (illinois 22 clinton)
 (florida 25 bush)
 (ohio 21 clinton)
 (pennsylvania 23 clinton)
	... )	       	((clinton 370)
 (clinton 370)
 (bush 168)
 (clinton 370)
 (bush 168)
 (clinton 370)
 (clinton 370)
	... )
(Clinton won 370 total electoral votes, and Bush won 168.)

(defun vote-total-list (state-result-list)
	(mapcar
		#'(lambda (state) 
			(state-winner-total state state-result-list))
		state-result-list) )

(defun state-winner-total (state state-result-list)
	(list
		(third state)
		(reduce #'+
			(mapcar #'second
				(remove-if-not
					#'(lambda (s) (equal (third state) (third s))
					state-result-list) ) ) ) ) )

Part b (15 minutes)
Write a version of the winner-name function that uses one or more 
applicative operators along with the vote-total-list function from part a. 
Winner-name, given a state result list as described on page 3, returns the 
name of the winner of the election. For example, evaluation of
(winner-name 
	'((texas 32 bush) (arkansas 6 clinton) (iowa 7 clinton)) )
should return bush.
Your solution may include other auxiliary functions. Neither your 
winner-name function nor any of these auxiliary functions may use 
recursion, however. You may assume vote-total-list works as specified, 
regardless of what you wrote in part a.

(defun winner-name (state-result-list)
	(first
		(reduce #'max-entry
			(vote-total-list state-result-list) ) ) )

(defun max-entry (e1 e2)
	(if (> (second e1) (second e2)) e1 e2) )

OR

(defun winner-name (state-result-list)
	(first 
		(find-if 
			#'(lambda (entry) 
				(= (second entry)
					(winning-total 
						(vote-total-list state-result-list) ) ) )
			(vote-total-list state-result-list) ) ) )

(defun winning-total (vote-list)
	(reduce #'max (mapcar #'second vote-list)) )

Part c (20 minutes)
Write a function result-total that takes three inputs:
¥	a table that pairs candidates with accumulated electoral vote totals;
¥	a candidate name (an atom); and 
¥	an electoral vote amount (a positive integer).
Result-total should return the table that results from adding the given 
electoral vote amount to the given candidateÕs total. If the given candidate is 
not represented in the table, he or she should be inserted. The order of table 
entries in the result need not be the same as the order of entries in the input 
table. Here are some sample calls.
expression			desired result		
(result-total
	'((bush 40) (clinton 36))
	clinton
	20 )			((bush 40)
 (clinton 56))	or	((clinton 56)
 (bush 40))
(result-total
	'((bush 40) (clinton 36))
	bush
	100 )			((bush 140)
 (clinton 36))	or	((clinton 36)
 (bush 140))
(result-total
	'(( ))
	clinton
	36 )
			((clinton 36))		
(result-total
	'((bush 40) (clinton 36))
	perot
	50 )			((bush 40)
 (clinton 36)
 (perot 50))		table entries may
be in any order
Your result-total function may use either recursion or applicative 
operators. You may also use auxiliary functions.

(defun result-total (table candidate votes)
	(if (assoc table candidate)
		(cons (list candidate 
					(+ votes (second (assoc table candidate))) )
			(remove-if 
				#'(lambda (x) (equal (first x) candidate))
				table ) )
		(cons (list candidate votes) table) ) )

Part d (15 minutes)
Write a function election-helper that takes two inputs: a list of state 
election results as previously described on page 3, and a table pairing 
candidates with electoral vote totals as described in part c. Election-helper 
should return the table pairing candidates with electoral vote totals that 
incorporates all the state election results. For example, evaluation of
(election-helper
	'((ohio 21 clinton) (texas 32 bush) (iowa 7 clinton))
	'((clinton 20) (bush 10)) )
should return the table
((clinton 48) (bush 42))
The table entries may appear in any order.
Your function must not use any applicative operators, nor may it use 
auxiliary functions except the result-total function from part c. (ItÕs ok for 
result-total to have used applicative operators, and for you to use builtin 
Common Lisp functions.) You may assume result-total works as specified, 
regardless of what you wrote in part c.

(defun election-helper (state-result-list results-so-far)
	(if (null state-result-list) 
		results-so-far
		(election-helper 
			(rest state-result-list)
			(result-total 
				results-so-far 
				(first (first state-result-list))
				(second (first state-result-list)) ) ) ) )

Part e (15 minutes)
Write the winner-name function, which returns the name of the 
election winner when given a list of state election results as described on 
page 3. You may use the election-helper function from part d. You may also 
use auxiliary functions; however, none of them may use applicative 
operators (except the result-total function called by election-helper).

(defun winner-name (state-result-list)
	(first 
		(winning-entry 
			(rest (election-helper state-result-list nil)))
			(first (election-helper state-result-list nil)) ) ) )

(defun winning-entry (entry-list so-far)
	(cond
		((null entry-list) so-far)
		((> (second (first entry-list)) (second so-far))
			(winning-entry (rest entry-list) (first entry-list)) )
		( T (winning-entry (rest entry-list) so-far)) ) )

Problem 2 (4 points, 20 minutes)
Complete the following solution to homework assignment 9 by filling 
in the blanks in the prefix-pair-to-decimal and starts-with-prefix? functions. 
Read the code carefully, and donÕt delete any of it.
; Return the decimal equivalent of the given Roman digit.
(defun digit-to-decimal (roman-digit)
	(second (assoc roman-digit '((M 1000) (D 500) (C 100)
	(L 50) (X 10) (V 5) (I 1)) )) )
; Return true when the given Roman numeral starts with a pair 
; of digits in which the first is a prefix for the second,
; and return false otherwise.
(defun starts-with-prefix? (roman-num)
		
		
		
		
		 )

(and 
	(rest L) 
	(< (digit-to-decimal (first L)) 
		(digit-to-decimal (second L))) )

; Given a pair of Roman digits where the first digit is a prefix 
; of the second, return the decimal equivalent of the digit pair.
(defun prefix-pair-to-decimal (roman-digit1 roman-digit2)
	(second
		(assoc 
			roman-digit2
			(rest 
				(assoc roman-digit1
						
						
						 ) ) ) ) )

((C (M 900) (D 400)) (X (C 90) (L 40)) (I (X 9) (V 4)))

; Return the decimal equivalent of the given Roman numeral
; (which may be null).
(defun roman-to-decimal (roman-num)
	(cond
		((null roman-num) 0)
		((starts-with-prefix? roman-num)
			(+ 
				(prefix-pair-to-decimal 
					(first roman-num) (second roman-num) )
				(roman-to-decimal (rest (rest roman-num))) ) )
		( T 
			(+ 
				(digit-to-decimal (first roman-num))
				(roman-to-decimal (rest roman-num)) ) ) ) )

Problem 3 (3 points, 15 minutes)
Given below are two error-checking functions, one for checking an 
Islamic date (from homework assignment 2), the other for checking a 
transaction (from homework assignment 8).
(defun legal-Islamic-date? (d)
	(and
		(listp d)
		(= (length d) 2)
		(member (first d) '(1 2 3 4 5 6 7 8 9 10 11 12))
		(<= (second d) (- 30 (rem (first d) 2))) ) )
(defun legal-transaction? (trans)
	(and
		(listp trans)
		(= (length trans) 2)
		(date? (first trans))
		(numberp (second trans)) ) )
Part a
These two functions can be generalized by a function legal? that takes 
as inputs a value to be checked and a 1-input predicate, returning true if the 
value satisfies the predicate and false otherwise. Complete the framework 
for legal? given below.
(defun legal? (x pred)
	(and
		(listp x)
		(= (length x) 2)
			 ) )

(funcall pred x)
Part b
Complete the definition of legal-transaction? below by providing the 
appropriate input to legal?.
(defun legal-transaction? (trans)
	(legal? trans
			 
			 
			 
			 ) )

#'(lambda (x) 
	(and 
		(date? (first trans))
		(numberp (second trans)) ) )

Problem 4 (9 points, 30 minutes)
Given below is a version of the flatten function from lab assignment 
9+10. It doesnÕt work correctly.
; L is a list.  Return the list of the atoms that occur in L,
; in the order they appear in L.
(defun flatten (L)
	(if (null L) nil
		(reduce #'append (mapcar #'flatten L)) ) )
Part a
By filling in the blank below, provide a nonempty input list to flatten 
that does not cause an error when the resulting expression is evaluated.
(flatten 	 )
Part b
What is the result of evaluating (flatten '(A B))? If the result is an 
error, describe the error message and give the expression whose evaluation 
produced the error.

input to mapcar isn't a list:
	(mapcar #'flatten 'A) or (mapcar #'flatten 'B)

Part c
Which of the following is the reason that flatten doesnÕt work 
correctly? (More than one may apply.)
A.	The base case test (null L) is incorrect.
B.	The base case test is correct, but nil is the wrong result to return in 
that case.
C.	The input passed to the recursive call is not what the function 
expects.
D.	The input passed to the recursive call doesnÕt get closer to the base 
case.
E.	Reduce and append are the wrong functions to use with (mapcar 
#'flatten L) to get the answer.
Explain your answer.

A,B.	The base case should be testing for (atom L) and 
returning (list L).
C.	The function wants a list and is getting an atom.
Part d
Making as few changes as possible to flatten, fix it. HereÕs a copy of 
the code; indicate clearly what should be inserted, what should be deleted, 
and what should be changed.
(defun flatten (L)
	(if (null L) nil
		(reduce #'append (mapcar #'flatten L)) ) )

(defun flatten (L)
	(if (atom L) (list L)
		(reduce #'append (mapcar #'flatten L)) ) )

Problem 5 (6 points, 15 minutes)
The pattern-matching code from lab assignment 12 appears on the 
last page of the exam.
Part a
Provide a call to match that would eventually result in a call to match-
with-*-list with 
first input (the pattern) equal to nil, 
second input (the object) equal to nil, and 
third input (the *-list) equal to the list (A B). 
If no call to match can produce such a call to match-with-*-list, explain why.

No call possible. Add-*-entry only adds lists to the *-list, 
not atoms. Partial credit for something that's too vague. No 
partial credit for providing a call to match.
Part b
Provide a call to match that would eventually result in a call to match-
with-*-list with 
first input (the pattern) equal to nil, 
second input (the object) equal to nil, and 
third input (the *-list) equal to the list ((1) (2)). 
If no call to match can produce such a call to match-with-*-list, explain why.

(match '(* X *) '(2 X 1)) works.

note that (match '(* *) '(2 1)) doesn't work; -1 for this.
-1 for getting them in the wrong order.
Part c
Provide a call to match that would eventually result in a call to match-
with-*-list with 
first input (the pattern) equal to nil, 
second input (the object) equal to nil, and 
third input (the *-list) equal to the list (((A B)) (C)). 
If no call to match can produce such a call to match-with-*-list, explain why.

(match '(* X *) '(C X (A B))) works.
-1 for getting them in the wrong order.
-1 for two consecutive asterisks.
-2 for (C X A B) as an object.
-1 for a solution with wrong parens, but where C and (A B) 
are parenthesized differently.

Pattern matching code from lab assignment 12

(defun match (pattern object)
  (match-with-*-list pattern object nil) )

(defun match-with-*-list (pattern object *-list)
  (cond
   ((null pattern) (null object))
   ((prev-ref? (first pattern))
    (match-with-*-list
     (append (matched-value (first pattern) *-list) (rest pattern))
     object *-list ) )
   ((null object)
    (and (arb-sequence? (first pattern))
         (match-with-*-list (rest pattern) object 
                            (add-*-entry *-list nil) ) ) )
   ((arb-sequence? (first pattern))
    (or
     (match-with-*-list (rest pattern) object (add-*-entry *-list nil))
     (extend-match pattern (rest object)
       (add-*-entry *-list (first object)) ) ) )
   ((symbol? (first pattern))
    (and (equal (first pattern) (first object))
         (match-with-*-list (rest pattern) (rest object) *-list) ) )
   ( T 'INVALID-PATTERN ) ) )

(defun extend-match (pattern object *-list)
  (cond
   ((match-with-*-list (rest pattern) object *-list))
   ((null object) nil)
   ( T (extend-match pattern (rest object)
                     (extend-*-entry *-list (first object)) )) ) )

(defun arb-sequence? (pattern-elem)
  (equal pattern-elem '*) )

(defun symbol? (pattern-elem)
  (and (atom pattern-elem)
       (not (arb-sequence? pattern-elem))
       (not (prev-ref? pattern-elem)) ) )

(defun prev-ref? (pattern-elem)
  (numberp pattern-elem) )

(defun add-*-entry (*-list item)
  (if (null item) (cons item *-list)
      (cons (list item) *-list) ) )

(defun extend-*-entry (*-list item)
  (cons (append (first *-list) (list item)) (rest *-list)) )

(defun matched-value (n *-list)
  (nth (- n 1) (reverse *-list)) )