IT-504-A Artificial Intelligence - Nov 2022 Question Paper

Under each question, How to answer lists the points an answer should cover, outlined by CampusPrep from the syllabus. Check the details against your textbook.

1. 7 Marks
   aCompare the Depth first Search and Breadth first search.
   How to answer

   • Define DFS (LIFO/stack, goes deep) and BFS (FIFO/queue, level by level).
   • Compare on data structure, memory, completeness, optimality, time/space complexity.
   • Compare with table and example tree/graph traversal order.
   • State use-cases: DFS for deep/search with limited memory, BFS for shortest path in unweighted graph.
2. 7 Marks
   bGiven an initial state of 8-puzzle problem and final state to be reached. Initial State: | 1 | 2 | 3 | ; | | 4 | 6 | ; | 7 | 5 | 8 | Final State: | 1 | 2 | 3 | ; | 4 | 5 | 6 | ; | 7 | 8 | | Find the most cost-effective path to reach the final state from initial state using $A^*$ Algorithm. Consider $g(n) =$ Depth of node and $h(n) =$ Number of misplaced tiles.

   

   How to answer

   • Define initial and goal states and $f(n)=g(n)+h(n)$ with $g$=depth, $h$=misplaced tiles.
   • Expand nodes level by level computing $g$, $h$, $f$.
   • Select minimum $f$ node, show open/closed progression to goal.
   • Give optimal path and total cost.
3. 7 Marks
   aWhat is Production rule? Explain the characteristics of production rules.
   How to answer

   • Define production rule as condition-action / IF-THEN with knowledge base, control.
   • Explain characteristics: expressiveness, modularity, commutativity, decomposability.
   • Give example format of production rule.
4. 7 Marks
   bA water jug problem state that "You are given two jugs, a 4-gallon one and a 3-gallon one, a pump which has unlimited water which you can use to fill the jug, and the ground on which water may be poured. Neither jug has any measuring markings on it. How can you get exactly 2 gallons of water in the 4-gallon jug?"

   1. i)Write the Production rule for the problem.
   2. ii)Write any one solution to the above problem.
   How to answer

   • Formulate state as $(x,y)$ for 4-gallon and 3-gallon jugs with operators.
   • List production rules: fill, empty, pour between jugs.
   • Give step-by-step sequence to get exactly 2 gallons in 4-gallon jug.
5. 7 Marks
   aExplain the different problems present in Hill climbing algorithm.
   How to answer

   • Define hill climbing as local greedy search.
   • Explain plateau, local maxima, ridges, shoulders.
   • Explain problems: getting stuck, no backtracking, evaluation issues.
6. 7 Marks
   bIn above the mention problem "mouse is very patient even when it's hungry, so it wants to find an optimal way to reach the cheese kept on the other end of the maze, there are some walls in between, which make the mice's job a bit tricky. Find an optimal way for the mouse so that it reaches the cheese optimally. (Hint: Manhattan distance as heuristics)

   

   How to answer

   • Model maze grid with walls, start (mouse) and goal (cheese).
   • Use Manhattan distance $h=|x-x_g|+|y-y_g|$ as heuristic with $f=g+h$.
   • Expand A* stepwise avoiding walls to get optimal path.
   • Show final optimal route length.
7. 7 Marks
   aWhat are properties of good system for knowledge representation? Explain in various knowledge representation techniques in brief.
   How to answer

   • List properties: representational adequacy, inferential adequacy, efficiency, acquisitional efficiency.
   • Briefly explain semantic nets, frames, logic, scripts, production rules.
   • Compare suitability with example.
8. 7 Marks
   bConvert the following fact into the Predicate logic

   1. i)Everybody loves Ram.
   2. ii)Everybody loves somebody.
   3. iii)There is somebody whom everybody loves.
   4. iv)There is somebody who Ram doesn't love.
   5. v)There is somebody whom no one loves.
   How to answer

   • Use quantifiers $\forall$, $\exists$ and predicate $Loves(x,y)$.
   • Write formulas for each of the five statements distinguishing scope.
   • Explain order of quantifiers for (ii) vs (iii).
9. 7 Marks
   aConsider Two Fuzzy sets $A = 1/x_1 + 0.3/x_2 + 0.5/x_3 + 0.2/x_4$ $B = 0.5/x_1 + 0.4/x_2 + 0.1/x_3 + 1/x_4$ perform union, intersection, difference and complement over the fuzzy set A and B.
   How to answer

   • Recall fuzzy union = max, intersection = min, difference and complement $1-\mu$.
   • Compute membership-wise for $x_1$ to $x_4$.
   • Present resulting fuzzy sets in $a/x$ notation.
10. 7 Marks
    bDistinguished the forward and backward reasoning with example.
    How to answer

    • Define forward (data-driven) vs backward (goal-driven) chaining.
    • Explain inference steps with example rules/facts.
    • Compare with table: direction, use, explanation.
11. 7 Marks
    aExplain how the sematic net used in knowledge representation and reasoning?
    How to answer

    • Define semantic net: nodes as objects/concepts, arcs as relations.
    • Explain inheritance, IS-A, HAS-A with diagram.
    • Explain reasoning by spreading activation / inheritance.
12. 7 Marks
    bExplain the Min-max method? Apply the min-max method to decide which move is to be chosen (Suppose first player is the maximize player).

    

    How to answer

    • Explain MIN-MAX with maximizer/minimizer levels and backup.
    • Evaluate leaf values bottom-up to compute MIN then MAX.
    • Select best child of root as optimal move.
13. 7 Marks
    aExplain the various types of learning in neural network.
    How to answer

    • Define supervised, unsupervised, reinforcement learning.
    • Explain Hebbian, perceptron, backpropagation, competitive learning.
    • Give neural network example for each type.
14. 7 Marks
    bExplain the different component of Natural Language understanding process. https://www.rgpvonline.com
    How to answer

    • List NLU phases: morphological, syntactic, semantic, discourse, pragmatic.
    • Explain role of lexicon, parser, semantic analyzer.
    • Show pipeline with example sentence.
15. 14 Marks
    Write short note on (any three):

    1. a)Expert System
    2. b)Baye's theorem
    3. c)Resolution technique
    4. d)Monotonic and Non-monotonic reasoning
    How to answer

    • Select any three topics with definition and key points.
    • Give formula/architecture/steps and example for each.
    • Mention applications and advantages/limitations.