Final Exam 15 122 Principles of Imperative Computation Frank Pfenning May 3 2012 Name Andrew ID Section Instructions This exam is closed book with one double sided sheet of notes permitted You have 3 hours to complete the exam There are 6 problems Read each problem carefully before attempting to solve it Do not spend too much time on any one problem Consider if you might want to skip a problem on a first pass and return to it later Consider writing out programs or diagrams on scratch paper first Spanning Integers Big O BDDs Interfaces Union Find Trees Prob 1 Prob 2 Prob 3 Prob 4 Prob 5 Prob 6 Total 45 35 40 35 60 35 250 Score Max Grader 1 1 Integers 45 pts Task 1 15 pts For each of the following expressions in C indicate whether they are always true If not give a counterexample and state whether the counterexample is guaranteed to be false or undefined in C You should not assume any particular size for ints and state your counterexamples in terms of INT MAX INT MIN and UINT MAX Assume we are in the scope of declarations int x unsigned int u so x and u are properly initialized to arbitrary values We have filled in one row for you C expression Always true If no counterexample False or undefined x 1 1 x no x INT MAX undefined x 0 x 0 x 0 x 0 u 1 u 1 u 1 u u 1 1 u Task 2 10 pts Write a C function safe add which aborts if the addition would raise an overflow and otherwise returns the sum You should not assume any particular size for integers but use INT MAX and INT MIN as needed int safe add int x int y 2 Task 3 10 pts Write a C function mod add which implements two s complement modular addition on its arguments As in Task 1 you should not assume any particular size for integers On the other hand you may assume values of type int and unsigned int have the same size and that values of type int are in two s complement representation int mod add int x int y Task 4 10 pts Write a C function extend add which adds two ints and returns a result of type long long int Since a long long int must be large enough to hold the result of adding two ints the result should always be defined long long int extend add int x int y 3 2 Big O 35 pts Task 1 15 pts Define the big O notation O f n g n and briefly state the two key ideas behind this definition in two sentences Task 2 10 pts For each of the following indicate if the statement is true or false 1 O n2 1024n 32 O 31n2 34 2 O n log n O n 3 O n O n log n 4 O 32 O 232 n 5 O 2n O 22 Task 3 10 pts You observe the following timings when executing an implementation of sorting on randomly chosen arrays of size n Form a conjecture about the asymptotic running time of each implementation n 215 216 217 218 O A time in secs 10 23 20 51 41 99 85 27 n 215 216 217 218 B time in secs 22 36 90 55 368 97 1723 03 O n 215 216 217 218 C time in secs 2 01 5 03 12 77 29 93 O Which would be preferable for inputs of about 1 million elements Circle one A B C 4 3 Binary Decision Diagrams 40 pts An important operation in the construction of digital circuits is the nand gate which inputs booleans x1 and x2 and outputs x1 x2 We write nand x1 x2 In C this might be defined as bool nand bool x1 bool x2 return x1 x2 Task 1 15 pts Construct a ordered binary decision tree without sharing for nand x1 nand x2 x3 where the variables are tested in the order x1 x2 x3 x1 0 0 0 x3 1 x2 0 1 x2 0 1 x3 0 1 5 x3 1 1 0 x3 1 Task 2 10 pts Ordered binary decision diagrams OBDD differ from binary decision trees in that they exploit sharing State the two conditions on an OBDD that are required for a reduced ordered binary decision diagram ROBDD 1 2 Task 3 15 pts Convert the binary decision tree from Task 1 into an ROBDD where the variables are tested in the same order You only need to show the final ROBDD but if you show intermediate steps we may more easily assign partial credit 6 4 Interfaces 35 pts We now consider the C implementation of ROBDDs with hash tables A node in an OBDD is implemented with the following struct struct node int var struct node lo struct node hi int result int refcount typedef struct node node testing variable x i successor for x i 0 successor for x i 1 result 0 or 1 reference count We have the following basic invariants 1 For an interior node u we have u lo NULL and u hi NULL 2 For a leaf node u we have u lo NULL and u hi NULL and u result 0 or u result 1 3 Since the variables must be tested in order the low and high successor of an interior node u must have a higher variable number than u All interior nodes are created with a function node make node int var node low node high In order to make sure that the OBDDs we construct are reduced we use a hash table If an interior node testing the same variable with the same low and high successors has already been constructed before we return the one stored in the hash table We use the following hash table interface typedef void ht key typedef void ht elem typedef struct ht ht ht ht new int init size ht key elem key ht elem e bool key equal ht key k1 ht key k2 int key hash ht key k int m void ht insert ht H ht elem e ht elem ht search ht H ht key k void ht free ht H void elem free ht elem e 7 Task 1 5 pts Define an appropriate client side type key in C Task 2 5 pts Define an appropriate client side type elem in C Task 3 10 pts Define an appropriate client side function elem key in C elem key u Task 4 10 pts Define an appropriate client side function key equal in C bool key equal u v Task 5 5 pts Assume you have also defined an appropriate function key hash Show the function call the client needs to construct an appropriate empty hash table of initial size 1024 ht new 1024 8 5 Union Find 60 pts In this problem we reconsider the union find data structure used to maintain equivalence classes of integers …