AD-304 Artificial Intelligence - Dec 2023 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
   aFour approaches of AI are Acting Humanly, Thinking humanly, Thinking rationally and Acting rationally. Discuss feasibility of the approaches in current scenario. Which approach is best suitable for rational agent and why?
   How to answer

   • Define the four definitions/approaches to AI: Acting Humanly (Turing test approach), Thinking Humanly (cognitive modelling), Thinking Rationally (laws of thought approach), and Acting Rationally (rational agent approach).
   • Discuss current feasibility: acting/thinking humanly faces limitations in defining/measuring human thought and irrationalities; rational acting/thinking leverages computational models and logic.
   • Explain why Acting Rationally is best suited for designing a rational agent (general framework, mathematically tractable, achieves expected performance given objectives).
2. 7 Marks
   bExplain how A* search different with AO* search technique. Discuss the advantage and disadvantage of both the techniques?
   How to answer

   • Key differences: A* works on OR graphs searching for an optimal single path; AO* works on AND-OR graphs searching for an optimal solution tree/subgraph.
   • A* advantages: guarantees optimal and complete solution if heuristic is admissible; simple evaluation function $f(n) = g(n) + h(n)$.
   • A* disadvantages: high memory and space complexity (keeps all nodes in memory).
   • AO* advantages: handles decomposed problem subtasks requiring conjunctions (AND branches), more memory efficient for decomposable problems.
   • AO* disadvantages: complex implementation, does not guarantee shortest path if cost computation is not properly propagated across branches.
3. 7 Marks
   aState the difference between informed search and uninformed search with suitable example.
   How to answer

   • Define Uninformed (Blind) Search: relies only on state transitions and problem definition (e.g., BFS, DFS, UCS).
   • Define Informed (Heuristic) Search: uses domain-specific knowledge or heuristic functions $h(n)$ to guide the search (e.g., Greedy Best-First, A*).
   • Provide a comparative table: time complexity, space complexity, optimality, knowledge utilization.
   • Provide an illustrative example (e.g., finding the shortest path on a map using Euclidean distance heuristic vs searching blindly with BFS).
4. 7 Marks
   bFor the Blocks World problem given below, use Hill Climbing to show the next 3 best moves. State and use a suitable global heuristic.

   

   How to answer

   • Define a suitable global heuristic (e.g., for each block: +1 for every block correctly placed under it down to table, -1 for every block incorrectly placed under it down to table).
   • Calculate the initial state heuristic score.
   • Generate possible successor moves from the current state (valid block moves: move a clear block onto table or onto another clear block).
   • Select the best move that maximizes the heuristic at each step (Move 1, Move 2, Move 3) following standard Hill Climbing.
   • Show state diagrams for the chosen 3 successive moves.
5. 7 Marks
   aConsider the following facts: i) Steve likes easy courses ii) Science courses are hard iii) All the courses in the CSE department are easy iv) CS3101 is a CSE department course 1) Translate these into predicate logic. 2) Convert them into clausal form. 3) Using resolution prove "What course would Steve like".
   How to answer

   • 1) Convert sentences to FOL: $\forall x (\text{Easy}(x) \rightarrow \text{Likes}(\text{Steve}, x))$, $\forall x (\text{Science}(x) \rightarrow \text{Hard}(x))$, $\forall x (\text{CSE}(x) \rightarrow \text{Easy}(x))$, $\text{CSE}(\text{CS3101})$.
   • 2) Convert each FOL sentence into CNF/clausal form: (C1) $\neg\text{Easy}(x) \vee \text{Likes}(\text{Steve}, x)$, (C2) $\neg\text{CSE}(y) \vee \text{Easy}(y)$, (C3) $\text{CSE}(\text{CS3101})$.
   • 3) Set up resolution: Negate query $\neg\text{Likes}(\text{Steve}, z)$ or with answer literal $\text{Ans}(z)$, unify $x$ with $z$, resolve with (C1) yielding $\neg\text{Easy}(z)$, resolve with (C2) giving $\neg\text{CSE}(z)$, resolve with (C3) giving $z = \text{CS3101}$ and an empty clause.
   • Conclude that Steve likes CS3101.
6. 7 Marks
   bDescribe the difference between Depth First Search (DFS) and Breath First Search (BFS) with suitable example.
   How to answer

   • Define BFS: traverses level by level using a Queue (FIFO).
   • Define DFS: traverses deepest nodes first using a Stack (LIFO) or recursion.
   • Tabulate differences: Space complexity ($O(b^d)$ vs $O(bm)$), Time complexity, Completeness, Optimality.
   • Provide a small tree/graph example showing the exact sequence of visited nodes for BFS and DFS.
7. 7 Marks
   aWhat are the key advantages of using Bayes theorem compared to other probability frameworks?
   How to answer

   • State Bayes theorem: $P(A|B) = \frac{P(B|A)P(A)}{P(B)}$.
   • Key advantage 1: Ability to update beliefs systematically as new evidence arrives (prior to posterior).
   • Key advantage 2: Transparent handling of uncertainty and subjective beliefs compared to purely frequentist approaches.
   • Key advantage 3: Effective in handling incomplete, noisy data and foundation for Bayesian Networks.
   • Key advantage 4: Combines observable evidence with prior domain knowledge.
8. 7 Marks
   bConsider the following graph The numbers written on edges represent the distance between the nodes. The numbers written on nodes represent the heuristic value. Find the most cost-effective path to reach from start state A to final state J using A* Algorithm.

   

   How to answer

   • State the A* evaluation formula: $f(n) = g(n) + h(n)$.
   • Maintain OPEN and CLOSED lists.
   • Step 1: Start at A: $g(A)=0, f(A)=10$. Expand A to B ($g=6, f=6+8=14$) and F ($g=3, f=3+6=9$).
   • Step 2: Pick F (minimum $f=9$). Expand F to G ($g=4, f=4+5=9$) and H ($g=10, f=10+3=13$).
   • Step 3: Pick G ($f=9$). Expand G to I ($g=4+3=7, f=7+1=8$).
   • Step 4: Pick I ($f=8$). Expand I to J ($g=7+3=10, f=10+0=10$).
   • Continue expansions until goal node J is popped from OPEN with minimum $f$.
   • State final optimal path: A -> F -> G -> I -> J with total cost 10.
9. 7 Marks
   aWrite short notes on: i) Propositional logic ii) First Order Predicate logic
   How to answer

   • i) Propositional Logic: Boolean logic dealing with propositions (true/false), connectives (AND, OR, NOT, IMPLIES, BICONDITIONAL), syntax, semantics, and truth tables. Limitations in expressing relations and generalizations.
   • ii) First Order Predicate Logic (FOL): Extends propositional logic with objects, predicates, functions, and quantifiers (Universal $\forall$ and Existential $\exists$). Higher expressive power to represent complex real-world statements.
10. 7 Marks
    bHow would you define Natural Language Processing (NLP) and its significance in today's technological landscape?
    How to answer

    • Definition of NLP: subfield of AI concerned with enabling computers to understand, interpret, and generate human language.
    • Two main components: Natural Language Understanding (NLU) and Natural Language Generation (NLG).
    • Significance in today's technology: powering virtual assistants (Siri, Alexa), chatbots, machine translation, sentiment analysis, search engines, and modern LLMs (e.g., ChatGPT).
    • Key challenges: ambiguity, context, idioms, sarcasm.
11. 7 Marks
    aWhat are the key advantage and limitations of expert systems in the field of Artificial Intelligence?
    How to answer

    • Brief definition of Expert Systems: AI software emulating the decision-making ability of human experts.
    • Key advantages: high availability, consistency in decision-making, reduced cost of human expertise, explanations for conclusions, handles domain-specific complex tasks.
    • Limitations: knowledge acquisition bottleneck, lack of common sense reasoning, brittle outside specific narrow domain, cannot adapt or learn autonomously from new situations.
12. 7 Marks
    bWhat are the main differences between forward chaining and backward chaining in expert systems, and when would you prefer to use each approach?
    How to answer

    • Define Forward Chaining: data-driven inference starting from known facts to infer new facts until goal/conclusion is reached.
    • Define Backward Chaining: goal-driven inference starting with a hypothesis/goal and searching backward to find supporting facts.
    • Differences: direction, efficiency, search space size.
    • When to use Forward Chaining: planning, monitoring, control problems where data is plentiful and goals are many/unspecified.
    • When to use Backward Chaining: diagnostic systems, debugging, medical diagnosis where a specific hypothesis needs verification.
13. 7 Marks
    aConsider a state space where the start state is number 1 and the successor function for state n returns two states, numbers 2n and 2n + 1. i) Draw the portion of the state space for states 1 to 15. ii) Suppose the goal state is 11. List the order in which nodes will be visited for breadth-first search, depth-first search with limit 3.
    How to answer

    • i) Draw the complete binary tree of 4 levels (depths 0 to 3): - Level 0: 1 - Level 1: 2, 3 - Level 2: 4, 5, 6, 7 - Level 3: 8, 9, 10, 11, 12, 13, 14, 15.
    • ii) BFS node visitation order until goal 11 is found: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11.
    • Depth-first search with limit 3 (depth 0, 1, 2, 3): - Path down leftmost: 1 -> 2 -> 4 -> 8, backtrack, 9, backtrack to 4, backtrack to 2 -> 5 -> 10, backtrack, 11 (Goal reached). - List exact visitation sequence: 1, 2, 4, 8, 9, 5, 10, 11.
14. 7 Marks
    bThe heuristic values for each state are shown below. Given these values, draw a diagram in that illustrates the search tree of explored states, using A* search (the path cost is still a unit cost). Indicate the calculated cost at each node in the tree. $$\begin{array}{|ll|ll|} \hline \text{A:} & 9 & \text{G:} & 3 \\ \text{B:} & 4 & \text{H:} & 5 \\ \text{C:} & 5 & \text{I:} & 8 \\ \text{D:} & 7 & \text{J:} & 2 \\ \text{E:} & 3 & \text{K:} & 0 \\ \text{F:} & 10 & \text{L:} & 7 \\ \hline \end{array}$$
    How to answer

    • Identify start state (A) and goal state (K with h=0).
    • At each node, compute $g(n)$ (depth/step count) and $f(n) = g(n) + h(n)$.
    • Expand nodes in increasing order of $f(n)$.
    • Draw the explored search tree indicating for each node its name, $g(n)$, $h(n)$, and $f(n)$.
15. 7 Marks
    aConsider following tree below: [Tree is shown in figure] Apply $\alpha$-$\beta$ pruning and identify the all prune node for the given above tree.

    

    How to answer

    • Identify player levels: Root is MAX (P), Level 1 is MIN (Q), Level 2 is MAX (P), Level 3 is MIN (Q), and Leaves are terminal values: 2, 8, 3, 1, 6, 9, 8, 9, 3, 10, 2, 14, 16, 8, 15, 18.
    • Perform depth-first traversal tracking $[\alpha, \beta]$ initialized to $[-\infty, +\infty]$.
    • Evaluate leftmost subtree: MIN node with leaves 2, 8 gets value 2; sibling MIN node with leaves 3, 1 gets value 1. Their parent MAX node chooses $\max(2, 1) = 2$.
    • Propagate values to MIN node at Level 1 and evaluate next subtrees with updated bounds.
    • Check cutoff condition $\alpha \ge \beta$ at each step.
    • Clearly list all pruned subtrees/leaf nodes (e.g., the branch with leaf 18 or intermediate nodes as marked by the cross on the figure).
16. 7 Marks
    bWhat are the critical factors to consider when designing and developing an effective expert system?
    How to answer

    • Domain suitability: ensuring the problem is well-defined, bounded, and requires expert judgment rather than common sense.
    • Knowledge acquisition and representation: efficient extraction of domain rules from experts and suitable formalism (production rules, frames, semantic networks).
    • Inference mechanism: choosing appropriate chaining strategy (forward vs backward) and conflict resolution.
    • Uncertainty handling: dealing with incomplete, uncertain, or probabilistic information (certainty factors, fuzzy logic, Bayesian).
    • User interface and explanation facility: providing transparent, understandable rationales for recommendations.
    • Maintainability and scalability: modular knowledge base design for easy updating and testing.