CMPS 282 Final, Spring 2006

CMPS 282 — Software Engineering FINAL EXAM 2 hours June 13, 2006, 3:00 pm Please draw a horizontal line across the page between the answers to each question 1. (18 points) The following piece of code takes inputs a, b, c and produces outputs x, y. All variables are reals. SQRT is a library procedure that computes the square root. You may assume that SQRT is correct. if a ̸= 0 then if b ∗ b − 4 ∗ a ∗ c ≥ 0 then x = ( −b + SQRT (b ∗ b − 4 ∗ a ∗ c) )/(2 ∗ a) y = 0 else x = (−b)/(2 ∗ a) y = SQRT (4 ∗ a ∗ c − b ∗ b)/(2 ∗ a) endif else x = −c/b y = 0 endif (a) (8 points) How many tests do you need to test this code. Answer with a number. (b) (10 points) Give a set of test cases to test this code. For each test case, specify: the inputs a, b, c the expected outputs x, y 2. (30 points) Consider a system serving generic user requests. Users are divided into 4 groups: A, B, C, D. A user’s class is indicated by a predicate user, e.g., user(Joe, B) is true iff Joe is a user in group B, and false otherwise (Joe is a user in some other group, or Joe is not a user at all). We define also the following predicates: • pending(x, r): user x has submitted a request r, which has not been serviced. r is called a pending request. • working(y, r): worker y is working on request r • completed(r): request r has been completely serviced State the following constraints in logic: (C1) (15 points) If some user in class A has a pending request, then no one should be working on a request of a class B user. (C2) (15 points) A worker cannot work on two requests at once. 1 3. (20 points) We wish to implement a system that satisfies both of the constraints in question 2, along with the following two more constraints: (C3). A class A user can submit a request at any time (C4). Once a worker starts working on a request, that same worker keeps working on the request until the request is completed. (a) (10 points) Is this doable? Answer yes or no (b) (10 points) Justify your answer to (a) Hint: you do not need to answer question 2 first. You can answer this question using only the meaning of the constraints as stated in English. 4. (32 points) Consider the following specification for a procedure X that computes the square root x of a real variable y: ⟨0 ≤ y < MAX⟩ X ⟨−ϵ < x2 − y < ϵ⟩ MAX is the largest floating point numeral that can be represented in the real data type. Instead of implementing X ourselves, we are going to replace X with a procedure from an existing library. For each of the following library procedures A, B, C, D, we give the specification. State which ones can or cannot be used to replace X. Justify your answer with a short explanation. (a) (8 points) ⟨0 < y < MAX⟩ A ⟨−ϵ < x2 − y < ϵ⟩ (b) (8 points) ⟨0 ≤ y < MAX⟩ B ⟨−ϵ < x2 − y < 2 ∗ ϵ⟩ (c) (8 points) ⟨0 ≤ y < MAX⟩ C ⟨−ϵ < x2 − y < ϵ⟩ (d) (8 points) ⟨0 ≤ y < MAX⟩ D ⟨−ϵ/2 < x2 − y < ϵ⟩ 2