2011 Set4

1. a) Are there agent functions that cannot be implemented by any agent program?
   b) For mathematician’s theorem proving assistant and internet book shopping agent
      develop a PEAS description of task environment. [8+8]
2. a) Explain in detail about A* search technique.
   b) What are the advantages of heuristic search? In what kind of a problem space would
        a depth first search be better than a breadth first one? [8+8]
3. a) Describe in detail about hill climbing algorithm.
    b) Write a detailed note on genetical algorithms. [8+8]
4. a) Define Pruning? Explain alpha beta pruning in detail.
    b) Discuss how well the standard approach to game playing would apply to games such
        as tennis, pool and croquet which take place in a continuous physical state space. [8+8]
5. a) Define semantics for propositional logic and construct a knowledge base for pits for
        Wumpus world problem.
b) Explain in detail about truth-table enumeration algorithm for deciding propositional
   entailment. [8+8]
6. a) Represent the following sentences in first-order logic using a consistent vocabulary
       (which you must define)
       i) Some students took French in spring 2009.
      ii) Every student who takes French passes it.
     iii) Only one student took Greek in spring 2009.
    iv) The best score in Greek is always higher than the best score in French.
 b) What is atomic sentence and complex sentences? Explain about Quantifiers in detail
    with examples. [8+8]
7. a) Describe about heuristics for state space search.
    b) Describe about language of planning problems in detail. [8+8]
8. a) Explain in detail about induction learning.
    b) Explain in detail about EM algorithm. [8+8]

2011 Set3

1. a) Consider the n-queens problem using the efficient incremental formulation.
Explain why the state space size is at least !
and estimate the largest n for
which exhaustive exploration is feasible.(Hint: Derive a lower bound on the
branching factor by considering maximum number of squares that a queen can
attach in any column)
b) Discuss in detail about the foundation of AI and also discuss about history of AI
intelligent agents. [8+8]
2. a) Describe a state space in which iterative deepening search performs much worse
than depth first search.
b) Compare iterative deepening A* algorithm and standard iterative deepening algorithm.
[8+8]
3. a) Describe in detail about local search algorithms.
b) Elucidate in detail about local beam search and discuss about local search for
constraint satisfaction problems. [8+8]
4. a) Explain minimax algorithm that computes minimax decision from current state.
What is space complexity?
b) Explain about the significance of applying a heuristic evaluation function to states
in the search. [8+8]
5. a) Analyze Wumpus-world reasoning by knowledge base entailment by taking an
example.
b) Show that PL-RESOLUTION function is complete. [8+8]
6. a) Using first-order logic write down the following
i) One’s mother is one’s female parent
ii) A grand parent is a parent of one’s parent.
iii) A sibling is another child of one’s parent.
b) Resolution can produce non-constructive proofs for queries with variables, so we
had to introduce special mechanisms to extract definite answers. Explain why this
issue does not arise with knowledge bases containing only definite clauses. [8+8]
7. a) Explain about planning with state space search in detail.
b) Write a detailed note on partial order planning graphs. [8+8]
8. a) Describe in detail about instance based learning.
b) What is learning? Discuss about different forms of learning. [8+8]

2011 Set2

1. a) Give examples of agent types and their PEAS descriptions.
b) Both the performance measure and utility function measure how well an agent
doing. Explain the difference between the two. [8+8]
2. a) Explain the idea behind bidirectional search.
b) Discuss optimal strategies in a normal search problem. Also explain a partial search
tree for tic-tac- toe game. [8+8]
3. a) Explain in detail about local search for constraint satisfaction problem.
b) Delineate about local search algorithms. [8+8]
4. a) Search in game playing programs always proceed forward from current state to
goal state. Why? Explain.
b) Define cutoff test. Discuss in detail about cutting off search with an example. [8+8]
5. a) Compare forward Vs backward reasoning. Give simple knowledge base of Horn
clauses and also its corresponding AND-OR graph representations.
b) Given the following, Can you prove that the unicorn is mythical? How about
magical? Horned?
If the unicorn is mythical, then it is immortal mammal. If the unicorn is either
immortal or a mammal then it is horned. The unicorn is magical if it is horned. [8+8]
6. a) Write axioms describing the predicates GrandChild, GreatGrandparent, Brother,
Sister, Daughter, Son, Aunt, Uncle, BrotherInLaw, SisterInLaw and FirstCousin.
Find out proper definition of mth cousin n times removed, and write the definition
in first order logic.
b) Discuss skolemization process. [8+8]
7. a) Give a detailed note on partial order planning graphs.
b) Discuss in detail about backward state space search. [8+8]
8. a) Discuss different statistical learning methods in detail.
b) Explain about learning with decision tree. [8+8]

2011 Set1

1. a) Explain in detail about task environments. Also discuss different flavors of task
environments.
b) Given an architecture with n bits of storage, how many different possible agent
programs are there? [8+8]
2. a) Does a finite state space always lead to a finite search tree? How about a finite state
space that is a true? Can you be more precise about what types of stack space always
lead to finite search trees?
b) Discuss in detail about memory bounded heuristic search strategy algorithms. [8+8]
3. a)Describe in detail about backtracking search for CSP’s.
b) Explain in detail about simulated annealing search. [8+8]
4. a) Implement move generators and evaluation functions for chess game. Construct a
general alpha beta game playing agent that uses your implementation. Compare the
effect of increasing search depth, improving move ordering and improving the
evaluation function. How close does your effective branching factor come to the
ideal case of perfect move ordering?
b) Discuss optimal strategies in a normal search problem. Also explain a partial search
tree for tic-tac- toe game. [8+8]
5. a) Discuss in detail about logical equivalence by taking arbitrary sentences , , of
propositional logic.
b) Give a generic knowledge –based agent in detail. [8+8]
6. a) Represent the following sentences in first-order logic using a consistent vocabulary
(which you must define)
i) There is a barber who shaves all men in town who don’t shave themselves.
ii) A person born in UK each of whose parents is a UK citizen or a UK resident
is a UK citizen by birth.
iii) A person born outside the UK, one of whose parents is a UK citizen by birth,
is a UK citizen by descent.
iv) Politicians can fool some of people all of the time, and they can fool all of the
people some of the time, but they can’t fool all of the people all of the time.
b) Prove from first principles that universal instantiation is sound and that existential
instantiation produces an inferentially equivalent known base. [8+8]
7. a) What is meant by planning? Discuss about classical planning problem in detail.
b) Discuss in detail about expressiveness and extension in detail. [8+8]
8. a) Explain about learning with hidden variables.
b) Discuss about learning with complex data and with hidden variables. [8+8]

AI November 2010 Set4

IV B.Tech I Semester Regular Examinations, November 2010
ARTIFICIAL INTELLIGENCE
( ECC )
Time: 3 hours Max Marks: 80
Answer any FIVE Questions
All Questions carry equal marks
? ? ? ? ?
1. (a) Write about problem formulation and goal formulation.
(b) Explain 8-queens problem. [8+8]
2. (a) Define a heuristic function and explain the linear combination with an exam-
ple.
(b) Explain the hill climbing, local maximum and plateau with diagram. [8+8]
3. (a) Explain difference between simple hill climbing and steepest ascent hill climb-
ing.
(b) Explain difference between best first search and steepest ascent hill climbing.
[8+8]
4. In a chess game assume the average branching factor is 35, and the number of
moves made by each player to win or failure is 50. Estimate size of game tree, with
diagram. What is your conclusion from above game? [16]
5. (a) What do you mean by monotonicity? Are propositional and first-order logic
monotonic?
(b) Is the sentence ”Either 2+2=4 and it is raining, or 2+2=4 and it is not raining”
making a claim about arithmetic, weather, or neither? Explain.
(c) Look at the following sentences and decide for each if it is valid, unsatisfiable,
or neither using equivalence rules.
i. ((smoke ^ heat) ! fire) , ((smoke
ii. (big V dumb) V (big ! dumb). [6+6+4]
6. Consider the following sentences:
• John likes all kinds of food
• Apples are food
• Chicken is food
• Anything anyone eats and isn’t killed by is food
• Bill eats peanuts and is still alive
• Sue eats everything Bill eats
(a) Translate these sentences into formulas in predicate logic
(b) Convert the formulas into clause form
(c) Use resolution to answer the question, ”What food does Sue. [6+4+6]
Please purchase PDF Split-Merge on www.verypdf.com1 toof r2emove this watermark.
Code No: M1924/R07 Set No. 4
7. (a) What are the limitations of the problem solving approach and what is the
motivation behind the design of planning systems
(b) What do you mean by state space search?
(c) What do you mean by regression planning? [6+6+4]
8. (a) Explain the major issues that affect the design of the learning element.
(b) Explain various forms of learning [8+8]

AI November 2010 Set3

IV B.Tech I Semester Regular Examinations, November 2010
ARTIFICIAL INTELLIGENCE
( ECC )
Time: 3 hours Max Marks: 80
Answer any FIVE Questions
All Questions carry equal marks
? ? ? ? ?
1. In the history of AI? Explain the following:
(a) Knowledge base systems are key to power
(b) AI becomes science. [16]
2. What is a greedy best first search? Explain with example and diagram. [16]
3. (a) “Hill climbing behaviour is a straight line but best-first search keeps tracks of
all lines”. Justify above statement with an example.
(b) Write about local maximum and global maximum in hill climbing. [12+4]
4. (a) Is exhaustive search for games such as chess is possible? Explain with your
own measures.
(b) Explain secondary research. [8+8]
5. (a) Describe a generic knowledge based agent.
(b) What are the problems with propositional logic?
(c) How can a knowledge-based agent be made fully autonomous. [6+6+4]
6. (a) Explain the backward chaining algorithm.
(b) Explain inference procedure using resolution with refutation.
(c) For each of the following pairs of atomic sentences, give the most general
unifier if it exists.
(a) f(x) and f(g(y))
(b) f(Marcus,g(x,y)) and f(x,g(Caeser,Marcus)) [8+4+4]
7. (a) Write on language of planning problems
(b) Explain classical planning problem. [8+8]
8. (a) Give the general model of learning agents
(b) Explain inductive learning. [8+8]

AI November 2010 Set2

IV B.Tech I Semester Regular Examinations, November 2010
ARTIFICIAL INTELLIGENCE
( ECC )
Time: 3 hours Max Marks: 80
Answer any FIVE Questions
All Questions carry equal marks
? ? ? ? ?
1. Explain 8-Puzzle problem and 8-queens problems. [8+8]
2. What is a simulated annealing search? Explain with algorithm and example. [16]
3. Explain the local search for constraint satisfaction problem with an algorithm and
diagram. [16]
4. For a chess game, assume the average branching factor in 35 and the number of
moves made by each player to win or loss is 50 is exhausted search is possible?[16]
5. (a) Explain in detail a knowledge-based agent.
(b) Discuss on complexity of propositional inference. [8+8]
6. Consider the following sentences
i. Jack owns a dog
ii. Every dog owner is an animal lover
iii. No animal lover kills an animal
iv. Either Jack or curiosity killed the cat, who is named tuna
(a) Express the original sentences in first-order logic
(b) Convert each sentence to implicative normal form
(c) State whether curiosity killed the cat using resolution with refutation. [5+5+6]
7. (a) Explain planning with state space search
(b) Explain with example heuristic state space search. [8+8]
8. (a) Explain the major issues that affect the design of the learning element.
(b) Explain various forms of learning [8+8]