Final Exam15-122 Principles of Imperative ComputationFrank PfenningMay 3, 2012Name: 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.SpanningIntegers Big-O BDDs Interfaces Union-Find TreesProb 1 Prob 2 Prob 3 Prob 4 Prob 5 Prob 6 TotalScoreMax 45 35 40 35 60 35 250Grader11. 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 orundefined in C. You should not assume any particular size for ints and state your counterexamplesin terms of INT_MAX, INT_MIN, and UINT_MAX. Assume we are in the scope of declarationsint x = ...;unsigned int u = ...;so x and u are properly initialized to arbitrary values. We have filled in one row for you.C expressionAlways true? If no, counterexample False or undefinedx + 1 == 1 + x no x = INT_MAX undefinedx <= 0 || -x < 0x >= 0 || -x > 0-u - 1 == u ^ -1u - 1 < uu - 1 == -(1 - u)Task 2 (10 pts). Write a C function safe_add which aborts if the addition would raise an overflowand otherwise returns the sum. You should not assume any particular size for integers, but useINT_MAX and INT_MIN as needed.int safe_add(int x, int y) {}2Task 3 (10 pts). Write a C function mod_add which implements two’s complement modular addi-tion on its arguments. As in Task 1, you should not assume any particular size for integers. Onthe other hand, you may assume values of type int and unsigned int have the same size, andthat 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 typelong long int. Since a long long int must be large enough to hold the result of adding twoints, the result should always be defined.long long int extend_add(int x, int y) {}32. Big-O (35 pts)Task 1 (15 pts). Define the big-O notationO(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)5. O(2n) = O(22n)Task 3 (10 pts). You observe the following timings when executing an implementation of sortingon randomly chosen arrays of size n. Form a conjecture about the asymptotic running time of eachimplementation.Antime (in secs)21510.2321620.5121741.9921885.27O( )Bn time (in secs)21522.3621690.55217368.972181723.03O( )Cn time (in secs)2152.012165.0321712.7721829.93O( )Which would be preferable for inputs of about 1 million elements? Circle one:A B C43. Binary Decision Diagrams (40 pts)An important operation in the construction of digital circuits is the nand-gate, which inputs booleansx1and x2and outputs ¬(x1∧ x2). We write nand(x1, x2). In C, this might be defined asbool 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#x2#x2#0#0#1#1#1#0#x3#1#0#x3#1#0#x3#1#0#x3#1#0#5Task 2 (10 pts). Ordered binary decision diagrams (OBDD) differ from binary decision trees inthat they exploit sharing. State the two conditions on an OBDD that are required for a reducedordered binary decision diagram (ROBDD).1.2.Task 3 (15 pts). Convert the binary decision tree from Task 1 into an ROBDD, where the variablesare tested in the same order. You only need to show the final ROBDD, but if you show intermediatesteps we may more easily assign partial credit.64. Interfaces (35 pts)We now consider the C implementation of ROBDDs with hash tables. A node in an OBDD isimplemented with the following struct.struct node {int var; /* testing variable x_i */struct node* lo; /* successor for x_i = 0 */struct node* hi; /* successor for x_i = 1 */int result; /* result = 0 or 1 */int refcount; /* reference count */};typedef struct node* node;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 oru->result == 1.3. Since the variables must be tested in order, the low and high successor of an interior node umust have a higher variable number than u.All interior nodes are created with a functionnode 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 in-terior node testing the same variable with the same low and high successors has already beenconstructed before, we return the one stored in the hash table.We use the following hash table interfacetypedef 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));7Task 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 func-tion call the client needs to construct an appropriate (empty) hash table of initial size 1024.ht_new(1024, ________________ , _________________ , __________________ )85. Union-Find (60 pts)In this problem we reconsider the union-find data structure used to maintain equivalence classes ofintegers. We say that the representation of an equivalence class has depth d if the longest path froman element in the class to the canonical representative is d. For example, any singleton equivalenceclass has depth 0, and an equivalence class with two elements must have depth 1.Task 1 (5 pts). Initialize the union-find