Code: C–20 / T-21                                                      Subject: ARTIFICAL INTELLIGENCE &

                                                                                                                   NEURAL NETWORKS

Time: 3 Hours                                                                                    June 2006                  Max. Marks: 100

NOTE: There are 9 Questions in all.

· Question 1 is compulsory and carries 20 marks.   Answer to Q.1A must be written in the space provided for it in the answer book supplied and nowhere elese.

· Out of the remaining EIGHT Questions answer any FIVE Questions. Each question carries 16 marks.

· Any required data not explicitly given, may be suitably assumed and stated.

Q.1 A     Choose the correct or best alternative in the following:                                         (2x10)

a. Minimax procedure is a _____________ search

(A)  Depth first search                        

                   (B)  Breadth first search

(C)   Depth First Depth Limited Search

(D) D-search

b. _________ is a Linear Separable Problem.

(A) NOR                                           (B)  NAND

(C)  XOR                                            (D)  OR

c. Boltzmann’s machine is a variation of ______________ network                          

(A) Hopfield Network                       

(B) ART Network

(C) Kohonen Network

(D) SOM

             d.   Analysing words into their components and non words token is called

(A) Syntactic Analysis                       (B) Morphological Analysis

(C)  Semantic Analysis                        (D) Pragmatic Analysis      

             e.   Terminating the exploration of a subtree that offers little possibility for improvement over other known paths is called ___________

(A) Alpha cutoff                                 (B)  Beta cutoff

(C)  Alpha-Beta cutoff                         (D)  Futility cutoff

             f.    _________ represents the kind of knowledge about events that is usually contained in natural languages sentences

(A) Frame                                          (B)  Script

(C)  Semantic Net                               (D)  Conceptual Dependency

Q.1B     State True / False

             g.   Means-Ends Analysis combines both forward and Backward Search.

             h.   Depth First Search requires less memory than Breadth First Search.

             i.    TWEAK is a Linear Planning Technique.

             j.    Modal Truth Criterion does not tell us exactly when a proposition is True.

Answer any FIVE Questions out of EIGHT Questions.

Each question carries 16 marks.

Q.2     a.   What is a Heuristic Technique?  How does it differ from other solution guaranteed techniques?                                                                   (8)

             b.   Solve the cryptarithmetic problem using Constraint Satisfaction.                          (8)

                   CROSS

                   ROADS

                   -------------

                   DANGER

                   --------------                                                                                                        

Q.3     a.   Explain the procedure of MINIMAX Alpha Beta pruning method.  How performance of the above algorithm can be improved?                                (8)

             b.   The backward cost propagation of the AO* algorithm must be guaranteed to terminate even on graphs containing cycles.  How can we guarantee that it does?  To help answer this question, consider what happens for the following two graphs, assuming in each case that node F is expanded next and that its only successor is A:                                                       (8)

Q.4     a.   Construct partitioned semantic net representations for the following:

(i) Every batter hits a ball.

(ii) All the batters like the pitches.                                                    (8)

b.     Consider the following facts:

· The members of the Elm St. Bridge Club are Joe, sally, Bill, and Ellen.

· Joe is married to sally.

· Bill is Ellen’s brother.

· The spouse of every married person in the club is also in the club.

· The last meeting of the club was at Joe’s house.

(i)  Represent these facts in predicate logic.

(ii)  From the facts given above, most people would be able to decide on the truth of the following additional statements:

· The last meeting of the club was at Sally’s House.

· Ellen is not married.

Can you construct resolution proofs to demonstrate the truth of each of these statements given the five facts listed above?  Do so if possible.  Otherwise, add the facts you need and then construct the proofs.  (8)

Q.5     a.   Give difference between Red cut and Green Cut giving two examples. (6)

     b.   Write a PROLOG program to find factorial of a number.                                    (5)

c. Write a PROLOG program to append a List L1 to List L2.                                (5)

  Q.6           Write short notes on

(i) Bayesian net probable reasoning.

(ii) Hopfield Networks.

(iii) Fuzzy Logic.

(iv) Explanation Based Learning.                                        (4 * 4 = 16)

Q.7     a.   Describe the learning process in Neural Network.                                               (8)

b.   Implement the candidate elimination algorithm for version spaces.  Choose a concept space with several features (for example, the space of books, computers, animals, etc.) Pick a concept and demonstrate learning by presenting positive and negative examples of the concept.                  (8)

Q.8     a.   What is an Expert System.  Explain the architecture of Expert system with a neat diagram.              (8)

             b.   Explain the different processes of Knowledge Acquisition.                                  (8)

  Q.9     a.   Differentiate between Linear and Non Linear Planning with example.                   (8)

             b.   Solve the following using Linear Planning                                                            (8)

C

                   C                    B

                   A  B               A

                   ____               _____

                   Initial State      Goal State