Department of Computer Science
CPS 721: An Introduction to Artificial Intelligence Sample Midterm Test #2
NOT FOR DISTRIBUTION
Copyright By PowCoder代写 加微信 powcoder
(C) COPYRIGHT:
THIS EXAM CANNNOT BE SHARED WITHOUT EXPLICIT PERMISSION
Do not turn this page over until you are asked to do so.
Time: 1 hour and 40min.
Total marks: 20
Keep your Ryerson photo ID card on your desk.
Closed Book: aids are not allowed, all electronic devices must be turned off, use of scrap paper is not allowed. Use a pen with permanent ink only. If you use pencil, you cannot submit a remarking request.
Do not detach the pages of this test. Please print your answers legibly. Good luck!
Last name:
First Name:
Student #:
Section #:
1 (2 points).
Assume that you are given a collection of atomic statements about products available for purchase, manufac- turers and prices, using the following predicates:
inStore(ItemID,ProductType,Quantity) – Quantity of a ProductType (can be a phone, a laptop, a tablet, etc) with an unique ItemID (it can be any unique item identifier) is available in the store,
where Quantity is the number of the copies of a product that are available in the store.
manufacturer(ItemID,Company,Year) – ItemID has been manufactured by Company in Year.
Formulate queries (not rules) in Prolog using these predicates, equality and inequality only.
• How many Dell laptops manufactured in 2017 and in 2018 are actually available in the store? (If a product is sold out, its stock level is 0.) Let all Dell laptops manufactured in the same year have an identical item identifier, but laptops made in different years have distinct identifiers.
• Which printer in the store is the oldest one? In other words, check which printer has the earliest manu- facturing date. There is no need to check whether any printers are actually availabale in stock. (Note that KB can include arbitrary many items.)
2 (3 points). Let the term with three arguments tree(Element,LeftSubtree,RightSubtree)
represent a binary tree and the constant void represent the empty tree. Let the predicate leaves(T,N) be true if N is the number of non-empty leaves in a given binary tree T, where a non-empty leaf is a sub-tree different from void that has only void nodes as chidlren. For example, a query
?- leaves(tree(a, tree(b,tree(d,void,void),void), tree(c,void,void)), X). returns the answer X = 2, but a query ?- leaves(tree(a, void, tree(b,void,void)),3).
must return the answer no (but would return yes, if the last argument would be 1). Write a recursive program that implements this predicate. You can assume that in any query the first argument will be a (possibly empty) tree (input to your program), and the second argument will be either a variable representing the number of non-empty leaves that has to be computed or a number representing the result to be verified.
3 (3 points). For each of the following pairs of lists, state which pairs can be made identical, and which cannot. Write brief proof: it is not acceptable to give an answer without explanations. (You may be penalized if you do not explain properly.) For those pairs that mention variables, and that can be made identical, give the values of their variables that make the two lists the same. Write legibly.
(a) [X, Y, [a, Y]] and [a, b, [W | [W]]].
(b) [X,Y,X|W] and [a,b,T].
4 (5 points). The predicate member(X, List) is true if and only if X is an element that occurs in List. For example, the following queries succeed:
? − member(t, [p, q, r, s, t]). and ? − member(k, [k, l]).
The following queries fail: ? − member(g, [ ]). ? − member(a, [t, j, m]).
You have to write two different recursive programs that implement this predicate and then find whether one of them is more efficient than the other. More specifically, you have to solve the following sub-problems.
A) (1 points) Write a recursive program that implements the predicate member(X, List) without using the predicate append(L1, L2, L3).
B) (1 points) Write a program that uses the predicate append(L1, L2, L3) to implement the predicate member(X, List). You also must write rules that define the predicate append(L1, L2, L3) considered in class.
C) (2 points) For each of these two programs, show the evaluation trees, including backtracking (if any), that corresponds to Prolog’s evaluation for the following query: ? – member(p,[d,f,p,r]).
You have to mention every step of the back-chaining procedure.
D) (1 point) Compare evaluation trees and make conclusions what implementation is more efficient in terms of computation time (e.g., if List has n elements and n is any large number). Give an argument to support your claims. Please write legibly.
This page was intentionally left blank. Use this page for your rough work only. Nothing on this page will be marked.
5 (5 points). Consider the following constraint satisfaction problem:
where each letter stands for a distinct digit and leading digits must not be zeroes. To write a Prolog program that solves this crypt-arithmetic puzzle, you have to do the following:
(1) (0.5 point) show the dependency graph whose nodes are the variables {O, N, E, T, W } (you have to draw a graph whose nodes are the variables, with an edge from var1 to var2 if the value of var1 will be calculated from that of var2);
(2) (4 points) write an efficient Prolog program that uses “interleaving of generate and test” technique; in other words, use your dependency graph to reduce the number of guesses (remember, that you may need carry digits that can be either 0 or 1). In your program, use the predicate all different(List) that holds if all elements in List are different from each other. You have to write a Prolog program that implements this predicate. Note that if you would like to use other predicates in your program, you must implement them as well.
(3) (0.5 point) Write the first solution that will be computed by your program.
6 (1 point). What is the Turing test? Explain briefly. Write no more than 5 sentences. Write legibly.
7 (1 point).
Let the predicate road(X,Y) be true if there is a road from city X to city Y . Let the predicate reachable(X) be true if city X is reachable from an initial location. The predicate initLoc(City) is true if City is indeed an initial location. You are given a small collection of atomic statements about an initial location and roads and a Prolog program that implements the predicate reachable(X):
initLoc(toronto).
road(toronto,edmonton). road(ottawa,montreal). road(montreal,boston). reachable(X) :- initLoc(X).
reachable(Z) :- road(Y,Z), reachable(Y).
Show the evaluation tree, including backtracking, that corresponds to Prolog’s evaluation for the following query: ? − reachable(boston).
You have to mention every step of the back-chaining procedure. Use the symbol x to show branches that fail and dashed lines to show backtracking.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com