CSE1729 – Introduction to Programming
April 14, 2020
Prelim 2
This is a 120 minute exam. The only reference material you may use during the exam, are the course textbook or notes. You may not use any additional resources (websites, Google, discussion boards, assistance from other humans) during the exam. Please read every question carefully before answering and express your answers as neatly and completely as you can.
There are 4 questions on the exam, each worth 10 points; you may choose any three to complete. Thus, the highest score that can be achieved on the exam is 30 points. Please indicate which 3 questions you wish to be graded in the check boxes next to the question numbers below.
Name:
Section:
Question
Points
Grade?
Score
1
10
2
10
3
10
4
10
Total
30
1
1. HIGHER ORDER FUNCTIONS AND TAIL RECURSION Recall the most common definition of differentiation:
df = lim f(x+∆x)−f(x) dx ∆x→0 ∆x
We can use this formula to compute an approximation to the first derivative of a function, f , by taking a small value, h to represent ∆x. This gives the following formula, known as the Forward Difference:
f′(x)≈D+f(h)= f(x+h)−f(x) h
(a) [1 point] Define a SCHEME function, named (D+ f h), which uses the formula for the Forward Dif- ference to approximate the derivative of a given function f , using h as the value for ∆x. Note, your function should return a function of one argument, x, that approximates the derivative of f at x (i.e
f ′(x)).
(b) [1 point] Alternatively, we could approximate the derivative by using the interval on the “other side” 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 Difference 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)).
(c) [3 points] The simplest way to get an approximation of the second derivative is to get a symmetrical equation about x by using both the forward and backward differences to estimate f ′(x + ∆x) and f ′(x) respectively:
f′′(x)≈D2f(h)= D+(h)−D−(h) h
Define a SCHEME function, named (D2 f h), which uses the functions for the forward difference and backward difference defined in the previous two parts to define a function which, given x, will compute the second derivative of f at x using the approximation shown above. Note, your function should, again, return a function that approximates the second derivative of f at x (i.e f ′′(x)).
(d) [2 points] Hofstadter-Conway $10,000 Sequence Consider the following recursive sequence, defined by the recurrence relation
1
a(n)= 1 a(a(n−1))+a(n−a(n−1))
if n = 1, ifn=2, if n>2.
In 1988, John Conway showed that limn→∞ a(n)/n = 1/2 and offered a prize of $10,000 to the discoverer of a value of n for which |a(i)/i − 1/2| < 1/20 for i > n. The prize was subsequently claimed by Mallows, after a reduction of the “intended” prize to $1000, who found n = 1489. In private communication, Hofstadter later claimed he had found the sequence and its structure some 10-15 years before Conway posed his challenge.
Define a SCHEME function, named (a n) which computes the nth value in the sequence defined by John Conway.
(e) [3 points] If it is possible, define a tail recursive version of the Hofstadter-Conway $10,000 Sequence (i.e. your solution to Part d). If it is not possible, explain why.
2
2. PAIRS AND LISTS Recall our simple definition of the SET Abstract Data Type. We’d like to be able to • insert a number into our set, and
• test membership: Determine if a given number is an element of our set.
The first implementation we considered used a list as the data structure for storing Set elements. However, the list data structure had a shortcoming in that it required us to possibly visit each data element in the list when checking for set membership. Considering the fact that sets do not, by definition, contain duplicates. We also check for set membership before doing an insert operation.
One approach, to reduce the increase in time required for these operations as the number of set elements increases, is to store the set elements in several, shorter, lists. To do this, we need to organize the elements of the set into these shorter lists in a precise way so that it it is clear in which of these smaller lists a set element belongs. To assign a set element to one of the shorter lists, we can define a function which determines which list to use when given a set element. This function is referred to as a hash function.
We will call the set of elements stored in this manner a hash set. In order to build an implementation of a hash set for integer data elements, we need a hashing function. That is, a function which will assign an integer data element to one of the smaller lists that make up our hash set. Let’s build a hash set to store integers in ten smaller lists. We will assign a data element to one of these lists by its least significant digit. Finally, we can store all ten of these smaller lists together in another list. For instance, the set {1, . . . , 20} would be stored as:
((10 20) (1 11) (2 12) (3 13) (4 14) (5 15) (6 16) (7 17) (8 18) (9 19)) An empty set would be represented by
(define hash-set (list ‘() ‘() ‘() ‘() ‘() ‘() ‘() ‘() ‘() ‘()))
(a) [1 point] Define a SCHEME function, named (is-empty? S), which evaluates to #f if the hash set S, defined as the list of lists described above, contains any element(s) and #t if it contains no elements.
(b) [1 point] Define a SCHEME function, named (hash e) which given an integer element e, evaluates to the least significant digit of e. We will use this for the index of the smaller list that e will either be placed into for an insert operation or the list in which e can be found when testing for set membership. For example,
> (hash 1729)
9
> (hash 42)
2
(c) [2 points] It will be useful to be able to isolate and extract the appropriate list from our hash set when performinganinsertoramembershipquery.DefineaSCHEMEfunction,named(get-hash-list i S), which retrieves the sub-list of hash-set S at index i. For example, retrieving the list at index 9, can be accomplished by your get-hash-list function, e.g.:
> (get-hash-list 9 example)
(9 19)
Note, sub-lists are indexed starting at 0.
(d) [3 points] Define a SCHEME function, named (is-member? e S), which performs a membership query for element e in our hash set S. Consider, if I wanted to complete an membership query on my example hash set with the value 1729. I would
1. use my hash function to determine that this new element belongs in the sub-list at index 9 2. retrieve that sub-list, and
3. search that smaller list for the value of interest, 1729.
3
You are, of course, free to use any of the functions defined in previous parts and free to define any additional helper functions you find useful.
(e) [3 points] Define a SCHEME function, named (insert e S), which inserts element e into hash set S. You should first check to ensure e is not already an element of set S. In this case, you should just return the original set S. Inserted elements must be placed into the correct sub-list according to the hash function. For instance,
> (insert 1729 example)
((10 20) (1 11) (2 12) (3 13) (4 14) (5 15) (6 16) (7 17) (8 18) (1729 9 19))
4
TREE CONVENTIONS
Problems 3 and a on the exam both concern binary trees. As in class, we consider binary trees with the property that each node stores—in addition to its two subtrees—an integer. Recall the convention that we used for such trees: each node is represented by a list
(v left right), where v is a value, and left and right are its two subtrees.
Please adopt this convention in your responses to the following questions. You may make free use of the “convenience” functions:
(define (maketree v left-tree right-tree)
(list v left-tree right-tree))
(define (value T) (car T))
(define (left T) (cadr T))
(define (right T) (caddr T))
The first of these functions builds a tree from a value and a pair of trees; the following three functions extract, from a tree T, the value of the root and its left and right subtrees. Finally, we used the SCHEME empty list to represent the empty tree.
66 416 716 −1 5 31 19 11 31
A binary search tree Not a binary search tree
Figure 1: On left, a tree that has binary search tree structure; on right, a tree that does not.
5
3. TREES & BINARY SEARCH TREES
(a) [2 points] Define a SCHEME procedure, named (tree-duplicate T), which takes a binary tree as an argument and returns a separate tree data structure that is similar to the original tree T (same values in the same places with the same structure).
(b) [4 points] Write a SCHEME function named, (only-children T), which evaluates to the number of nodes in tree T that have exactly one child node.
(c) [4 points] Define a SCHEME function named (bst-depth x T) which, given a value x and a binary search tree T, returns the depth of the node containing the value x in binary search tree T. Note, you must take advantage of the binary search tree property to produce an efficient implementation of bst-depth. Also, you may assume the value x is present in the binary search tree.
6
4. HEAPS
In the following parts, you can assume the existence of several functions to manipulate heaps. Namely, you have (for all sub-parts):
(define (heap-insert e H) …)
(define (combine H1 H2) …)
(define (h-min H) …)
(define (remove-min H) …)
As before, the functions do the following. heap-insert adds element e to a heap H returning a new heap. combine takes two heaps H1 and H2 and combines them to return a single heap. h-min returns the element at the top of heap H and remove-min returns a new heap H′ identical to H except for the removal of its smallest element.
(a) [5 points] Recall that a heap is a binary tree with the property that the value of any node is less than (or equal to) that of its children.
Write a SCHEME function, named (trim-heap H z), which, given a heap H and an integer z, returns a heap that contains all elements of H that are smaller than z.
For example, given the heap on the left in Figure 2 below and the number 15, your function could return the heap on the right hand side.
66 716 7
191131 11
Before deletion After deletion
Figure 2: On left, a heap. On right, the remaining heap after all elements greater or equal to 15 have been removed.
(b) [5 points] Give a SCHEME function (predecessor v H) which, given a value v and a heap H, returns the largest value stored in the heap which is smaller than the value v.
1 82
7
A heap H.
For instance, the call
For example, evaluating (predecessor 7 H), where H is the heap shown here, would return the value 2. You may return an empty list if the value, v, does not appear in the heap. You may assume v has a predecessor if it appears in the heap.
(predecessor 7 (list->heap (list 1 8 2 7) ‘()))
should produce the output 2.
For full credit, you must find the predecessor of the value v without extracting all of the elements stored in heap H.
7
8