c++代写_高级数据结构和算法代写

Final Exam

120 minutes – Open book and notes

CSci4511 Is there a statement that represents well the English sentence? Ifyes, specify which one it is. If no, please write the correct

---

15 points  CSci4511

You are given the following English sentence: “Anyone who owns a

pool owns a house” and these translations into predicate calculus:

(a)∀x∀y∀z  [[P ool(y) ∧ Owns(x, y) ∧ Owns(x, z)] → House(z)]

(b)∃x∃y∃z  [P ool(y) ∧ House(z) ∧ Owns(x, y) ∧ Owns(x, z)]

(c)∀x∀y [[P ool(y) ∧ Owns(x, y)] → [∃zHouse(z) ∧ Owns(x, z)]]

(a) Is there a statement that represents well the English sentence? If

yes, specify which one it is. If no, please write the correct logical

sentence.

(b) For each of the logical sentences above write in English what the

logical sentence is actually saying.

1 10 points Write the following sentences in predicate calculus using

predicates such as Student(x), Building(x), Room(x), V isited(x, y) and

convert them to CNF:

(a) Every student has been in at least one room of every building on

campus.

(b) There is a student who has been in every room of at least one

building on campus.

2 15 points  CSci4511

Express each of the following statements in fifirst-order logic and convert

to CNF, skolemizing as needed.

(a) All computer science majors own a Mac or a PC.

(b) Everyone who owns a Mac owns an IPOD.

(c) All except one student in Stats 101 are Math majors.

(d) IPOD owners love music.

(e) John is a CS major who does not like music.

Prove by resolution with refutation that “John owns a PC”

3 15 points  CSci4511

Prove by resolution with refutation that the following set of expres

sions in CNF is unsatisfifiable. Assume that upper case arguments are

constant, lower case arguments are variable:

(a)¬Bar(x) ∨ ¬Zip(x)

(b)¬Bar(w) ∨ ¬F oo(w, y) ∨ Bar(y)

(c)F oo(A, B)

(d)F oo(A, C)

(e)Bar(A)

(f)Zip(C)

4 20 points

You are given the following action schema to transfer object o from

location x to location y:

Action (T ransfer(o, x, y),

Precond: At(Robot, x) ∧ At(o, x)

Effect: ¬At(Robot, x) ∧ ¬At(o, x) ∧ At(Robot, y) ∧ At(o, y)

(a) Create new action schemas by decomposing the action schema

given into three schemas, one to grasp the object, one to move it

to the destination, and one to drop it at the destination.

(b) Describe in general how action schemas can be created by split

ting existing schemas. Explain when this would be a good idea

and when it would not.

5 25 points

Answer these questions explaining your reasoning brieflfly but precisely.

(a) Can you construct a graph in which A* (with an admissible

heuristics) will expand more nodes than uniform cost? if yes,

show an example, if not, explain why not.

(b) Does iterative deepening depth-fifirst search use less memory than

breadth-fifirst search? Why (or why not)?

6(c) How does the number of variables and the size of the domain af

fect the complexity of solving a CSP problem using backtracking

search?

(d) Explain why dropping negative effffects from every action schema

results in a relaxed problem.

7 Extra Credit 10 points

Suppose you decide to use simulated annealing but you do not want

to reduce the initial temperature. How will the algorithm behave? Be

precise.

商科代写 cs代写 法律学代写 经济学代考_经济学作业代写 艺术代写 心理学代写  哲学代写 伦理学代写 体育学代写 化学代写 教育学代写 医学代写 历史代写 地理学代写