CompSci 171: Introduction to Artificial IntelligenceFinal Exam: 4.00-6.00 pm, June 12, 2007Instructor: Max WellingCLOSED BOOKCompSci 171: Introduction to Artificial IntelligenceFinal Exam: 4.00-6.00 pm, June 12, 2007Instructor: Max WellingCLOSED BOOK1. [20 points] ProbabilitiesConsider the following joint probability table for the random variables A,B,C.A B C P(A, B, C)False False False 0.05False False True 0.10False True False 0.03False True True 0.25True False False 0.15True False True 0.02True True False 0.07True True True 0.331a) [5pts] Compute the probability P(A = true)? 1b) [5pts] Compute the probability P(A=true, B=false)1c) [5pts] Compute the probability P(A=true|C=true)1d) [5pts] Compute the probability P(A=true, B=false|C=true)2. [20 points] Conditional IndependenceAssume we have one disease variable (call it D) and two symptoms (call them S1 and S2). For simplicity, assume that the S-variables have three possible values (e.g., low, medium, and high) and that D has two values (true or false).The doctor observes 300 patients and finds:D was true 100 times and for these cases:S1=low 50 times, S1=med 30 times, and S1 = high 20 timesS2=low 10 times, S2=med 80 times, and S2 = high 10 timesD was false 200 times and for these cases:S1=low 20 times, S1=med 80 times, and S1 = high 100 timesS2=low 180 times, S2=med 10 times, and S2 = high 10 times2a) [10pts] Estimate the following probabilities from these data: P(S1=low|D=true), P(S1=low|D=false), P(S2=low|D=true), P(S2=low|D=false), P(D=true), P(D=false). Joe walks into the doctor’s office. The doctor finds that: S1=low and S2=low. Assume conditional independence of S1 and S2 given D.2b) [10pts] Is it more likely that Joe has the disease (D=true) or that he doesn’t have the disease (D=false) given the information S1=low and S2=low? (hint: you don’t need the normalization constant).3. [20 points] First Order Logic Translate the following English sentences into First Order Logic:3a) [4pts] Every election has a winner3b) [4pts] There are no tall trees with short roots 3c) [4pts] There are exactly 2 princes in Monte Carlo3d) [4pts] Everyone has a father and a mother3e) [4pts] There is someone who has a brother4. [20 points] Propositional Logic4a) [10 pts] Bring the following sentence in propositional logic in conjunctive normal form: ( )A B C D� � � �4b) [10pts] Consider the following knowledge base: ( ) ( ) ( ) ( )KB A B C D C B D= �� � � �� � � �.And the following query: A Ca = �Prove using the method of resolution that the query is entailed by the knowledge base.5. Search, CSP, Games 5a) [5pts] Under what conditions on the step-cost is “uniform-cost search” an optimal search algorithm?5b) [5pts] Compute the gradient of 21( , ) (3 7)2C x y xy= - and provide pseudo-code forthe gradient descent algorithm that minimizes C(x,y). 5c) [5pts] Explain the “minimum remaining values heuristic” for CSPs.5d) [5pts] Is the following statement true: “ Time-complexity for mini-max search witha b- pruning is
View Full Document
Unlocking...