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. A B C D Figure 1: Data model for question 1 (a) What can you say about the relationship between the sets A, B, C, and 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) 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 (b) (5 points) every student takes at least two different courses (c) (10 points) if two students take the same course, then they are in the same level 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 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) State the following constraint in logic: Every link points to a file system object that is reachable from the root (c) (15 points) We introduce a deleteFile operation removes a file object from the system. What is an appropriate precondition for deleteFile? Make sure that all constraints are preserved. 2 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} (b) {odd(y) ∧ xy = c} x := x ∗ x; y := y/2 {xy = c} (c) {xy = c} x := x ∗ x; y := y/2 {xy = c} (d) ⟨y > 0 ∧ odd(y)⟩ while y ̸= 0 do x := x ∗ d; y := y − 2 endwhile ⟨true⟩ 3