Midterm I Exam 15 122 Principles of Imperative Computation Frank Pfenning February 17 2011 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 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 Queues Prob 1 Prob 2 Prob 3 Prob 4 Total 20 30 25 25 100 Score Max Grader 1 1 Modular Arithmetic 20 pts In C0 values of type int are defined to have 32 bits In this problem we work with a version of C0 called C8 where values of type int are defined to have only 8 bits In other respects it is the same 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 0x d 19 in hexadecimal 0x e 0x45 in decimal Task 2 10 pts Assume int x has been declared and initialized to an unknown value For each of the following indicate if the expression always evaluates to true or if it could sometimes be false In the latter case indicate a counterexample in C8 by giving a value for x that falsifies the claim You may use decimal or hexadecimal notation a x 1 x b x 1 1 x 1 x c x x 0 d x 1 7 1 e x x 2 x 2 2 Search Algorithms 30 pts We explore the application of ideas behind linear and binary search in a new context We are given an 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 that the 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 preconditions 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 in big O notation You do not need to justify your answer Task 3 2 pts Show that your loop invariants hold initially 3 Task 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 the postconditions You may assume without proof that the statement after the loop is never reached so that the final return statement can never be executed 4 Task 6 10 pts Now apply the idea behind binary search to complete the following function to satisfy the same pre and post condition You do not need to prove this but we suggest that you reason 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 one or two sentences Task 8 1 pts What is the worst case asymptotic complexity of find2 as a function of n in big O notation You do not need to justify your answer 5 3 Stacks 25 pts In this problem we will implement a simple text buffer with some editing functions A text buffer consists of a sequence of characters with a distinguished position called the point A buffer with characters abcdef and the point between b and c is written as a b c d e f The abstract interface has operations to create a new buffer move point forward or backward and to insert or delete character at point Each operation is explained in detail where you are asked to implement it All operations should be constant time O 1 typedef struct tbuf tbuf tbuf tbuf new void insert char tbuf B char c void delete char tbuf B void forward char tbuf B void backward char tbuf B others elided create new text buffer insert character at point delete character before point move point forward one char move point backward one char We are implementing a text buffer by two stacks one with the characters before the point and one with the characters after the point The text buffer a b c d e f above would be represented by the following two stacks b c a 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 6 The implementation will use stacks of characters according to the following interface as developed in lecture typedef char elem typedef struct stack stack bool stack empty stack S stack stack new void push stack S elem e elem pop stack S requires stack empty S O 1 O 1 O 1 O 1 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 property 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 7 In response to the questions below you do not need to write annotations but you are free to do 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 remain valid Task 2 5 pts Write a function to insert a character into a text buffer before point For example if a text buffer B contains a b c d e f then after insert char B w it should have the form a b w c d e f void insert char tbuf B …