Code: C–20 / T-21 Subject: ARTIFICAL INTELLIGENCE &
NEURAL NETWORKS
Time: 3 Hours Max. Marks: 100
NOTE: There are 11 Questions in all.
· Question 1 is compulsory and carries 16 marks.
· Answer any THREE Questions each from Part I and Part II. Each of these questions carries 14 marks.
· Any required data not explicitly given, may be suitably assumed and stated.
Q.1 Answer ANY FOUR of the following: (4x4)
a. When do we call a heuristic function to be monotonic? Can we guarantee an optimal solution, if A* search algorithm uses monotonic heuristic function?
b. Represent ‘Bob shot Bill with gun and he died’ in CD formalism.
c. Represent “Most people of south have black hair” using fuzzy logic.
d. If it is given that in the future it will be the case that P was true in the past, then can we infer that P is true now? Justify your example.
e. Give an example of non monotonic reasoning you have experienced at some time. How is it implemented?
f. Explain Inductive learning and why we still use it even though it is not a ‘valid’ form of learning.
g. Differentiate between Frame based and semantic net representations.
h. What type of Neural Network be used for learning linearly separable functions? Give an example of linearly separable function.
PART I
Answer any THREE Questions. Each question carries 14 marks.
Q.2 a. Consider a sliding block puzzle with the initial configuration as given below:
|
B |
B |
B |
W |
W |
W |
E |
Where B – Black tile, W – White tile and E- Empty cell. The goal of the puzzle is to have all the white tiles to left of all the black tiles with empty cell at the extreme.
|
W |
W |
W |
B |
B |
B |
E |
The puzzle has the following move:
“A tile can move to an adjacent empty cell with unit cost or may hop over one tile into empty cell with cost equal to 2”
(i) Specify one heuristic function.
(ii) Draw one possible path for solution and find the total cost of suggested path. (2, 8)
b. Under what conditions an algorithm A* gives optimal solution? Give justification in support of your answer. (4)
Q.3 Answer the following:
(i)
Differentiate two situations in A* algorithm for graph/tree, one when
SUCC 
open
list and other when SUCC closed list.
(ii) Name two applications where forward chaining is used.
(iii) What is the difference between A* search and AO* search algorithms?
(iv) Explain branch & bound technique. (4, 2, 4, 4)
Q.4 a. Consider the following piece of knowledge:
- Tony is a member of Alpine club.
- Every Alpine club member who is not a skier is a mountain climber.
- Mountain climbers do not like rains.
- Anyone who does not like snow is not a skier.
Represent this knowledge as a set of predicate statements. Show how such a system would answer the query ‘Does Tony likes snow?’ by using resolution by refutation method. (4+4)
b. What do you mean by that a formula F is variant of
another formula G? Show that 
and 
are variant of each other. (2,
4)
Q.5 a. Consider a two player game where initially there are five sticks in a pile. Two players remove alternatively one, two or three sticks from a pile. The player who picks up the last stick loses.
(i) Show by drawing the game tree, that the player who has second move can always win.
(ii) Give simple characterization of the winning strategy? (3, 3)
b. Consider the following game tree in which the static scores are shown along the leaf nodes from the first player’s (Maximizing) point of view.
(i) What move should the first player choose?
(ii) What nodes would need to be examined using alpha-beta pruning algorithm assuming that nodes are examined from left to right order? (3, 5)
A Maximizing
 |
 |
B C D
Minimizing
E F G H I J K
 |
 |
 |
 |
L M N O P Q R S T U V W X Y
5 3 8 6 17 6 0 1 5 12 9 4 10 12
Q.6 a. Transform the following FOL formula into its equivalent Prenex form and then to standard (skolemised) form.
a : (" x) { (~ P(x) ® R(a)) L ($ z) ~ Q (z, a) } L{(" x) {P(x) ® ($ y) Q(x, y)} (8)
b. The Enterprise is a space_ship that was at 15N2E at 12 noon on Feb. 16, 1994 and its colour is grey and its captain is Kirk.
- Represent above information using 5 predicates namely location, time,
date, colour and captain, each having two arguments.
- Draw a semantic net for the above piece of knowledge. (3, 3)
PART II
Answer any THREE Questions. Each question carries 14 marks.
Q.7 a. Given the following program
person (X) :- woman(X).
man(ram).
man(das).
woman(rina).
woman(seema).
What will be the output of the query ?person(X) in each of the following cases?
(i) If a rule person(X) :- man(X). is added in the beginning of above program.
(ii) If a rule person(X) :- man(X),!. is added in the beginning of above
program.
(iii)If a rule person(X) :-!, man(X). is added in the beginning of above
program.
(iv)If a rule person(X) :- man(X),fail. is added in the beginning of above
program. (8)
b. Write iterative and recursive prolog programs to find the sum of a list. Assume that list contains integer elements. (3 + 3)
Q.8 a. Write a recursive program in prolog named ‘no_double (L, N)’, where N is list obtained after removing all duplicates from L. Draw search tree for the query?-no_double([1, 2, 2], N). (5+5)
b. Consider the following rules with probabilities as arguments.
a(P) :- b (P1), P = P1 * 0.6.
a(P) :- c (P).
Suppose ‘b’ is known to be absolutely certain and ‘c’ is 80% certain. What is the cumulative probability of ‘a’ using the independence assumption? (4)
Q.9 a. Briefly compare rule-based and frame-based knowledge representation schemes. For which type of problem solving situation would you prefer a frame based structure. (6)
b. List two advantages of ‘cut’ in Prolog. (2)
c. Write DCG grammar to produce the logical form of the type X(Y) for the sentences like ‘ram is man – man(ram)’, ‘crow is black – black(crow)’, ‘john is doctor – doctor(john)’ etc. (6)
Q.10 Monkey and Bananas problem:
“Monkey is in a room with some bananas hanging on ceiling out of his reach. A box is available. The monkey has height low but if he climbs onto box, then he will have the same height as that of the bananas”. Initially the monkey is at arbitrary positions, say A, the bananas at B and the box at C. Actions available to monkey are: GO (from one place to another); PUSH(push an object); CLIMBUP(climb onto a box)” CLIMBDN(climb down from the box), GRASP and UNGRASP an object. Grasping results in holding the object if the monkey and object are in the same place at the same height.”
(i) Write down the initial state description.
(ii) Write down STRIPS Style definitions of the six actions.
(iii) Give the plan of sequence of operations. (2, 6, 6)
Q.11 a. Suppose you want to use back propagation Neural Network for machine translation purpose. The training of NN is done on various types of examples consisting of (s1, t1) pair, where ‘s1’ is source language sentence and ‘t1’ is its corresponding target language sentence. Is it possible? If so, suggest how it could be done. (7)
b. Consider degree of education at ‘elementary school’, ‘high school’, ‘college’, ‘Ph.D.’ levels. Assume linguistic variable level_of_education’ = {not_highly_educated, somewhat_educated, highly_educated}. Generate fuzzy sets intuitively for values of linguistic variables and show the corresponding graphs. (7)