Midterm I Exam 15 122 Principles of Imperative Computation Frank Pfenning Tom Cortina William Lovas September 30 2010 Name Andrew ID 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 Searching Stacks sorting queues Linked lists Modular arith JVM Prob 1 Prob 2 Prob 3 Prob 4 Total 40 50 30 30 150 Score Max Grader 1 1 Searching and Sorting 40 pts Shown here is the binary search program from Homework Assignment 2 that has been repaired except that the condition before the return statements at the end of the function has been omitted A copy of this code is provided on the last sheet which you may tear off and use for reference while working on Tasks 2 and 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 int binsearch smallest int x int A int n requires 0 n n length A requires is sorted A n ensures result 1 is in x A n A result x result 0 A result 1 x int lower 0 int upper n while lower upper loop invariant 0 lower lower upper upper n loop invariant lower 0 A lower 1 x loop invariant upper n A upper x int mid lower upper lower 2 if A mid x lower mid 1 else assert A mid x upper mid assert lower upper 18 if 19 20 21 22 return lower else return 1 Task 1 10 pts Fill in the missing condition at the end of the function so that the proper value is returned 2 The next two questions ask you to show that the postcondition of the function is satisfied in two parts For each part reason from the function s precondition loop invariants the explicit assertion and the condition you inserted You can refer to annotations by the line they appear in Task 2 10 pts If the function returns some result i for 0 i n show that either i 0 or A i 1 x Task 3 10 pts If the function returns 1 show that x cannot be in the array To simplify the reasoning you may assume that lower 0 and upper n at line 17 3 Task 4 10 pts The merge function employed by mergesort as discussed in lecture allocates some fresh temporary space each time it is called If we call mergesort with an array of size n how much temporary space does mergesort allocate overall Give your answer in big O notation and briefly explain your reasoning 4 2 Stacks and Queues 50 pts Consider the following interface to stacks as introduced in class typedef struct stack stack stack s new bool s empty stack S void push int x stack S int pop stack S O 1 O 1 O 1 O 1 create new empty stack check if stack is empty push element onto stack pop element from stack In these problem 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 stack are non NULL Task 1 10 pts Write a function rev stack S stack D We require that D is originally empty When rev returns D should contain the elements of S in reverse order and S should be empty void rev stack S stack D requires s empty D ensures s empty S 5 Now we design a new representation of queues A queue will be a pair of two stacks in and out We always add elements to in and always remove them from out When necessary we can reverse the in queue to obtain out by calling the function you wrote above struct queue stack in stack out typedef struct queue queue Task 2 10 pts Write the enq function void enq queue Q int x Task 3 10 pts Write the deq function Make sure to abort the computation using an appropriate assert statement if deq is called incorrectly int deq queue Q 6 Now we analyze the complexity of this data structure We are counting the total number of push and pop operations on the underlying stack Task 4 10 pts What is the worst case complexity of a single enq What is the worst case complexity of a single deq Phrase your answer in terms of big O of m where m is the total number of elements already in the queue Task 5 10 pts What is the worst case complexity of a sequence of n operations each of which could be enq or deq Justify your answer using amortized analysis if appropriate 7 3 Linked Lists 30 pts Recall the definition of linked lists with integer data struct list int data struct list next typedef struct list list An alternative to terminating lists with NULL is to terminate them with a self loop We call such a list a sloop For example the following is a sloop of length 3 data next 1 2 3 X Task 1 10 pts Write a function is sloop list p to test if p is a sloop that is a linked list terminated by a self loop You should assume that there are no other cycles in the list bool is sloop list p 8 Task 2 10 pts The following program is supposed to add an element to the end of a sloop but it contains three bugs Fix the bugs by clearly modifying a given statement or adding new statements list addend list p int k requires is sloop p ensures is sloop p list q alloc list while p p next loop invariant is sloop p p p next p data k p next q 9 Task 3 10 pts Explain in detail how to use the idea behind the tortoise and the hare algorithm to write a stronger is sloop function than you wrote in Task 1 It should terminate with false on lists containing a cycle unless the cycle has only one node Your description should be concise and complete If you wish you can write code to support the explanation but that is not required 10 4 Modular Arithmetic and JVM 30 pts Task 1 5 pts Implement a function iushr n k which is like n k except that it fills the highest bits with zeros instead of copying the sign bit iushr stands for integer unsigned shift right int iushr int n int k Task 2 5 pts Implement a function oadd x y which is like x y except that it aborts the computation with an appropriate assert statement if we have an overflow Here overflow means that the result would be less than the minimal representable negative number or greater than the maximal representable positive number assuming 32 bit two s complement arithmetic Your code does not need to be particularly efficient int oadd int x int y 11 Now recall the …