Code: AC20/AT21                                                    Subject: ARTIFICIAL INTELLIGENCE &

                                                                                                                   NEURAL NETWORKS

Time: 3 Hours                                                                                                     Max. Marks: 100

NOTE: There are 9 Questions in all.

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

· 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. Graceful degradation of admissibility means

(A)  If h’ > h occasionally, then your solution will rarely cost more than h’-h plus its optimal cost.   

                    (B)  If h’ < h occasionally, then your solution will rarely cost more than h’-h plus its optimal cost.

(C) If the maximum value of h’ in the tree is rarely much more than h, then the solution will rarely cost more than h’.                                       

(D)  If h’ > h occasionally, then the solution will degrade gracefully.

b. Depth first iterative deepening requires _____________ time as compared to depth-first search and gives ____________ solution.

(A) More, a sub-optimal                     (B)  More, an optimal

(C)  Same, an optimal                          (D)  Same, a sub-optimal

c. An Expert System shell is a

(A) Skeletal system                            

(B)  Domain specific shell

(C)  Programming language                 

(D)  Knowledge representation technique

             d.   The means-ends analysis strategy is

(A)  Searching at different levels of abstraction to reduce details    

(B)  Subgoaling on preconditions of operator that reduce differences

(C)  Depth first searches from the goal node and the root node.     

(D)  Breadth first searches from the goal node and the root node.

             e.   In the alpha-beta minimax search, beta is __________ on the values that a  ___________ node may be ultimately assigned.

(A) a lower bound, maximizing            (B) an upper bound, minimizing

(C)  a lower bound, minimizing             (D) an upper bound, maximizing

Q.1 B.         State True or False

             f.    Operationalization is the process in which a program produces formal descriptions from informal ones

(A) True                                              (B)  False

             g.   Heuristic does not improve the efficiency of the search technique.

(A) True                                             (B)  False

             h.   The removal of cut without affecting the procedural correctness of the procedure is called Red Cut.

(A) True                                             (B)  False

             i.    In a monotonic production system the application of a rule prevents the latter application of another rule.

(A)  True                                             (B)  False

             j.    Fuzzy set does not uses set membership.

(A)  True                                             (B)  False

Answer any FIVE Questions out of EIGHT Questions.

Each question carries 16 marks.

Q.2     a.   Describe how Branch and Bound technique can be used to find shortest solution to water jug problem?                                                                 (8)

             b.   Solve the crypt arithmetic problem using constraint satisfaction.                           (8)

DONALD

                      +GERALD

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

                        ROBERT

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

Q.3     a.   “Best first Search algorithm is not adequate for searching AND-OR graphs” – Discuss with an example.                                                                (8)

             b.   How does Iterative Deepening improve the performance of A* search algorithm.                (8)

Q.4     a.   Use resolution to find whether Deepak will pass in Data Structures course, given the following facts           

Data Structures is a compulsory course for all the students in this class. Deepak is a student of this class. No one fails in a subject which one likes. Deepak likes science courses. Data Structures is a Science course.                                                           (8)

b.   Define the fuzzy sets that are used to represent the list of propositions.

(i) John is tall.

(ii) Mary is slightly ill.

(iii) Sue and Linda are close friends.

(iv) Most Frenchmen are not very tall.                                                             (8)

Q.5     a.   Write a PROLOG program to reverse a list.                                                     (10)

             b.   Consider the following Prolog database

                                    a(X) :- b(X).

                                    b(X) :-c(X),d(X).

d(X) :- e, f(X).

                                    c(X) :- g(X).

                                    g(2).

f(5).

                                    g(5).

                                    e.

                   List all new facts which can be proved using forward chaining.                            (6)

  Q.6           What is an Expert System? Explain the role of knowledge in design of Expert System. Explain the architecture of an Expert System.         (16)

Q.7     a.   Construct partitioned Semantic Net representation for the knowledge

(i) Every batter hits a ball.

(ii) All the batters like the pitcher.   (6)

b.   Explanation based learning is a method for generation of general rules from observations. Describe a technique with examples which can be used for this purpose.                                              (10)

Q.8     a.   Differentiate the three levels of analysis viz syntax, semantics and pragmatics in Natural Language processing using examples.                                    (8)

b.   What are the components of a planning system? Explain briefly how these components can be implemented.                                                                                                                         (8)

Q.9           Write short notes on

(i) Multilayer Feed forward Networks

(ii) Applications of AI.

(iii) Version spaces.

(iv) Context free grammars.                                                                    (4  4)