Midterm II Exam 15 122 Principles of Imperative Computation Frank Pfenning Tom Cortina William Lovas November 4 2010 Name Andrew ID Section Instructions This exam is closed book with one sheet of notes permitted You have 80 minutes to complete the exam There are 4 problems Read each problem carefully before attempting to solve it Consider writing out programs on scratch paper first Red black Ropes trees BDDs Heapsort Prob 1 Prob 2 Prob 3 Prob 4 Total 40 40 30 40 150 Score Max Grader 1 1 Ropes 40 pts In C0 and C strings are typically represented as arrays of characters This allows constant time access of a character at an arbitrary position but it also has some disadvantages In particular concatenating two strings function string join is an expensive operation since we have to create a new character array and copy the two given strings into the new array character by character Task 1 10 pts What is the asymptotic complexity of the following loop as a function of n Assume that string fromint is a constant time operation string string fromarray int A int n requires 0 n n length A string s int i for i 0 i n i loop invariant 0 i i n s string join s string fromint A i return string join s The data structure of ropes attempts to improve efficiency of concatenation by representing strings as binary trees where the leaves contain ordinary strings and the intermediate nodes represent concatenations For example the string totally efficient might look as follows among many other possibilities totally ef ci ent Note that ordinary strings are only stored at the leaves Assuming no rebalancing concatenation of ropes is a constant time operation 2 Task 2 10 pts Assuming no rebalancing show the final result of concatenating the rope above first on the left with then on the right with to form a rope for the string totally efficient Task 3 10 pts Describe what additional information you might store in the nodes so that accessing the ith character in a string of length n represented by a rope is O log n if the rope is balanced 3 Task 4 10 pts Carefully describe the invariant for your data structure You do not need to write code to check it but your description should be precise and detailed enough that it would be clear how to write the code 4 2 Red Black Trees 40 pts The transformation below from the tree on the left to the tree on the right we called a double rotation It was used in rebalancing after insertion into a red black tree We assume keys are integers and x y and z are keys for the three nodes shown explicitly Task 1 10 pts Show that the name double rotation is justified by drawing an intermediate tree between the two so that each step is a single rotation Try to obey the data structure invariants as much as possible but see Task 3 x y z T1 x y T2 z T4 T1 T3 T2 T3 T4 red node black node Task 2 20 pts Assume that first tree satisfies all red black tree invariants except for the color invariant at y whose parent is also red Also assume that the first tree has no restriction on keys at the root interval and black height h Fill in the following table indicating the bounding intervals and the black height for each subtree Tree Interval Black Height T1 T2 T3 T4 5 Task 3 10 pts Under the same assumptions as in Task 2 explain which red black tree invariants hold for the tree you drew in the middle and which ones are violated and where 6 3 Binary Decision Diagrams 30 pts Task 1 10 pts Draw a binary decision tree not a BDD for the boolean function with arguments x1 x2 and x3 that returns true if and only if exactly two of the inputs are true It should test the variables in the given order 7 Task 2 20 pts Draw a reduced ordered binary decision diagram ROBDD for the boolean function above again using the given variable ordering Show intermediate steps in the reduction from the tree to the ROBDD for partial credit in case your final result is not quite correct 8 4 Heapsort 40 pts We can use the invariant behind heaps in order to implement an in place sorting algorithm for arrays called heapsort For simplicity we use max heaps which satisfy Max Heap Ordering Invariant Each node except for the root must be less or equal to its parent This guarantees that a maximal element is at the root of the heap rather than a minimal one as we did in lecture The algorithm proceeds in two phases In phase one we build up a heap spanning the whole array in phase two we successively delete the maximum element from the heap and move it the end Here is our implementation written compactly with only pre and post conditions but no loop invariants or assertions Note that we only sort the range A 1 n ignoring A 0 void heapsort int A int n requires 1 n n length A ensures is sorted A 1 n int i for i 2 i n i sift up A i i 1 for i n 1 2 i i swap A 1 i sift down A 1 i The functions sift up and sift down are like the functions we wrote in lecture except that they take an array as a first argument and what we called H next the index right after the last element currently in the heap as the third argument The pre and post conditions for both functions are given below Your main task will be to enrich this code with invariants and assertions You should assume the following functions bool bool bool bool is heap int A int n is heap except up int A int i int n is heap except down int A int i int n is sorted int A int lower int upper with the following interpretation is heap A n means that the range A 1 n satisfies the heap invariant is heap except up A i n means that the range A 1 n satisfies the heap invariant except that A i which must be in the heap may be greater than its parent is heap except down A i n means that the range A 1 n satisfies the heap invariant except that A i which must be in the heap may be less than one or both of its children 9 is sorted A lower upper means that the range A lower upper is sorted in increasing order Here are the pre and post conditions for the sift up and sift down functions that are called from heapsort void sift up int A int i int n requires is heap except up A i n ensures is heap A n void sift down int A int i int n requires is heap except down A i n …