15-122: Principles of Imperative Computation — Spring 2022
Final Exam
Tuesday 6th December, 2022
1 Is this a Tree? [C0] (35 points)
This question is about binary trees containing integer data, defined as follows:
typedef struct tree_node tree;
struct tree_node {
int data;
tree* left;
tree* right;
};
As usual, the empty tree is represented by the NULL pointer. The data in a tree are not neces-sarily ordered, and there may be duplicates.
Task 1.1
To warm up, write a recursive C0 function that returns the number of elements in a tree.
You may assume that the tree contains fewer than int_max() elements.
int tree_size(tree* T)
//@ensures \result >= 0;
{
}
The function tree_size above impose no requirement on its input! In particular, the tree T could be some horrible pointer mess like the following:
In class, we saw a most naive representation invariant on trees that did not consider the pointer structure. In the next few tasks, we will implement a specification function
bool is_tree(tree* T);
that returns true on well-formed trees, like the ones seen in class as well as the ones rooted at node 5 and at node 10 in the above example, but rejects (i.e., returns false on) ill-formed trees (like the ones rooted at node 3 or at node 7).
We will do so by traversing the tree (i.e., visiting each of its nodes) and, along the way, storing the pointers we encounter in a hash set. As we examine a new pointer, we first check if it is in the set, adding it only if we never saw it before.
Task 1.2
The next two tasks ask you to flesh out this approach in two specific situation. For each, state what the function should do (in term of its return value and/or how it manipulates the hash set, as appropriate) and why.
a. What should is_tree do when called on a pointer that is not in the set?
It should
because
b. What should is_tree do when called on a pointer that is already in the set?
It should
because
c. What should is_tree do when called on a NULL pointer?
It should
because
Recall that a hash set is a set library implemented using hash tables. Here is the interface of a semi-generic C0 self-resizing hash set library, as discussed in class and the lecture notes:
/******** Client interface ********/
// typedef _______ elem;
bool elem_equiv(elem x, elem y);
int elem_hash(elem x);
/******** Library interface ********/
// typedef ______* hset_t;
hset_t hset_new(int capacity)
/*@requires capacity > 0; @*/
/*@ensures \result != NULL; @*/ ;
bool hset_contains(hset_t H, elem x)
/*@requires H != NULL; @*/ ;
void hset_add(hset_t H, elem x)
/*@requires H != NULL; @*/
/*@ensures hset_contains(H, x); @*/ ;
Task 1.3
As a client of this C0 library, define the type elem of the data we will want to insert in the hash set so that we can use it to check if a tree has a valid pointer structure.
typedef elem;
Task 1.4
Define the function elem_equiv that determines when two set elements are the same.
bool elem_equiv(elem e1, elem e2)
//@requires e1 != NULL && e2 != NULL;
{
}
Task 1.5
The hash function we will use returns the (integer) value at the root of its input tree:
int elem_hash(elem T)
//@requires T != NULL;
{
return T->data;
}
Assume the hash table underlying the hash set library implementation uses separate chaining to resolve collisions. If it contains n entries and the table has capacity m, can we count on all chains having length about n/m? Why or why not?
⃝ Yes ⃝ No ecause
Task 1.6
Complete the recursive function has_good_pointers, to be called within is_tree, which checks if the tree T has a valid pointer structure with the help of the hash set H, used to store pointers that have already been visited. Include contracts as needed. (You may not need all lines provided.)
bool has_good_pointers(tree* T, hset_t H)
//@ ;
{
if ( ) return ;
if ( ) return ;
}
Task 1.7
Write the function is_tree that checks that its argument has a valid pointer structure, using has_good_pointers as a helper function.
bool is_tree(tree* T) {
}
Task 1.8
Assume is_tree(T) returns true. What is the asymptotic runtime complexity of this call in terms of the number n of elements in the tree in the best and worst case? As you answer this question, consider the functions elem_equiv and elem_hash as implemented earlier.
Best case: O( ) when
Worst case: O( ) when
2 A Heap for Every Occasion [C1] (55 points)
Consider a priority queue implementation based on heaps as seen in class. The heaps on this page contain characters, where a character that comes later in the alphabet (like ’Z’) is considered to have higher priority than a character that comes earlier (like ’A’).
Task 2.1
Given the following array with char values representing a heap, draw the corresponding tree representation and circle every parent-child relation where the heap ordering invari-ant is not satisfied. This heap has 12 elements.
Task 2.2
Given the following heap, draw the tree we get after we add ’J’ to it. Your tree should satisfy the heap invariants.
Task 2.3
Given the following heap, draw the tree that we get after we remove the maximum element. Your tree should satisfy the heap invariants.
In the remaining tasks of this question, you will be the client of a priority queue library with the same interface seen in class, extended with the function pq_size which returns the number of elements in a priority queue. This interface is reported on page 30 of this exam. This priority queue library may not be implemented using heaps. All the code you will need to write in this question is in C1.
Task 2.4
There is an easy way to sort an array if we have a priority queue: insert all its elements into the priority queue and then empty out the priority queue back into the array. This last phase will retrieve the inserted elements in order.
Complete the code for the function sort that uses a priority function cmp to sort the input array A from highest to lowest priority. The specification function is_sorted(A,lo,hi,cmp) checks if the array segment A[lo,hi) is indeed sorted in this manner. The specification function ge_seg_pq(A,lo,hi, Q, cmp) checks that every element in the array segment A[lo,hi) has priority greater than or equal to the priority of every element in the priority queue Q according to cmp. The missing loop invariant on line 19 should be valid and it should allow you to prove the correctness of this code (in a later task).
1 void sort(void*[] A, int n, has_higher_priority_fn* cmp)
2 //@requires n == \length(A);
3 //@requires cmp != NULL;
4 //@ensures is_sorted(A, 0, n, cmp);
5 {
6 pq_t Q = ;
7
8 // Store the elements in the priority queue
9
10
11
12
13
14
15
16 // Retrieve the sorted elements and put them back in the array
17 for (int i = 0; i < n; i++)
18
19 //@loop_invariant ;
20 //@loop_invariant ge_seg_pq(A, 0, i, Q, cmp);
21 //@loop_invariant is_sorted(A, 0, i, cmp);
22 {
23 //@assert !pq_empty(Q);
24
25 void* x = ;
26 A[i] = x;
27 }
28 }
Task 2.5
Assume that the function cmp runs in constant time. What is the worst-case asymptotic complexity of the call sort(A,n,cmp)?
O( )
Task 2.6
Assume that you have already shown that the loop invariants on lines 19–21 are valid and that the loop terminates. Prove that this function is correct, i.e., that the postcondition holds when it returns. (You may not need all the lines provided.)
To show:
a by
b by
c by
d by
e by
f by
Task 2.7
But, let’s prove nonetheless that the loop invariant on line 21 is preserved by an arbitrary iteration of the loop. As you do so, you may assume that the other loop invariants for this loop are valid. You may use other specification functions from the arrayutil library by passing cmp as an additional parameter (for example, gt_seg(x, A,lo,hi, cmp) to indicate that x has higher priority than every element in A[lo,hi) according to cmp). (You may not need all the lines provided.)
Assume:
To show:
a by
b by
c by
d by
e by
f by
g by
Task 2.8
We know how to return the element with highest priority out of a priority queue. Now, let’s find the element with the k
th highest priority (if k is 1, it returns an element with the highest priority). Complete the implementation of the function k_priority(Q,k) that returns the k
th priority element in priority queue Q. On return, Q should contain the same elements as when the function was called. Hint: as you look for the k
th priority element, you will need to store other elements somewhere.
elem k_priority(pq_t Q, int k)
//@requires Q != NULL && !pq_empty(Q);
//@requires 1 <= k && k <= pq_size(Q);
{
// Temporary space
;
// Get to the k-th element
// Restore Q
return
;
}
Task 2.9
The median of a collection Q is the element m in Q so that half of the other elements have priority higher than or equal to m’s and half have lower or equal priority. If there are an even number of elements in Q, the half with lower priority will have one more element. Complete the function median that computes the median element of a priority queue Q according to this definition, where “larger” means “having higher priority”.
elem median(pq_t Q)
//@requires Q != NULL && !pq_empty(Q);
{
return
;
}
Task 2.10
Assume that the priority function stored in the priority queue Q runs in constant time and that Q contains n elements. What is the worst-case asymptotic complexity of the call median(Q)?
O( )