CMPS 282 Final, Spring 2008

CMPS 282 — Software Engineering SAMPLE FINAL EXAM 2 hours Please draw a horizontal line across the page between the answers to each question You may refer to the following during the exam: • the course textbook • the course lecture notes • your homework solutions • any notes that you have taken in class You may not refer to any other materials. Good luck! 1. (20 points) (a) (10 points) Consider the data model given in figure 1. D A B C Figure 1: Data model for question 1 (a) What can you say about the relationship between the sets A, B, C, and D? Solution. From the data model graph, A ⊆ B ⊆ C ⊆ D ⊆ A. Hence A = B = C = D. (b) (10 points) Consider the data model given in figure 2. Consider the derived relation r3(x, y) ≜ (∃z : r1(x, z) ∧ r2(y, z)). To how many elements of Y can an element of X be related to, in general? 1 Z X ! Y ! r1 r2 Figure 2: Data model for question 1 (b) Solution. For each x ∈ X, there is exactly one z ∈ Z that x is related to by r1. Many y can be related by r2 to this one z. Hence the answer is that x can be related to many y, i.e., 0 or more. 2. (20 points) You are given the following takes(s, c) is a predicate that is true iff student s is taking course c level(c) is a function that gives the level of a student (freshman, sophomore, junior, or senior) State the following in first order logic: (a) (5 points) every course is taken by at least one student Solution. ∀ c : Course ∃ s : Student [takes(s, c)] (b) (5 points) every student takes at least two different courses Solution. ∀ s : Student ∃ c1, c2 : Course [c1 ̸= c2 ∧ takes(s, c1) ∧ takes(s, c2)] (c) (10 points) if two students take the same course, then they are in the same level Solution. ∀ s1, s2 : Student [ (∃ c : Course [takes(s, c1) ∧ takes(s, c2)]) ⇒ level(s1) = level(s2) ] 3. (40 points) Consider the file system example discussed in class. (a) (10 points) State the following constraint in logic: No two directory entries in the system have the same contents Solution. ¬∃ e1, e2 : Entry [e1 ̸= e2 ∧ e1.contents = e2.contents] Now suppose we wish to add links to the file system example. Assume that we now add a Link data type to the File system, We also add a relation LinkName from Link to Name, and a relation LinkContents from Link to FSObject. These give the name of the link, and the file system object that the link points to, respectively. (b) (15 points) 2 State the following constraint in logic: Every link points to a file system object that is reachable from the root Solution. ∀ l : Link ∀ o : FSObject[ l.contents = o ⇒ Root ∈ ancestors(o) ] (c) (15 points) We introduce a deleteFile operation that removes a file object from the system. What is an appropriate precondition for deleteFile? Make sure that all constraints are preserved. The appropriate precondition is that no link points to the file. In logic: Solution. ∀ l : Link [l.contents ̸= f] 4. (20 points) Let / denote integer division with truncation, e.g., 11/2 = 5. Assume that all variables are integer valued, and all ranges of quantification are over integers. Define even(a) = (∃b : a = 2 ∗ b), odd(a) = ¬even(a). State which of the following Hoare triples are valid. Answer “valid” or “not valid” (5 points each). (a) {even(y) ∧ xy = c} x := x ∗ x; y := y/2 {xy = c} Solution. valid (b) {odd(y) ∧ xy = c} x := x ∗ x; y := y/2 {xy = c} Solution. not valid (c) {xy = c} x := x ∗ x; y := y/2 {xy = c} Solution. not valid (d) ⟨y > 0 ∧ odd(y)⟩ while y ̸= 0 do x := x ∗ d; y := y − 2 endwhile ⟨true⟩ Solution. not valid 3