CS 2360/4730
Midterm 1 Winter 1997
Please write your name on the upper right hand corner of this page. There are
70 points possible on this exam. You have 80 minutes to complete it. Put only
what you want to be graded on the front sides of the pages, and use the back
sides of the pages as scratch paper. If you run out of room on the front side
of the page, you can put part of your answer on the back of that same page, but
make sure you note on the front of the page that there's stuff to be graded on
the back. And please strive for legibility, because I don't give credit for
stuff I can't read. For this exam, use only recursive or applicative
programming techniques as indicated in the individual problems. Don't use
traditional iterative methods (no loop, do, dolist, dotimes, etc.). Before you
start, check out the cheat sheet on the last page of this exam. It might help.
And yes, you may remove the cheat sheet from the rest of the exam.
1. (10 points) Let's start with a real easy one. Write a function in Common
LISP called compare-scores. The function takes two arguments, both of them
numeric values, and compares them. (You can assume that the values being
passed will be numeric; do not do error checking.) If the second value is
greater than the first, the function returns the symbol better. If the second
value is less than the first, the function returns the symbol worse. If the
two values are equivalent, the function returns the symbol same. Here are some
examples of this function at work:
? (compare-scores 50 80)
BETTER
? (compare-scores 80 50)
WORSE
? (compare-scores 60 60.0)
SAME
2. (0 points) Here's another easy one. In fact, it's so easy that it's not
going to get you any points at all, but it will make it easy for you to keep
track of your scores in this course. So that we can post your scores on the
newsgroup, we'd like you to provide us with a super secret identification code
(of no more than eight characters) that will allow you to find your scores
without anyone else knowing which scores are yours. If you want us to post
your scores on the newsgroup, please print your code in the space below. If
you don't want us to post your scores, just leave the space blank.
___________________________
3. (10 points) Show the following lists in box (or box-and-pointer) notation:
(a (b (c)))
(((a) b) c)
4. (10 points) Here are some questions that don't require you to write LISP
code (short but understandable answers would be greatly appreciated):
a) What are the basic principles of the functional programming paradigm?
b) What advantages does the functional programming paradigm offer over other
programming paradigms?
c) Some unenlightened programmers think that recursion is unnecessarily
inefficient when it comes to resource usage. What recursive technique
might these dullards employ to overcome this perceived problem?
5. (10 points) Consider the following function definitions:
(defun mystery-1 (m-list)
(mystery-2 m-list nil nil))
(defun mystery-2 (m-list list-1 list-2)
(cond ((null m-list) (list list-1 list-2))
(t (mystery-3 (rest m-list)
(cons (first m-list) list-1)
list-2))))
(defun mystery-3 (m-list list-1 list-2)
(cond ((null m-list) (list list-1 list-2))
(t (mystery-2 (rest m-list)
list-1
(cons (first m-list) list-2)))))
What will be returned when the following call to mystery-1 is evaluated?
? (mystery-1 '(k s a e r t o i z b))
6. (10 points) Let's make a new function. The function delete-every-nth does
exactly what its name suggests: that is, it deletes every nth element from a
given list. Here are some examples of delete-every-nth in action:
? (delete-every-nth 3 '(a b c d e f g h i))
(A B D E G H)
? (delete-every-nth 2 '(a b c d e f g h i))
(A C E G I)
? (delete-every-nth 1 '(a b c d e f g h i))
NIL
? (delete-every-nth 0 '(a b c d e f g h i))
(A B C D E F G H I)
? (delete-every-nth 4 '(a b c d))
(A B C)
? (delete-every-nth 4 '(a b c))
(A B C)
? (delete-every-nth 4 nil)
NIL
Your job now is to use Common LISP to construct the delete-every-nth function
(and any other functions which might be necessary). The delete-every-nth
function takes two arguments, as shown in the examples. The first will always
be a non-negative integer, and the second will be a list of arbitrary length.
You can assume that these constraints will always be met; don't do any error
checking on the parameters being passed. Oh, I almost forgot...you are to
implement delete-every-nth with augmenting recursion. (If you were hoping to
do it with tail recursion, see the next problem. And while we're on the
topic, the augmenting recursion version of this function is not just the tail
recursive version with some meaningless computation tacked on.)
7. (10 points) Now construct another version of delete-every-nth, but this
time use tail recursion as the only control structure. Call this version
delete-every-nth-tr. This function should accept the same arguments and give
the same results as delete-every-nth. (For purposes of this problem, you can
assume that every function shown on the cheat sheet is available in a tail
recursion form. If you need a function not shown on the cheat sheet, you'll
have to construct your own tail-recursive version of it.)
8. (10 points) After the second midterm, I'll want to compare each student's
score on the second midterm to his or her score on the first midterm and see
who seems to be getting better at this stuff. To do this, I'll need a function
called analyze-scores. This function will take three arguments. The first is
a list of student names. The second is a list of scores from the first
midterm; the first score belongs to the first student in the previous list,
the second score belongs to the second student, and so on. The third argument
will be a list of scores from the second midterm. This function will return
a list of lists. Each list within the list will contain a pair of elements;
the first element is a student's name and the second element is an indication
of how the student's second midterm score compares to that student's first
midterm score. Here's an example of how analyze-scores works:
? (analyze-scores '(alphonse bubba cassandra diogenes edsel) '(30 40 50 60 70)
'(70 60 50 40 30))
((ALPHONSE BETTER) (BUBBA BETTER) (CASSANDRA SAME) (DIOGENES WORSE) (EDSEL
WORSE))
Your last task on this exam is to construct analyze-scores (and any other
supporting functions you might need) in Common LISP. You've already done some
of the necessary work in problem 1, so you can assume the existence of a
compare-scores function if you think it's useful (hint: it is). Oh, one other
thing...the only control structure you can use here is mapcar. Don't use if,
or cond, or anything other than mapcar.
The cheat sheet
(first '(a b c d e)) => a
(second '(a b c d e)) => b
(third '(a b c d e)) => c
(rest '(a b c d e)) => (b c d e)
(cons 'a '(b c d e)) => (a b c d e)
(cons '(a) '(b c d e)) => ((a) b c d e)
(append '(a b) '(c d)) => (a b c d)
(append '(a) '(b) '(c)) => (a b c)
(list 'a 'b 'c) => (a b c)
(list 'a) => (a)
(list '(a b) '(c d)) => ((a b) (c d))
(remove 'a '(a nil b nil a)) => (nil b nil)
(remove nil '(a nil b nil a)) => (a b a)
(length '(a b c d e)) => 5
(length nil) => 0
(* 4 2) => 8
(+ 4 2) => 6
(/ 4 2) => 2
(- 4 2) => 2
(sqrt 25) => 5
(null '()) => T
(null '(a b c)) => nil
(atom 'a) => T
(atom '(a b c)) => nil
(listp 'a) => nil
(listp '(a b c)) => T
(eql 'a 'a) => T
(eql '(a b) '(a b)) => nil
(equal 'a 'a) => T
(equal '(a b) '(a b)) => T
(= 3 3.0) => T
(= 3 5) => nil
(< 3 5) => T
(> 3 5) => nil
(cond ( )
:
( ))
(mapcar #'sqrt '(16 25 36)) => (4 5 6)
(assoc 'b '((a x) (b y) (c z))) => (b y)
(defun )
(function ) =>
It's abbreviated as #'
It can also be applied to lambda functions
Copyright 1998 by Kurt Eiselt. All rights reserved.
Last revised: January 27, 1998