Computer science

1 Questions 1. A computer knowledge base about films and user preferences uses firstorder predicate logic to store facts. It contains the following predicates Predicate Meaning Owns(p, f) Person p owns a copy of film f. Acts(p, r, f) Person p acts the role of r in film f. Directs(p, f) Personp directs film f. Prefers(p, f1, f2) Personp likes film f1 more than film f2. It contains five (possibly overlapping) sets of constants: Set Label Example elements Directors D Spielberg, Nolan Actors A MichaelCaine, CarrieFisher Films F TheLadyVanishes, Inception Roles R PrincessLeia, Batman Users U Mary, Claire, Bob Express the following English sentences in predicate logic so they could be stored in the computer database. a) Mark Hamill acts the role of Luke Skywalker in Star Wars: A New Hope. b) Mary owns a copy of The Lady Vanishes but does not own a copy of Casablanca. c) Mark Hamill acts some role in Star Wars: A New Hope. d) All films Alice owns are directed by Stephen Spielberg. e) Mark Hamill and Harrison Ford act in at least one film together. f) Jane owns at least one film directed by Quentin Tarantino. g) No films directed by Christopher Nolan star Leonardo DiCaprio, except for Inception. h) Claire prefers all films with Carrie Fisher in to Inception. i) Alfred Hitchcock acts in some films that he directs. j) John prefers all of Stephen Spielberg’s films to Alfred Hitchcock’s. (total: 20 marks) 2 2. Translate the following predicate logic expressions intended for the database of question 1, into good English. a) Owns(Claire,Gravity) b) Owns(John, Inception) ^ Owns(Mark, Inception) c) ? 9f 2 F(Owns(Claire(f) ^ Owns(Jo, f)) d) 9f 2 F, r 2RActs(ChristianBale, r, f) e) 8f1, f2 2 F (Directs(Spielberg, f1) ^ Directs(Nolan, f2) =) Prefers(Mark, f1, f2)) f) 8f 2 F (Owns(Mark, f) ? Owns(Bob, f)) g) 8f 2 F (9r 2R(Acts(BruceLee, r, f) =) Owns(Mark, f))) h) 8f 2 F (? 9r 2R(Acts(CarrieFisher, r, f) ^ Directs(Hitchcock, f))) i) 8f 2 F (Owns(Mark, f) =) Owns(John, f) _ (f = Gravity)) j) 9a 2 A(8f 2 F (9r 2R(Acts(a, r, f) =) Owns(Claire, f)))) (total: 20 marks) 3 3. a) Express the logic circuits in Figure 1 and Figure 2 as logical expressions. Use your knowledge of the Laws of Logical Equivalence to show these two expressions are the same, stating which laws you are using at each point. Confirm this by showing the outputs of both circuits in the same truth table. (10 marks) b) Produce a truth table for Figure 3 showing how the values of A1, A2, A3 and S depend on the inputs P,Q and R. Arrange your table so that the rows count up values of P Q and R in binary order 000, 001, 010, . . . 111. Show that the logical expression ? P _ ? R has the same truth values as the given circuit. (5 marks) c) Express the output column of the table below as a function of P, Q and R. Hence design a circuit that has three inputs P, Q and R and produces the desired output, using AND, OR and NOT gates. (5 marks) P Q R output 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 0 (total: 20 marks) P Q S Figure 1: Version 1 of a circuit 4 P Q S Figure 2: Version 2 of a circuit P Q R A1 A2 A3 S Figure 3: A circuit to analyse 4. a) Which two inference rules do the following two arguments use: “When it is cold my car breaks down. My car hasn’t broken down today. Therefore it’s not cold today”. and “If the criminal entered by the window then he left fingerprints. The criminal did enter by the window. Therefore he left fingerprints.” (2 marks) b) Write out a formal proof following the format in the notes, of the argument that P _ Q and ? Q allow the conclusion P. (3 marks) c) Convert the following argument to a formal proof following the format of the notes. Use the letters suggested to stand for the corresponding propositions in the text. 5 If the software contains a serious bug (B), or the hardware is faulty (H) then the code will generate an error (E). The tests passed (T). An error would cause the tests to fail. Therefore the software does not contain a serious bug. (5 marks) d) In the Wumpus World that was presented in your course notes, assume bottomless pits occur in a cell with probability 0.02, independent of other cells, and cause breezes in neighbouring cells. Given cell (1,1) is clear and there is a breeze in cells (1,2) and (2,1), what is the probability of a pit in cell (3,1)? Given the same evidence, what is the probability of a pit in cell (2,2)? (5 marks) e) A computer virus checker is 98% accurate, correctly detecting viruses 98% of the time, and correctly not detecting viruses 98% of the time. The virus software detects ScourgeMaster, a serious virus, on your computer. However you know only 1 in 200,000 computers is infected by this virus. What is the probability your computer actually has been infected by ScourgeMaster? (5 marks) (total: 20 marks) 6 5. a) Figure 4 shows seven computer centres, and the cost of connecting them in £1000s. Use Prim’s algorithm starting with vertex A, to find the minimum cost spanning tree that connects them, showing your working, and state its cost. (7 marks) Figure 4: Computer network connection costs b) Figure 5 shows the bus fares in pounds to travel between various villages. Use Dijkstra’s algorithm to find the minimum cost journey from A to D and state the path found. Figure 5: Bus fares (7 marks) c) Produce and step through an example to show that if some of the weights are negative in a network then Dijkstra’s algorithm fails. (6 marks) (total: 20 marks) 7 6. The run times in seconds of various algorithms (A1,A2,A3,A4,A5) are shown on the graph for inputs of size n, and also given in the table below. Identify which curves are proportional to n, logn, n2, n3 and 1.2n, giving your reasoning. (No marks, if no valid reason given). n A1 A2 A3 A4 A5 5 3.7151 0.1000 0.0012 0.0063 0.7000 10 5.3151 0.4000 0.0031 0.0500 1.4000 15 6.2510 0.9000 0.0077 0.1688 2.1000 20 6.9151 1.6000 0.0192 0.4000 2.8000 25 7.4302 2.5000 0.0477 0.7813 3.5000 30 7.8510 3.6000 0.1187 1.3500 4.2000 35 8.2069 4.9000 0.2953 2.1438 4.9000 40 8.5151 6.4000 0.7349 3.2000 5.6000 45 8.7870 8.1000 1.8286 4.5563 6.3000 50 9.0302 10.000 4.5502 6.2500 7.0000 (total: 20 marks) 8 7. Draw finite state automata that accept the following, in each case also giving a regular expression matching exactly the accepted strings a) all binary strings starting 101. (4 marks) b) all binary strings containing exactly three 0s. (4 marks) c) all binary strings containing a substring 111. (4 marks) d) all binary strings ending 11 or 00. (4 marks) e) all binary strings starting 0 and containing an odd number of 1s. (4 marks)