DOC PREVIEW
Berkeley COMPSCI 188 - CS 188 Midterm

This preview shows page 1 out of 3 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

NAME: SID#: Section: 1CS 188 Introduction to AISpring 2004 Stuart Russell MidtermYou have 50 minutes. The exam is open-book, open-notes. 100 points total. Panic not.ALL QUESTIONS IN THIS EXAM ARE TRUE/FALSE, MULTIPLE-CHOICE, OR SHORT-ANSWER.Mark your answers ON THE EXAM ITSELF. Write your name, SID, and section number at the top of each page.For true/false questions, CIRCLE True OR False.For multiple-choice questions, CIRCLE ALL CORRECT CHOICES (in some cases, there may be more than one).If you are not sure of your answer you may wish to provide a brief explanation.For official use onlyQ. 1 Q. 2 Q. 3 Q. 4 Q. 5 Q. 6 Total/12 /15 /25 /12 /18 /18 /1001. (12 pts.) Agents and Environments(a) (3) True/False: There exist task environments (PEAS) in which some pure reflex agents behave rationally.(b) (3) True/False: There exist task environments (PEAS) in which all pure reflex agents behave irrationally.(c) (3) True/False: The input to an agent program is the same as the input to the corresponding agentfunction.(d) (3) True/False: Every agent function is implementable by some program/machine combination2. (15 pts.) SearchConsider the problem of moving k knights from k starting squares s1, . . . , skto k goal squares g1, . . . , gk, onan unbounded chessboard, subject to the rule that no two knights can land on the same square at the sametime. Each action consists of moving up to k knights simultaneously. We would like to complete the maneuverin the smallest number of actions.(a) (5) What is the maximum branching factor b in this state space?(i) 8k (ii) 9k (iii) 8k(iv) 9k(b) (6) Suppose hiis an admissible heuristic for the problem of moving knight i to goal giby itself. Which ofthe following heuristics are admissible for the k-knight problem?(i) min{h1, . . . , hk} (ii) max{h1, . . . , hk} (iii)Pki = 1hi(c) (4) Which of these is the best heuristic?(i) min{h1, . . . , hk} (ii) max{h1, . . . , hk} (iii)Pki = 1hi23. (25 pts.) CSPs and local searchConsider the problem of placing k knights on an n × n chessboard such that no two knights are attacking eachother, where k is given and k ≤ n2.(a) (5) Choose a CSP formulation. In your formulation, what are the variables?(b) (5) What are the values of each variable?(c) (5) What sets of variables are constrained, and how?(d) (5) Now consider the problem of putting as many knights as possible on the board without any attacks.We will solve this using local search. Briefly describe in English a sensible successor function.(e) (5) Briefly describe in English a sensible objective function.NAME: SID#: Section: 34. (12 pts.) Propositional logicConsider a propositional language with four symbols, A, B, C, and D. How many models are there for each ofthe following sentences?(a) (4) B ∨ C(b) (4) ¬A ∨ ¬B ∨ ¬C ∨ ¬D(c) (4) (A ⇒ B) ∧ A ∧ ¬B ∧ C ∧ D5. (18 pts.) Propositional logicAccording to political pundits, a person who is radical (R) is electable (E) if he/she is conservative (C), butotherwise is not electable.(a) (12) Which of the following are correct representations of this assertion?i. (R ∧ E) ⇐⇒ Cii. R ⇒ (E ⇐⇒ C)iii. R ⇒ ((C ⇒ E) ∨ ¬E)(b) (6) Which of the sentences in (a) can be expressed in Horn form?(i) (ii) (iii)6. (18 pts.) First-Order Logic(a) (12) Which of the following are correct translations of “No two adjacent countries have the same color”?i. ∀x, y ¬Country(x) ∨ ¬Country(y) ∨ ¬Adjacent(x, y) ∨ ¬(Color(x) = Color(y)).ii. ∀x, y (Country(x) ∧ Country(y) ∧ Adjacent(x, y) ∧ ¬(x = y)) ⇒ ¬(Color(x) = Color(y)).iii. ∀x, y Country(x) ∧ Country(y) ∧ Adjacent(x, y) ∧ ¬(Color(x) = Color(y))iv. ∀x, y (Country(x) ∧ Country(y) ∧ Adjacent(x, y)) ⇒ Color(x 6= y).(b) (6) Which of the following are valid sentences?i. (∃x x = x) ⇒ (∀y ∃z y = z).ii. ∀x P (x) ∨ ¬P (x).iii. ∀x Smart(x) ∨ (x =


View Full Document

Berkeley COMPSCI 188 - CS 188 Midterm

Documents in this Course
CSP

CSP

42 pages

Metrics

Metrics

4 pages

HMMs II

HMMs II

19 pages

NLP

NLP

23 pages

Midterm

Midterm

9 pages

Agents

Agents

8 pages

Lecture 4

Lecture 4

53 pages

CSPs

CSPs

16 pages

Midterm

Midterm

6 pages

MDPs

MDPs

20 pages

mdps

mdps

2 pages

Games II

Games II

18 pages

Load more
Download CS 188 Midterm
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view CS 188 Midterm and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view CS 188 Midterm 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?