Midterm I Exam15-122 Principles of Imperative ComputationFrank PfenningFebruary 17, 2011Name: 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.• 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.Mod.arith. Search Stacks QueuesProb 1 Prob 2 Prob 3 Prob 4 TotalScoreMax 20 30 25 25 100Grader11 Modular Arithmetic (20 pts)In C0, values of type int are defined to have 32 bits. In this problem we work with a version ofC0 called C8 where values of type int are defined to have only 8 bits. In other respects it is thesame as C0. All integer operations are still in two’s complement arithmetic, but now modulo 28.All bitwise operations are still bitwise, except on only 8 bit words instead of 32 bit words.Task 1 (10 pts). Fill in the missing quantities, in the specified notation.a. The minimal negative integer, in decimal:b. The maximal positive integer, in decimal:c. −2, in hexadecimal: 0xd. 19, in hexadecimal: 0xe. 0x45, in decimal:Task 2 (10 pts). Assume int x has been declared and initialized to an unknown value. For eachof the following, indicate if the expression always evaluates to true, or if it could sometimes befalse. In the latter case, indicate a counterexample in C8 by giving a value for x that falsifies theclaim. You may use decimal or hexadecimal notation.a. x+1 > xb. (((x>>1)<<1) | (x&1)) == xc. (x ^ (~x)) == 0d. x <= (1<<7)-1e. x+x == 2*x22 Search Algorithms (30 pts)We explore the application of ideas behind linear and binary search in a new context. We are givenan array of integers subject only to the requirement that the first integer in the array is negative(A[0] < 0) and the last integer in the array is nonnegative (A[n − 1] ≥ 0). We cannot assume thatthe array is sorted. We want to find an index i in the array such that A[i] < 0 and A[i + 1] ≥ 0.The following is a function to find such an index, searching through the array from left to right.int find1(int[] A, int n)//@requires 2 <= n && n <= \length(A);//@requires A[0] < 0 && 0 <= A[n-1];//@ensures 0 <= \result && \result < n-1;//@ensures A[\result] < 0 && 0 <= A[\result+1];{for (int i = 0; i < n-1; i++)//@loop_invariant _____________________________________ ;//@loop_invariant _____________________________________ ;{if (0 <= A[i+1]) return i;}/* should never get here *///@assert false;return -1;}Task 1 (4 pts). Fill in loop invariants. Your loop invariants (together with the function precondi-tions) should be strong enough to guarantee the postconditions.Task 2 (1 pts). What is the worst-case asymptotic complexity of the find1 as a function of n, inbig-O notation? You do not need to justify your answer.Task 3 (2 pts). Show that your loop invariants hold initially.3Task 4 (5 pts). Show that your loop invariants are preserved by one iteration of the loop.Task 5 (5 pts). Show that your loop invariants (together with the function preconditions) imply thepostconditions. You may assume without proof that the statement after the loop is never reached,so that the final return statement can never be executed.4Task 6 (10 pts). Now apply the idea behind binary search to complete the following function tosatisfy the same pre- and post-condition. You do not need to prove this, but we suggest that youreason it out to yourself to make sure your function and the invariants are correct.int find2(int[] A, int n)// pre- and post-conditions as for find1{ int lower = 0;int upper = n-1;while (________________________)//@loop_invariant __________________________________________________ ;//@loop_invariant __________________________________________________ ;{ int mid = lower + (upper-lower)/2;if (________________________)__________________________ ;else__________________________ ;}return _______________ ;}Task 7 (2 pts). Does find2 always return the same answer as find1? Explain your answer in oneor two sentences.Task 8 (1 pts). What is the worst-case asymptotic complexity of find2 as a function of n, in big-Onotation? You do not need to justify your answer.53 Stacks (25 pts)In this problem we will implement a simple text buffer with some editing functions. A text bufferconsists of a sequence of characters with a distinguished position called the point. A buffer withcharacters abcdef and the point between b and c is written asa b|c d e fThe abstract interface has operations to create a new buffer, move point forward or backward, andto insert or delete character at point. Each operation is explained in detail where you are asked toimplement it. All operations should be constant time (O(1)).typedef struct tbuf* tbuf;tbuf tbuf_new(); /* create new text buffer */void insert_char(tbuf B, char c); /* insert character at point */void delete_char(tbuf B); /* delete character before point */void forward_char(tbuf B); /* move point forward one char */void backward_char(tbuf B); /* move point backward one char */// ... others elidedWe are implementing a text buffer by two stacks, one with the characters before the point, andone with the characters after the point. The text buffera b|c d e fabove would be represented by the following two stacks:!b!!a!!c!!d!!e!!f!before!point!a.er!point!The before stack has two elements, with b on top; the after stack has four elements with c on top.6The implementation will use stacks of characters according to the following interface as devel-oped in lecture.typedef char elem;typedef struct stack* stack;bool stack_empty(stack S); /* O(1) */stack stack_new(); /* O(1) */void push(stack S, elem e); /* O(1) */elem pop(stack S) /* O(1) *///@requires !stack_empty(S);;As explained, a text buffer is represented by a struct containing two stacks, before and after.struct tbuf {stack before;stack after;};The following function checks if B is a valid text buffer. Your functions must preserve this prop-erty.bool is_tbuf(tbuf B) {if (B == NULL) return false;return (B->before != NULL && B->after != NULL);}Task 1 (5 pts). Write a function to create a new (empty) text buffer.tbuf tbuf_new()//@ensure is_tbuf(\result);{}7In response to the questions below, you do not need to write annotations, but you are free todo so if you wish. You may assume that all function arguments of type tbuf are valid text buffers(according to is_tbuf) and your functions should ensure that they