JEPPIAARENGINEERINGCOLLEGE

Old Mamallapuram Road,Chennai-119.

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

(VI SEMESTER)

QUESTION BANK

CS1351 - ARTIFICIAL INTELLIGENCE

UNIT IIntroduction8

Intelligent Agents - Agents and environments - Good behavior - The nature of environments - structure of agents - Problem Solving - problem solving agents - example problems - searching for solutions - uniformed search strategies - avoiding repeated states - searching with partial information.

Unit IISEARCHING TECHNIQUES10

Informed search and exploration - Informed search strategies - heuristic function - local search algorithms and optimistic problems - local search in continuous spaces - online search agents and unknown environments - Constraint satisfaction problems (CSP) - Backtracking search and Local search for CSP - Structure of problems - Adversarial Search - Games - Optimal decisions in games - Alpha - Beta Pruning - imperfect real-time decision - games that include an element of chance.

Unit IIIKNOWLEDGE REPRESENTATION10

First order logic - representation revisited - Syntax and semantics for first order logic - Using first order logic - Knowledge engineering in first order logic - Inference in First order logic - prepositional versus first order logic - unification and lifting - forward chaining - backward chaining - Resolution - Knowledge representation -Ontological Engineering - Categories and objects - Actions - Simulation and events - Mental events and mental objects

UNIT IV LEARNING9

Learning from observations - forms of learning - Inductive learning - Learning decision trees - Ensemble learning - Knowledge in learning - Logical formulation of learning - Explanation based learning - Learning using relevant information - Inductive logic programming - Statistical learning methods - Learning with complete data - Learning with hidden variable - EM algorithm - Instance based learning - Neural networks - Reinforcement learning - Passive reinforcement learning - Active reinforcement learning - Generalization in reinforcement learning.

UNIT V APPLICATIONS8

Communication - Communication as action - Formal grammar for a fragment of English - Syntactic analysis - Augmented grammars - Semantic interpretation - Ambiguity and disambiguation - Discourse understanding - Grammar induction - Probabilistic language processing - Probabilistic language models - Information retrieval - Information Extraction - Machine translation.

TOTAL: 45
Text Book

1.Stuart Russell, Peter Norvig, “Artificial Intelligence - A Modern Approach”, 2nd Edition, Pearson Education / Prentice Hall of India, 2004.

ReferenceS

1.Nils J. Nilsson, “Artificial Intelligence: A new Synthesis”, Harcourt Asia Pvt. Ltd., 2000.

2.Elaine Rich and Kevin Knight, “Artificial Intelligence”, 2nd Edition, Tata McGraw-Hill, 2003.

3.George F. Luger, “Artificial Intelligence-Structures And Strategies For Complex Problem Solving”, Pearson Education / PHI, 2002.

PART B QUESTIONS:

IMPORTANT NOTE:

All the answers for the given questions are available in the text book “Artificial Intelligence - A Modern Approach”, by Stuart Russell, Peter Norvig, 2nd Edition, Pearson Education / Prentice Hall of India, 2004.

UNIT I

  1. Explain in detail about the classification of task environments.

(Page No.38)

Specifying the task environment

Properties of task environments

  1. Fully observable vs. partially observable.
  2. Deterministic vs. stochastic
  3. Episodic vs. sequential
  4. Static vs, dynamic
  5. Discrete vs. continuous
  6. Single agent vs. multiagent
  1. Explain about various agent programs in detail. (Page No.44)

Agent programs – Definition

Simple reflex agents

Model-based reflex agents

Goal-based agents

Utility-based agents

Learning agents

Explanation with neat diagrams

  1. Explain in detail about uninformed searching strategies. (Page No.73)

Breadth-first search

  • Uniform-cost search

Depth-first search

  • Depth-limited search
  • Iterative deepening depth-first search
  • Bidirectional search

Comparing uninformed search strategies

  1. Briefly explain about searching with partial information. (Page No.83)

Sensorless problems / conformant problems

Contingency problem

UNIT II

  1. Explain in detail about informed / heuristic searching strategies.

(Page No.94)

Informed search

Best-first search

Greedy best-first search

A* search

Memory-bounded heuristic search

  1. Explain in detail about Local Search Algorithms. (Page No.110)

State space landscape

Hill-climbing search (greedy local search)

Stochastic hill climbing

First-choice hill climbing

Random-restart hill climbing

Simulated annealing search

Local beam search

Genetic algorithms

  1. What are online search agents? Explain in detail about how they are used in searching unknown environments. (Page No.122)

Exploratiorn Problem

Online Search Problems

Competitive Ratio

Simpie Maze Problem

Online Search Agents

Online Local Search

Learning In Online Search

  1. Explain in detail about Constraint Satisfaction Problems.

(Page No.137)

Objective Function.

CSP

Map-Coloring Problem

CSP As Incremental Formulation

Boolean CSP

Constraint Language

Cryptarithmetic Puzzles

  1. Explain how backtracking search is carried out in CSPs. Explain with examples. (Page No.141)

Commutativity

Backtracking Search

Search Tree

Variable And Value Ordering

Propagating Information Through Constraints

Forward Checking

Constraint Propagation

Arc Consistency

Handling Special Constraints

Intelligent Backtracking: Looking Backward

  1. Explain how optimal decision making is done in games?

(Page No.162)

Problem formulation of a game

Optimal strategies

The minimax algorithm

Optimal decisions in multiplayer games

UNIT III

  1. Explain in detail about syntax and semantics used in the first order logic. (Page No. 245)

Models for first-order logic

Symbols and interpretations

Terms

Atomic sentences

Complex sentences

Quantifiers

  1. Universal quantification
  2. Existential quantification
  3. Nested quantifiers

Equality

  1. What are the steps involved in knowledge engineering process. Explain with an example. (Page No. 261)

The knowledge engineering process

The electronic circuits domain

  1. What are unification and lifting in first order logic? (Page No.275)

Generalized Modus Ponens

Unification

Storage and retrieval

  1. Explain briefly about forward chaining with an example.

(Page No. 280)

First-order definite clauses

Simple forward-chaining algorithm

Efficient forward chaining

Incremental forward chaining

  1. Explain briefly about forward chaining with an example.

(Page No. 287)

Composition

Backward Chaining Algorithm

Proof Tree

  1. Explain in detail about resolution in first order logic. (Page No. 295)

Completeness Theorem

Incompleteness Theorem

Conjunctive Normal Form For First-Order Logic

The Resolution Inference Rule

Example Proofs

Completeness Of Resolution

UNIT IV

  1. Explain in detail about Learning Decision Trees. (Page No. 653)

Definition

Decision trees as performance elements

Example

Expressiveness of decision trees

Inducing decision trees from examples

  1. Explain in detail about explanation based learning. (Page No. 690)

Extracting general rules from examples

Improving efficiency

  1. Explain in detail about how logical formulation of learning is carried out? (Page No.678)

Examples and hypotheses

Current-best-hypothesis search

Least-commitment search

  1. Write notes on Inductive Logic Programming with an example.

(Page No.697)

ILP

Example

Top-Down Inductive Learning Methods

Inductive Learning With Inverse Deduction

Making Discoveries With Inductive Logic Programming

  1. Write notes on statistical Learning. (Page No.712)
  2. Explain briefly about learning with complete data under statistical learning methods. (Page No.716)

Maximum-likelihood parameter learning: Discrete models

Bayesian network model

Naive Bayes models

Maximum-likelihood parameter learning: Continuous models

Bayesian parameter learning

Learning Bayes net structures

  1. Explain in detail about learning with hidden variables? (or) Explain about EM algorithm(Page No. 724)

Unsupervised clustering: Learning mixtures of' Gaussians

Learning Bayesian networks with hidden variables

Learning hidden Markov models

The general form of the EM algorithm

Learning Bayes net structures with hidden variables

  1. Briefly explain about instance based learning. (Page No. 733)

Nearest-neighbor models

Kernel models

  1. Write notes on Neural Networks. (Page No. 736)

Neuron

Units in neural networks

Network structures

Single layer feed-forward neural networks / Perceptrons

Multilayer feed-forward neural networks

  1. Write notes on passive reinforcement learning.(Page No. 765)

Direct utility estimation

Adaptive dynamic programming

Temporal difference learning

  1. Write notes on Active reinforcement learning.(Page No. 771)

Exploration

Learning an Action-Value Function

UNIT V

  1. Develop a formal grammar for a fragment of English. (Page No. 795)

Lexicon

Grammar of lexicon

  1. Write notes on Syntactic Analysis. (Page No. 798)

Efficient parsing

  1. Write notes on augmented grammars. (Page No. 806)

Verb subcategorization

Generative capacity of augmented grammars

  1. Write notes on semantic interpretation. (Page No. 810)

The semantics of an English fragment

Time and tense

Quantification

Pragmatic Interpretation

Language generation with DCGs

  1. Write notes on ambiguity and disambiguation. (Page No. 818)
  2. Explain in detail about discourse understanding of a language.

(Page No. 821)

Discourse

Reference Resolution

The Structure Of Coherent Discourse

  1. Write notes on Grammar induction. (Page No. 824)
  2. Explain in detail about probabilistic language models.

(Page No. 834)

Probabilistic context-free grammars

Learning probabilities for PCFGs

Learning rule structure for PCFGs

  1. Write notes on Information Retrieval. (Page No. 840)

Information retrieval

Evaluating IR systems

IR refinements

Presentation of result sets

Implementing IR systems

  1. Write notes on Information Extraction. (Page No. 848)
  2. Write notes on machine translation. (Page No. 850)

Solved University question papers

JEPPIAAR ENGINEERING COLLEGE

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

VI SEMESTER

CS1351 – ARTIFICIAL INTELLIGENCE

Part A

Answer all the Questions. 10*2=20

  1. What is meant by percept sequence?
  2. What are actuators?
  3. What are learning agents?
  4. What do you mean by relaxed problem?
  5. What is meant by effective branching factor?
  6. What is a ridge?
  7. What are propositional attitudes?
  8. What do you mean by reinforcement learning?
  9. Define strings.
  10. Distinguish between terminal and non terminal symbols.

Part B

Answer all the Questions. 5*16=80

  1. a. Explain in detail about problem solving.

(ANS: Page number-59)

(or)

b. Explain various agent program structures in detail.(ANS: Page number-44)

  1. a. Explain about local search algorithms in detail.

(ANS: Page number-111)

(or)

b. Explain in detail about backtracking search.(ANS: Page number-141)

13. a. Explain the syntax and semantics of the first order logic.(ANS: Page number-245)

(or)

b. Explain in detail about backward chaining and forward chaining(ANS: Page number-280)

.

14. a. Explain in detail about instance based learning(ANS: Page number-733)

. (or)

b. Explain the concept of learning decision trees and inductive learning(ANS: Page number-653)

.

15. a. Briefly explain about(ANS: Page number-818)

i. Ambiguity and disambiguation

ii. Discourse understanding. (or)

b. Develop a formal grammar for a fragment of English. (ANS: Page number-715)

JEPPIAARENGINEERINGCOLLEGE

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

VI SEMESTER

CS1351 – ARTIFICIAL INTELLIGENCE

Part A

Answer all the Questions. 10*2=20

  1. Define AI.
  2. What is an agent?
  3. What do you mean by heuristic function?
  4. Define A* search.
  5. What do you mean by belief state?
  6. What is meant by explanation based learning?
  7. Define Knowledge Engineering.
  8. Define verb categorization.
  9. What do you mean by ambiguity?
  10. What are the component steps of communication?

Part B

Answer all the questions.

11.a. Give the Algorithm for BFS and DFS and explain it in detail.(ANS: Page number-75,77)

(Or)

b. Explain the concept of searching with partial information in detail(ANS: Page number-83)

.

12. a. Explain in detail about CSPs(ANS: Page number-137)

(or)

b. Explain in detail about optimal decisions in games(ANS: Page number-162)

13. a. Explain in detail about forward and backward chaining?(ANS: Page number-280)

(or)

b. Explain First order predicate logic in detail(ANS: Page number-240)

.

14. a. Explain in detail about Generalization in reinforcement learning (ANS: Page number-763)

(or)

b. Explain in detail about neural networks(ANS: Page number-736)

.

15. a. Explain in detail about Probabilistic language processing(ANS: Page number-834)

(or)

b. Explain the concepts of Information retrieval and Information Extraction in detail(ANS: Page number-840)

.

T3184

BE/B TECH DEGREE EXAMINATION,APRIL/MAY 2008

Sixth Semester

(Regulation 2004)

Computer Science Engineering

CS 1351 -ARTIFICIAL INTELLIGENCE

(Common to B E (Part Time )Fifth semester regulation 2005)

Time:3 Hours Maximum :100 Marks

Answer All Questions

PART A-(10*2=20 marks)

  1. Define artificial intelligence
  2. What is the use of heuristic functions?
  3. How to improve the effectiveness of a search based problem solving technique?
  4. what is a constraint satisfaction problem?
  5. what is unification algorithm?
  6. how can u represent the resolution of predicate logic?
  7. list out the advantages of non monotonic reasoning?
  8. Differentiate between JTMS and LTMS.
  9. what are frameset and instancxes?
  10. list out important concepts of script?

PART B-(*16=80 marks)

  1. (a) (i) give an example of problem for which breadth first search would work better than depth first search. (ANS: Page number-73)

(ii) Explain algorithm for steepest hill climbing.(ANS: Page number-111)

Or

(b) Explain the following search strategies(ANS: Page number-74)

(i)best first search

(ii) A* search

  1. (a) Explain Min Max procedure (ANS: Page number-165)

Or

(b) Describe alpha beta pruning and give the other modifications to the min max procedure to improve its performance,(ANS: Page number-167)

13. (a) Illustrate the use of predicate logic to represent the knowl;edge with suitable example.(ANS: Page number-240)

Or

(b)consider the following sentences

john likes all kinds of food

apples are food

chicken is food

anything anyone isn’t killed by is food.

Bill eats peanuts and is still alive

Sue eats everything bill eats

(i)translate these sentences into formulas in predicate logic

(ii)prove that johnlikes peanuts using backward chaining

(iii)convert the formulas of a part into clause form

(iv)prove that john likes peanuts using resolution (ANS: Page number-253)

14 With an example explain the logics of nonmonotonic reasoning(ANS: Page number-358)

Or

(b) explain how bayesian statistics provides reasoning under various kinds of uncertainty(ANS: Page number-492)

15(a) (i) construct semantic net representation of the following:

Pomepein (marcus),blacksmith(marcus

Mary gave green flowered vaste to her favourite cousin

(ii)construct partitioned semantic net representations for the following

every batter hit a ball

all the batters like the pitcher(ANS: Page number-810)

or

(b) illustrates the learning from examples by induction with suitable examples.(ANS: Page number-651)

C3156

BE/B TECH DEGREE EXAMINATION,MAY /JUNE 2007

Sixth Semester

(Regulation 2004)

Computer Science Engineering

CS 1351 -ARTIFICIAL INTELLIGENCE

(Common to B E (Part Time )Fifth semester regulation 2005)

Time:3 Hours Maximum :100 Marks

Answer All Questions

PART A-(10*2=20 marks)

  1. Give the PEAS description of an interactive English tutor system
  2. write an informal description for the general structure tree algorithm
  3. what is local minima problem
  4. how does alpha beta pruning technique works?
  5. Name is referential transparency
  6. name the two kinds of synchronous rules that allow deductions
  7. list the steps in explanation based learning
  8. give an example of linearly non seperable function
  9. what are the seven process involved in a communication episode?
  10. what are the characteristics of information retrieval system
  1. a. what are the four basic steps of agent program in any intelligent system(ANS: Page number-44--53)

OR

b.explain how did you convert it into learning agents

breadth first search

uniform cost search

depth first search

depth limited search(ANS: Page number-73--80)

  1. a. i. what are the constraint satisfaction problems?

How can u formulate them as search problems?

  1. Discuss the various issues associated with backtracking search for CSP.how are they addressed? (ANS: Page number-137--141)
  1. explain the functional local search strategies with examples
  1. hill climbing
  2. genetic algorithms
  3. simulated annealing
  4. local beam search(ANS: Page number-110--115)
  1. a. explain the various steps associated with the knowledge engineering process?. discuss them by applying the steps to real world application of your choice(ANS: Page number-260--262)

OR

  1. i. what are the various ontologies involved in situation calculus

ii. How did you solve the following problems in situation calculus

  1. representational frame problems
  2. inferential frame problems(ANS: Page number-320)
  1. a. explain with proper example how EM algorithm can be used for learning with hidden variables.(ANS: Page number-724)

OR

  1. describe how decision trees could be used for inductive learning.explain its effectieveness with a suitable example.(ANS: Page number-653)
  1. a. explain machine translation system with a neat sketch.analyse its learning probabilities(ANS: Page number-850--852)

OR

b. perform bottom up and top down parsing for the input “the wumpus is dead”(ANS: Page number-798--800)

BE/B TECH DEGREE EXAMINATION,MAY /JUNE 2006

Sixth Semester

(Regulation 2004)

Computer Science Engineering

CS 1351 -ARTIFICIAL INTELLIGENCE

(Common to B E (Part Time )Fifth semester regulation 2005)

Time:3 Hours Maximum :100 Marks

Answer All Questions

PART A-(10*2=20 marks)

PART –A

1. Define the terms:agent,agent function.

2. Why problem formulation must follow the goal formulation?

3. What is the use of online search agents in unknown environment?

4. Specify the complexity of expectiminimax.

5. How TELL and ASK are used in first-order-logic?

6. What is ontological engineering?

7. State the reasons why the inductive logic programming is popular.

8. What is active and passive reinforcement learning?

9. What is grammar induction?

10. How machine translation systems are implemented?

PART-B

  1. (a) Discuss on different types of agent program(ANS: Page number-44)

(Or)

(b)Explain the following uniformed search strategies(ANS: Page number-73)

(i)Depth First Search

(ii)Iterative deepening depth –first search

(iii)Bidirectional search

12. (a) (i) Describe A* search and give the proof of optimality of A*.(ANS: Page number-96)

(ii) Give the algorithm for solving constraint satisfaction problems by local

search.(ANS: Page number-137)

(or)

(b)Explain Min-MaxAlgorithm and Alpha –beta pruning.(ANS: Page number-165,167)

13. (a) Illusrate the use of first-order-logic to represent the knowledge.(ANS: Page number-245)

(or)

(b) Explain the forward chaining and backward chaining algorithm with an

example.(ANS: Page number-280--294)

  1. (a) (i) Describe about decision tree learning.(ANS: Page number-653)

(ii)Explain the explanation –based learning(ANS: Page number-690)

(or)

(b)Discuss on learning with hidden variables.(ANS: Page number-724)

  1. (a) (i)Describe the process involved in communication using the example sentence “The wumpus is dead”.(ANS: Page number-792)

(ii)Write short notes on semantic interpretation.(ANS: Page number-810)

(or)

(b)Explain briefly about the following:(ANS: Page number-840-849)

(i)Information retrieval.

(ii) Information extraction.

B.E/B.TECH DEGREE EXAMINATION, MAY/JUNE 2009

Sixth semester (Regulation 2004)

Computer science and engineering

CS 1351 – ARTIFICIAL INTELLIGENCE

(Common to B.E (part –time) fifth semester regulation 2005)

Time: three hours maximum: 100 marks

Answer ALL questions PART A- (10 x 2 = 20 marks)