- For
each of the following give your estimate of the size of the vocabulary
held -
A. A four year old child. B. An IIT graduate. C. Salman Rushdie. D. An
IIT graduate about to write GRE. [Marks
2] - In
the following objective questions you need to draw arcs from the sets on
the left to the sets on the right.
Each
wrong arc will mean 1 mark. A. For
a computational agent draw arcs to relate the elements in the first column
below with the elements on the right hand side. The relation is x influences z
structure of the agent . Sociology Micro
structure of agent Psychology Macro structure of
agent Philosophy Economics B.
Draw
arcs from left to right to categorize the kind of activities in the two
approaches to intelligent machines Symbol
level Emergent Classical AI Animat
approach Artificial Neural
Networks Reductionist Learning Signal
level C.
Draw
arcs from left to right to relate terms in the following search methods Depth First systematic Breadth First heuristic Best First crossover Branch
& Bound temperature Hill
Climbing population
size A* admissible Simulated
Annealing unsystematic Genetic
Algorithm probabilistic British
Museum procedure D. Relate
each of the chess playing algorithms to the properties listed on the right Random
move Best
move guaranteed Mini-Max Systematic Alfa-Beta Unsystematic SSS* Depth
first E.
Draw
arcs to assert which of the following are related to each other. - Describe
the Turing Test. List
*one*point for and*one*against the statement The Turing Test is a good test for testing whether a machine has intelligence
- A
node-pair is a pair of nodes (node, parent) denoting a node and its parent
as marked during search.
Given a) a goal node-pair (found by some search algorithm) b)
a start node-pair (START NIL) c)
a list CLOSED of node-pairs d)
a function equal(node1, node2) which tests for equality Write
an algorithm to reconstruct the path found from the START node to the goal node. You
may use functions current(node-pair) and parent(node-pair) to
get the first node and the second node of the node pair. [Marks
12] - What
is DFID search? What are its advantages? Illustrate with an example.
What is the extra cost
one has to pay for the advantages? Quantify the extra cost
(how much extra work is done)? [Marks
10] - Consider
the following blocks world problem.
Show how STRIPS would
use goal stack planning to form a plan to transform the start state into goal
state. What is the plan found? [Marks 20] - In
what way is TWEAK s handling of the above problem different?
[Marks
8] - When
does Simulated Annealing perform better than Hill Climbing? How is this
better performance achieved? Would you ever prefer HC to SA? If yes, when?
[Marks
7] - What
are the conditions needed for algorithm A* to be admissible? Illustrate
with an example. [Marks
6]
- Given
the (rough) cost matrix below, show how Branch and Bound algorithm would
solve the TSP (traveling salesman problem).
[Marks
15] - In
what way is recursive best first search an improvement over best first
search? At what cost?
[Marks 5]
- Describe
very briefly the algorithms Simulated Annealing and Tabu Search. What is common
between the two? What is different?
[Marks 8] - In
what way is recursive best first search an improvement over best first
search? At what cost?
[Marks 5]
- Describe
the RBFS algorithm. What advantage
does it have over the algorithm A* . [Marks
5]
- What
is DFID search? What are its advantages? Illustrate with an example.
What
is the extra cost one has to pay for the advantages? Quantify
the extra cost (how much extra work is done)? [Marks
10] - Compare
the relative advantages and disadvantages of
a.
Best
first search b.
Hill
climbing c.
Simulated
annealing d.
Tabu
search [Marks
12] - What
is peak-to-peak heuristic? Where is it used, and how? [Marks
3]
- The
following graph represents a map of a region. You are at point Start and
need to find a route to point Goal. Show how RBFS will explore the graph.
The numbers labeling the nodes are the
*h*values. The numbers labeling the arcs are arc costs.
[Marks
20]
- Number
the nodes in the order in which algorithm A
^{*}explores the graph, marking*f*values at each stage. Clearly mark the parent pointer for each node, the nodes on CLOSED and OPEN, and the path found at the moment when the algorithm terminates.
[Marks
14] - In
the search graph generated by A* shown below, node N is about to be
expanded. Values labeling the nodes are
*g*values, and values labeling the arcs are cost for each arc. The dashed arcs connect to the successors of node N. Show how the graph will look after N has expanded.
[Marks 12] - The
following graph represents a map of a region. You are at point A and need
to find a route to point S. The figures in the brackets are the x-y
coordinates, which can be used for calculating the Manhattan distance between
any two points. The labels on the edges are the actual cost of the
journey, and may include factors not related to distance. Number the nodes
in the order in which algorithm A
^{*}explores the graph, marking f-values at each stage. Clearly mark the parent pointer for each node, the nodes on CLOSED and OPEN, and the path found at the moment when the algorithm terminates.
[Marks 15] - The
following graph represents an AND-OR graph. The terminal nodes are lebeled
SOLVED (depicted by double line) and have zero cost. The arcs represent the cost of
transforming the problem. Values associated with nodes are heuristic
estimates of solving that node. Simulate the exploration of the graph by
AO* algorithm till it terminates. Show how the graph looks at the end of
each cycle. Assume a FUTILITY value of 45. Clearly mark the final solution (by double lined arcs) in
the final graph.
[Marks 12] - Solve
the following AO graph. Show the graph generated by the AO search
procedure after each cycle till the solution is found, clearly marking the
best known paths at each stage. The labels on the nodes represent the
values returned by the heuristic function for
*that*node. Assume the cost of each arc is one unit.
What
is the final cost of the solution found? Is the above algorithm
guaranteed to find the optimal solution for the AO graph problem? Justify your
answer.
[Marks
15]
- Interaction
between agents can be modeled as games. What are the terms used to categorize
different kind of games used for such models. For each term give an
example of two games that are different w.r.t. that term.
- If
you know the strategy that an opponent is employing you can predict all
her moves accurately. Is the preceding statement true or false, in
context of the game of chess? Justify your answer.
- Algorithm
Minimax is searching a four ply binary game tree (16 leaf nodes). The
first leaf node it encounters is evaluated to 20. The other fifteen
leaves, from left to right evaluate to 10, -8, -7, 11, 6, 3, 7, 9, -12,
-15, -17, 18, 21, 17, -6. Max is to play. Who do you think is in a better
position? What move is Max likely to make? Justify your answer.
[Marks 13] - Under
what conditions will the Alpha-Beta algorithm yield an inferior solution
as compared to the Minimax algorithm?
[Marks 3]
- Simulate
the algorithm Alfa-Beta to explore the following game tree, searching from
left to right. Clearly show the alpha and beta values of the nodes and the
alfa cutoffs and the beta cutoffs wherever they take place. Also mark the path the game is likely
to take. What is the minimax value of the game tree? [Marks
12]
- Show
the initial set of clusters formed by algorithm SSS* for the above game
tree. [Marks
4]
- Label
the (sixteen) leaves of a 4-ply binary search tree with values so that the
Alpha-Beta algorithm produces no cutoffs searching from left to right.
What is the minimax value of your game tree?
[Marks
12]
- Show
how the algorithm SSS* explores the following game tree. MAX is to move
(at root). Show the initial
subtree with which SSS* begins exploration, and then number the nodes in the order SSS* visits them. Show the subtree generated by SSS* when
it terminates. What is the minimax value? In your solution mark the move
chosen by MAX.
[Marks
20]
- Under
what conditions will the SSS* algorithm yield an inferior solution as
compared to the Minimax algorithm? [Marks 3]
- Alpha-beta
is searching a four ply binary game tree (16 leaf nodes). The first node
it encounters is 20. Assign values to the other 15 nodes such that no cut
offs occur searching from left to right. [Marks 10]
- Flip
your game tree (reverse the order of leaves), and show the tree as
explored by the alpha-beta algorithm. [Marks
10]
- Let
G be the set of
*all*finite games. We define the game gnew as follows. Player-1 selects a game say game-i from the set G. Player-2 makes the first move in game-i , and they play the game till completion.
Is gnew a finite game? Justify your
answer. - Mark
the initial clusters with {A, B, C } as identified by the SSS* algorithm.
Then show clearly in a step-by-step manner how SSS* refines the clusters
to find the optimal solution, numbering the nodes in the order that they
are refined.
*Note*: Where ever a random choice has to be made, assume that SSS* chooses the leftmost node possible in the figure. What is the value found for the game tree? Mark the game path predicted by SSS* [Marks 12]
- Assign
truth values to the following statements.
A. The Mount Everest is
not in India. B. The tomato is a
vegetable. C. The following
sentence is false. D. The preceding
sentence is true. E. If the Moon is made
of cheese the Earth is round. F. The tomato is a
fruit. G. The butterfly is an
insect. [Marks
5]
- Describe
the various kinds of inferences that one can make using FOL. Given true
premises, which of the inference methods are guaranteed to produce true
conclusions. Explain with examples.
- Express the following
arguments in Propositional Logic. Which of the arguments are valid arguments?
For each of them give a proof if the argument is valid, else give a
counterexample.
A.
If
the earth were spherical, it would cast curved shadows on the moon. It casts
curved shadows on the moon. So it must be spherical. B.
If
he used good bait and the fish weren t smarter than he was, then he didn t go
hungry. But he used good bait and he did go hungry, so the fish must have been
smarter than he was.
[Marks
10] - Give a natural
deduction proof, or a conditional proof for the following
B âŠƒ (C âˆ§ âˆ¼D) (C âˆ§ A) âŠƒ âˆ¼E F âŠƒ (D âˆ¨ E) âˆ´ A âŠƒ (B âŠƒ âˆ¼F) [Marks
10] - What
modifications are required to employ classical FOL (which has
quantifiers), for automatic reasoning using forward chaining?
Express the following in predicate calculus, and make the required modifications, A detective without a sidekick is of no use." [Marks 6] - Find
the most general unifier (MGU) for the following sets of clauses. [Note.
Each part requires an independent answer.]
A. p(a, x,
f(g(y))) V p(z, h(z,w), f(w)) B. p(a, x, f(g(x))) V p(z, h(z,w), f(w)) where
"a" is a constant, and "w,x,y,z" are variables. [Marks 10] - One
of Tinker, Tailor, Soldier, and Spy is the mole. The mole was not present
in the President's dinner party. But Spy was attending the dinner party.
The mole smokes Havana cigars and always wears a green shirt at home. Soldier does not smoke. Tinker was
wearing a pink shirt at home. Anything coloured pink is not green.
Represent the above information in FOL. Convert it into CLAUSE FORM. Prove, using the resolution refutation method, that the statement "Tailor is the mole" is true. [Marks 17] - One
of Tinker, Tailor, Soldier, and Spy is the mole. The mole was not present in
the President's dinner party. But Spy was attending the dinner party. The
mole smokes Havana cigars and always wears a green shirt at home. Soldier does not smoke Havana cigars.
Tinker wears a pink shirt at home. Anything coloured pink is not green.
Represent the above information in FOL. Use the following predicates : Mole(Person), Colour(Object,Colour), WearsAtHome(Person,Object), Attend(Dinner, Person), Smoke(Person, HavanaCigar). Convert it into CLAUSE FORM. Prove, using the resolution refutation method, that the statement "Tailor is the mole" is true. [Marks 17] - "One
of Tinker, Tailor, Soldier, or Spy is the culprit. The culprit stole the
document. Tinker and Soldier did not
steal the document. If Tailor or Spy is the culprit, then the document must be in Paris."
Show,
after encoding the facts in predicate calculus, AND using resolution
refutation, the proof of validity of the following statement, "The
document is in Paris." [Marks
12] - For
a goal formula (i.e. prefixed with show in the implicit quantifier form), the skolemization conventions are
reversed. For example x in (show (inst ?x prism)) is viewed as an
existentially quantified variable. Similarly in (not (inst ?x prism)) x is
treated as existentially quantified. The former is a goal while the latter
formula is an assertion. Inspired by the similarity in their
skolemization, can we replace all goals with such negated assertions. How
will the theorem proving process be affected? Can we build a sound
reasoning system by doing so? Discuss in brief.
- Write
the most appropriate right hand side for the following rule
(p
what-does-this-rule-do (inst ^number
<n>) -(inst ^number <m> < <n>) ---> (assert . . . )) [Marks
3] - Construct
a Rete net for the following set of rules
(p
rule1 (course
^name AI ^teacher good) (student
^works hard ^in DBMS) --> (some
actions...)) (p
rule2 (student
^works sometimes ^in <x>) (course
^name <x> ^teacher poor) (TA
^is helpful) --> (some
actions...)) (p
rule3 (student
^works hard ^in DBMS) (course
^name AI ^teacher terrific) (TA
^is unhelpful ^and bright) --> (some
actions...)) (p
rule4 (TA
^is unhelpful ^and tough) (student
^in PDS ^works never) (student
^in CO ^works hard) --> (some
actions...)) In the Rete net show
where the tokens for the following data will reside. What is the conflict set? 1.
(student ^works hard ^in DBMS) 2.
(student ^in Maths ^works sometimes) 3.
(course ^name AI ^teacher terrific) 4.
(TA ^is unhelpful ^and absent) 5.
(TA ^is helpful ^and bright) 6. (student ^in PDS ^works never) [Marks 20] - Write the conditions for the rules in English,
and construct a Rete net for the following set
of rules
Rule 1: (p fare-infant (inst
^person <x> ^type child) (age
^of <x> ^is < 5) (inst
^person <y> <> <x>) (age
^of <y> ^is >= 5) (traveling
^person <x> ^with <y> ^to <xyz>) ---> (some
Right Hand Side)) Rule 2: (p fare-child (inst
^person <x> ^type child) (age
^of <x> ^is < 12) (age
^of <x> ^is >= 5) (traveling
^person <x> ^to <anywhere>) ---> (some
Right Hand Side)) Rule 3: (p fare-student (inst
^person <x> ^type student) (age
^of <x> ^is < 25) (traveling
^person <x> ^to <<home school>>) ---> (some Right Hand Side)) Rule 4: (p fare-games (inst
^person <x> ^type sportsman) (traveling
^person <x> ^to games) ---> (some
Right Hand Side)) Rule 5: (p fare-arjuna (inst
^person <x> ^type sportsman) (traveling
^person <x> ^to <anywhere>) (awardee
^person <x> ^award Arjuna) ---> (some
Right Hand Side)) - On the opposite page construct
a Rete net for the following set of rules
Rule 1: (p fare-child (inst
^person <x> ^type child) (age
^of <x> ^is < 12) (age
^of <x> ^is >= 5) (traveling
^person <x> ^to <anywhere>) ---> (some
Right Hand Side)) Rule 2: (p fare-student (inst
^person <x> ^type student) (age
^of <x> ^is < 25) (traveling
^person <x> ^to <<home school>>) ---> (some
Right Hand Side)) Rule 3: (p fare-games (inst
^person <x> ^type sportsman) (traveling
^person <x> ^to games) ---> (some
Right Hand Side)) Rule 4: (p fare-arjuna (inst
^person <x> ^type sportsman) (traveling
^person <x> ^to <anywhere>) (awarded
^person <x> ^award Arjuna) ---> (some
Right Hand Side)) Show where the following
tokens reside in the Rete Net. What is the conflict set? A. (inst
^person Sachin ^type sportsman) B.
(awarded
^person Sachin ^award arjuna) C.
(awarded
^person Satyajit ^award bharatRatna) D. (inst
^person Sunil ^type child) E.
(inst
^person Sachin ^type student) F.
(inst
^person Neha ^type student) G.
(age
^of Sachin ^is 26) H. (age
^of Sunil ^is 7) I.
(age
^of Seema ^is 3) J.
(age
^of Neha ^is 20) K.
(traveling
^person Sachin ^to holiday) L.
(traveling
^person Neha ^to school) [Marks
20] - Construct
a Rete net for the following set of rules
Rule
1: (p alsoFather (brother
^of <x> ^is <y>) (son
^of <z> is <x>) ---> (make
(son ^of <z> ^is <y>)) Rule 2: (p defineTau (brother
^of <x> ^is <y>) (son
^of <x> is <z> (age of <x> is
<ageX> (age
of <y> is {<ageY> > <ageX>} /* <y> is older that <x>*/ ---> (make
(tau ^of <z> ^is <y>)) Rule 3: (p younger-Than (age
of <x> is <ageX> (age
of <y> is {<ageY> > <ageX>} ---> (make
(younger ^than <y> ^is <x>)) In the Rete net show
where the tokens for the following data will reside. What is the conflict set? Token 1: (age
^of Ramu ^is 17) Token
2: (age ^of Ramesh is 36) Token
3: (brother ^of Mahesh ^is Ramesh) Token
4: (son ^of Suresh ^is Ramesh) Token
5: (son ^of Mahesh is Ramu) Write a rule to define
transitivity of the younger relation.
- What
is the difference between Evidence and Proof? [Marks 4]
- Sherlock
brooded over the piece of paper he had just received. "It is either
Tinker, or Tailor", he muttered finally, "but my sources are
only 50% reliable". "You could be right", added Pradosh,
"because my investigations reveal, with 0.8 confidence that it is
either Tinker or Soldier or Spy". They all looked at Hercule who,
twirling his moustache, said, "I think that it is either Tailor or
Spy. I am 60% certain of it".
Everybody knew that one of Tinker, Tailor, Soldier and Spy had stolen the document, but none was quite sure who. After a while George, who had been listening intently said, "The evidence collected by you all is inconsistent. However, the best we can do is to conclude that ____ is the culprit." A. Who,
according to you, is the culprit? B.
Is
George's remark of inconsistency justified? C.
What
is your final belief in Sherlock's statement? D. What
is your belief in the statement that Soldier is not the culprit? E.
What
is your belief in the statement that Spy is not the culprit? Give reasons for your
answers. [Marks
15] - Sherlock
brooded over the piece of paper he had just received. "It is either
Tinker, or Tailor", he muttered finally, "but my sources are
only 70% reliable". "You could be right", added Pradosh,
"because my investigations reveal with 0.8 confidence that it is
either Tailor or Spy". They all looked at Hercule who, twirling his
moustache, declared, "Well, someone did tell me it is the Spy, but he
is not very reliable. I would say 50-50 .
Everybody knew that one of
Tinker, Tailor, Soldier, or Spy had stolen the plans, but nobody was quite sure
who it was. Whoever it is it must be Osama, quipped Bush, but nobody was
listening to him. After a while Smiley, who had been listening intently said,
"The evidence collected by you all is inconsistent. However, the best we
can do is to conclude that < F.
Who,
according to you, stole the plans? G.
Is
George's remark of inconsistency justified? H. What
is your final belief in Sherlock's statement? I.
What
is the confidence interval for your answer to part A? Justify all your
answers. (Use answer sheet for
question 12) [Marks 12] - Sherlock
brooded over the piece of paper he had just received.
"It is either Dr.
Bhanu, or Kolathur Mani", he muttered finally, "but my sources are
only 60% reliable". "You could be right", added Pradosh, "because
my investigations reveal with 0.7 confidence that it is either Dr. Bhanu or
Nedumaran or R.R.Gopal". They all looked at Hercule who, twirling his
moustache, declared, "I think that it is either Kolathur Mani or
R.R.Gopal. But I am only 50% certain of it". Everybody knew that one of
Dr. Bhanu, Kolathur Mani, Nedumaran and R.R.Gopal had struck a deal with
Veerappan, but nobody was quite sure who it was. After a while George, who had
been listening intently said, "The evidence collected by you all is inconsistent.
However, the best we can do is to conclude that < J.
Who,
according to you, struck the deal? K.
Is
George's remark of inconsistency justified? L.
What
is your final belief in Sherlock's statement? M. What
is your belief in the statement that Nedumaran is not the one? N. What
is your belief in the statement that R.R.Gopal is not the one? Justify all your
answers. [Marks
16]
- State
one major disadvantage of using verbs, adjectives and adverbs of English
language as predicates while building a FOL reasoning system. Give a brief justification of your
answer.
- Calvin
killed the cat. How is this sentence analyzed linguistically, and how is
it analyzed at the conceptual level?
- Convert
the following story into CD like FOL representation.
"Heidi told her
grandfather that Clara was likely to come to their home. Some time later Clara
came to their home. Heidi was very happy" - Convert
the following story into CD like FOL representation.
"Drona
put down his weapons because he came to believe that his son was dead. This was because Yudhistra
told him that Aswathama was killed by Bhima." [Marks
12] - Convert
the following story into CD like FOL representation. Be careful with Bush
bombing Afghanistan .
"Bush told Blair
that Osama was a bad man and that is why Bush was going to bomb Afghanistan.
This happened after the planes crashed into the WTC buildings" [Marks
10]
- Give
all feasible labels to the three edges meeting at the vertex Y in the
centre of the adjoining figure. State your assumptions clearly. Show one
consistent labeling found by the Waltz algorithm for the entire figure.
- Is
the following line drawing of a trihedral object? Assign appropriate
labels to each edge. State any assumptions you might be making.
[Marks 8] |