Questions from earlier CS638 exams

 

  1. 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]

 

  1. In the following objective questions you need to draw arcs from the sets on the left to the sets on the right.       

Note:  Each correct arc will fetch +1 mark.

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.

 

 

  1. 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

 

 

 

 

 

 

 

SEARCH

 

  1. 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]

 

  1. 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]

 

 

  1. 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]

 

  1. In what way is TWEAK s handling of the above problem different?

                                                                                                                        [Marks 8]

 

  1. 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]

 

  1. What are the conditions needed for algorithm A* to be admissible? Illustrate with an example.                                                                 [Marks 6]

 

  1. Given the (rough) cost matrix below, show how Branch and Bound algorithm would solve the TSP (traveling salesman problem).

 

 

Chennai

Goa

Mumbai

Delhi

Bangalore

Chennai

0

800

1300

2200

400

Goa

800

0

600

2100

500

Mumbai

1300

600

0

1500

1200

Delhi

2200

2100

1500

0

2400

Bangalore

400

500

1200

2400

0

 

                                                                                                            [Marks 15]

 

  1. In what way is recursive best first search an improvement over best first search? At what cost?                                                                                                                                                                                                 [Marks 5]

 

  1. Describe very briefly the algorithms Simulated Annealing and Tabu Search. What is common between the two? What is different?

[Marks 8]

 

  1. In what way is recursive best first search an improvement over best first search? At what cost?                                                                                                                                                                                                 [Marks 5]

 

  1. Describe the RBFS algorithm.  What advantage does it have over the algorithm A* .                                                                                      [Marks 5]

 

  1. 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]

 

  1. Compare the relative advantages and disadvantages of 

a.       Best first search

b.      Hill climbing

c.       Simulated annealing

d.      Tabu search                                                                                 [Marks 12]    

 

  1. What is peak-to-peak heuristic? Where is it used, and how?                                                                                                                                         [Marks 3]
  2. 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]

OR

 

  1. 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]

                                                                                                                                

 

 

 

 

  1. 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]

 

 

 

 

 


  1. 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]


  1. 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]


  1. 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]


GAMES

 

  1. 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.

 

  1.  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.

 

  1. 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]

 

  1. Under what conditions will the Alpha-Beta algorithm yield an inferior solution as compared to the Minimax algorithm?                                                                                                                                                               [Marks 3]
  2. 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]

 

 

  1. Show the initial set of clusters formed by algorithm SSS* for the above game tree.                                                                                                 [Marks 4]

 

  1. 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]

 

  1. 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]

 

 

  1. Under what conditions will the SSS* algorithm yield an inferior solution as compared to the Minimax algorithm?                                                                                                                                                                              [Marks 3]

 

  1. 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]

 

  1. Flip your game tree (reverse the order of leaves), and show the tree as explored by the alpha-beta algorithm.                                           [Marks 10]

 

  1. 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.

 

 

  1. 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]

 

 

 

 

LOGIC

 

  1. 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]

 

 

  1. 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.

 

  1. 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]

 

  1. 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]

 

 

 

  1. 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]

  1. 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]

 

 

  1. 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]

 

  1. 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]

 

 

  1. "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]

 

 

  1. 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.

 

 

RETE NET

 

  1. 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]

 

 

 

  1. 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]

 

  1. 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>) {y not equal to 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>>) {or}

                                    --->

                                                (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))

 

 

  1. 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>>) {or}

                                    --->

                                                (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]

 

 

  1. 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.

 

 

 

 

UNCERTAINITY

 

  1. What is the difference between Evidence and Proof?                [Marks 4]

 

 

  1. 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]

 

  1. 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 <censored>  is the culprit."

 

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]

  1. 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 <censored>  is the one."

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]

 

 

 

 

 

KNOWLEDGE REPRESENTATION and NLP

 

  1. 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.

 

  1.  Calvin killed the cat.  How is this sentence analyzed linguistically, and how is it analyzed at the conceptual level?

 

  1. 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"

 

  1. 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]

 

  1. 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]

 

WALTZ ALGORITHM

 

  1. 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.

 

                                                                                                        

 

 

  1. Is the following line drawing of a trihedral object? Assign appropriate labels to each edge. State any assumptions you might be making.

[Marks 8]