CSE1729-SCHEME
Introduction to Programming Final Exam
May 3, 2021
This is a 120 minute exam, commencing at 8:00am and finishing at 10:00am. This exam is open book and open notes. So you may use material from lecture, labs, problem sets or your personal notes. You may not use any outside reference material during the exam, including online materials, or information provided by other people. Please read every question carefully before answering and express your answers as completely as you can. Beware, you must explicitly submit all solutions in Mimir. Any work not completely submitted will not be visible for grading. So, it is your responsibility to ensure your work is submitted before the timed exam ends. Work is not automatically submitted by the Mimir interface.
There are five questions on the exam, each worth 10 points; you may choose any four to complete. Thus the highest score that can be achieved on the exam is 40 points. Please indicate which four questions you wish to be graded in the check boxes located in the first question in Mimir.
Name:
Question Points Grade? Score
1 10
2 10
3 10
4 10
5 10
Total 40
1
1. SHORT ANSWERS
(a) (2 points) RECURSION
The rising factorial, denoted x(n), is the product of the n consecutive integers starting at x and
is defined as
n−1
x(n) =x(x+1)(x+2)···(x+n−1)=(x+k).
k=0
Define a SCHEME function, named (rising-fact x n), which computes the rising factorial
for x and n. The value is defined to be 1 (an empty product) when n = 0.
(b) (2 points) TAIL RECURSION
The falling factorial, denoted (x)n, is the product of the n consecutive integers ending at x and
is defined as
n−1
(x)n =x(x−1)(x−2)···(x−n+1)=(x−k).
k=0
Define a tail recursive SCHEME function, named (falling-fact x n), which computes the
falling factorial for x and n. The value is also defined to be 1 (an empty product) when n = 0.
(c) (2 points) HIGHER-ORDER FUNCTIONS
An alternate way to approximate the derivative is to use the interval on the “other side” (with respect to the more common method) of x to get the Backward Difference:
f′(x)≈D−f(h)= f(x)−f(x−h) h
Define a SCHEME function, named (D- f h), which uses the formula for the Backward Dif- ference to produce a function of one argument, x, which approximates the derivative of a given function f at x, using h as the value for ∆x. Note, your function should, again, return a function that approximates the derivative of f at x (i.e f ′(x)).
(d) (2 points) TREES
Given a binary tree with depth d, the maximum size of that tree is 2d+1 − 1. We define the density of a binary tree T to be the size (number of nodes) of T divided by the maximum size of a tree that has the same depth as T. Define a SCHEME function, named (tree-density T), which returns the density of tree T .
Hint: you will need to determine (tree-size T) and (tree-depth T) to find (tree-density T).
2
(e) (2 points) MORE TREES
Write a SCHEME function (tree-reduce f i T) which, given a ternary function f , an initial i, and a tree T , computes the reduce operation on the tree T according to f . The function
f , when applied to a tree node (x left right) takes 3 arguments that correspond to the root x and the reduce of the left and right subtrees. Consider the tree in Figure 1. The call (tree-reduce + 0 T) would output the sum of all the values in the tree, i.e., it would output 70.
9
5 15
4 7 10 20
Figure 1: A Simple Tree called T
3
2. PAIRS AND LISTS
As discussed in lecture, all values manipulated by a computer are stored using a binary representation. This representation of numbers in base-2 (binary), follows the same pattern as decimal numbers in base-10. The least significant bit/digit is placed in the rightmost position and each “place” is multiplied by increasing powers of the base and all results are added to determine the value represented. For instance, the following binary number represents the decimal value 6.
most significant bit → 0 1 1 0 ← least significant bit 23 22 21 20
0 +4 +2 +0 =6
Converting a decimal integer to it’s binary representation is actually straightforward. Each bit is the remainder of integer division by two. To move to the next “place,” repeat on the quotient resulting from integer division by two. For instance for the decimal integer 14,
Division by 2 Quotient Remainder Bit Position 14/2 7 0 0
7/2 3 1 1
3/2 1 1 2
1/2 0 1 3
Yields the binary representation 1110. That is, 1410 = 11102.
(a) (3 points) Define a SCHEME function, named (dec->bin d), which accepts a decimal integer as an argument and evaluates to a list of binary digits (bits), or 0/1 values, which represent the decimal value d in binary. This produces a bit string representing that integer. For example,
> (int->bin 42)
(1 0 1 0 1 0)
> (int->bin 1729)
(1 1 0 1 1 0 0 0 0 0 1)
(b) (2 points) Once in this form, we can perform operations on entire lists of bits. For instance, the “bitwise and” of two bit strings is the bit string resulting from applying the “and” operator on the two corresponding bits in the given bit strings. This results in a new bit string which has the same
length as the two input bit strings. Define a SCHEME function, named (bitwise-and a b), which accepts two lists of 0/1 values of equal length (binary representations of integers) and returns a list of 0/1 values of the same length representing the “bitwise and” of a and b. Since each bit is represented with a 0 or 1, the and of two bits will be 1 when their sum is equal to two.
> (bitwise-and (int->bin 1729) (int->bin 1728))
(1 1 0 1 1 0 0 0 0 0 0)
4
(c) (2 points) The “bitwise or” of two bit strings is the bit string resulting from applying the “or” operator on the two corresponding bits in the given bit strings. Define a SCHEME function, named (bitwise-or a b), which accepts two lists of 0/1 values of equal length (binary representations of integers) and returns a list of 0/1 values of the same length representing the
“bitwise or” of a and b. Since each bit is represented with a 0 or 1, the or of two bits will be 1 when their sum is non-zero.
> (bitwise-or (int->bin 1729) (int->bin 1728))
(1 1 0 1 1 0 0 0 0 0 1)
(d) (3 points) The “shift right” operation shifts each bit down to the next bit position. So, the least significant bit shifts out of the list and is removed. To compensate, a zero bit is shifted in from the left and becomes the most significant bit in the resulting binary number. For instance,
> (shift-right (int->bin 1729))
(0 1 1 0 1 1 0 0 0 0 0)
5
3. (10 points) PRIORITY QUEUE OBJECT
The priority queue ADT maintains a set of elements on which there is an order relation. Write a SCHEME object that implements the priority queue abstract data type. This object must maintain a sorted list to store the elements in the priority queue. The interface it provides via the dispatcher function must include the following methods:
empty? checks whether the priority queue is or is not empty;
peek returns the smallest value in the priority queue;
insert adds a value into the priority queue;
pull removes and returns the highest priority (i.e. smallest) value from the priority queue;
Your SCHEME object should adopt the skeleton and dispatcher shown below. Feel free to add any helper functions you may need.
(define (make-pq)
(let ((…)) ;; internal variables
(define (insert …) …)
(define (peek …) …)
(define (pull …) …)
(define (empty?) …)
(define (dispatcher …) …)
dispatcher))
6
4. (10 points) LINE OBJECT
In this problem, you will create a SCHEME object representing a straight line. Recall, a line is defined
by two points. Your object creation function will need two points, stored as SCHEME pairs, to define
the line which the object represents. From that information, your object will calculate the slope,
m = y2−y1 , and y-intercept, b = y − mx , of the line defined by those two points. The object x2−x1 1 1
dispatcher must expose the following capabilities for your object:
get-slope Returns the slope of the line represented by the object.
get-y-intercept Returns the y-intercept of the line represented by the object.
on-line? Takes a point stored in a SCHEME pair as an argument and returns #t if the point is on the line represented by the object and #f otherwise.
get-function Returns a SCHEME function of one argument which, for any x value supplied, returns the corresponding y value for a point on the line. Recall slope-intercept form for straight lines is y = mx + b.
Your SCHEME object should adopt the skeleton and dispatcher shown below.
(define (make-line p1 p2)
(let* ((…))
(define (get-slope) …)
(define (get-y-intercept) …)
(define (on-line? p) …)
(define (get-function) …)
(define (dispatcher method)
(cond ((eq? method ‘get-slope) …)
((eq? method ‘get-y-intercept) …) ((eq? method ‘on-line?) …)
((eq? method ‘get-function) …)))
dispatcher))
7
5. (10 points) MUTABLE DATA
Sylvester’s sequence is an integer sequence where each term is the product of all previous terms in the sequence plus one. Note, the first integer in the sequence, s0, is defined to be equal to two. So, s0 = 2 and
n−1 sn =1+si
i=0
Define a SCHEME function, named (sylvester), which uses destructive assignment to compute the values in Sylvester’s sequence. Your function should define a helper and evaluate to that helper when applied. For example, if your helper is named next, then you might have something like the following:
(define (sylvester)
(let (…)
(define (next)
…)
next))
The first application of the function returned by (sylvester) should evaluate to the first value in the sequence, s0. Every subsequent application of the function will return the next value in the sequence. The first few vaues of Sylvester’s Sequence are
2, 3, 7, 43, 1807, 3263443, 10650056950807, . . . So, your function should perform as follows:
> (define seq (sylvester))
> (seq)
2
> (seq)
3
> (seq)
7
> (seq)
43
> (seq)
1807
> (seq)
3263443
> (seq)
10650056950807
8
SCRATCH SPACE
9
SCRATCH SPACE
10