Basics of AI 2025

(a) Which search method always finds the shallowest goal node?

1. Depth-first search
2. Breadth-first search
3. Hill climbing
4. Best-first search

(b) Hill climbing algorithm can get stuck in:

1. Global maxima
2. Saddle points
3. Local maxima
4. None of these

(c) The Resolution principle is used for:

1. Syntax checking
2. Search optimization
3. Logical inference
4. Data clustering

(d) Scripts are used to represent:

1. Events and sequences of actions
2. Mathematical models
3. Logical formulas
4. Algorithms

(e) A context-free grammar (CFG) has productions of the form:

1. $\alpha \rightarrow \beta$ where both $\alpha$ and $\beta$ may be any strings of terminals/nonterminals
2. $A \rightarrow aB$ or $A \rightarrow a$
3. $A \rightarrow \alpha$ where $A$ is a single nonterminal and $\alpha$ is a string of terminals/nonterminals
4. $\alpha \rightarrow \beta$ where $|\alpha| \le |\beta|$

(f) Which of the following is not a component of natural-language communication?

1. Syntax
2. Semantics
3. Pragmatics
4. Compilation

(g) In top-down parsing, which rule is usually applied to avoid infinite recursion?

1. Left factoring
2. Operator precedence
3. $\epsilon$-production removal
4. Common subexpression elimination

(h) Augmented Transition Networks (ATN) extend RTNs by adding:

1. Registers and conditions
2. Random transitions
3. Probability
4. Grammar pruning

(i) In Q-learning, the update rule is based on:

1. Gradient descent
2. Bellman equation
3. Backpropagation
4. Search trees

(j) Decision Networks combine:

1. Search and logic
2. CSPs
3. Bayesian networks and utilities
4. Heuristics

(a) Define Artificial Intelligence. Explain the characteristics of an intelligent agent with examples.

(b) Describe Heuristic Search. Explain the working of the $A^*$ algorithm with a suitable example.

(a) Explain the Minimax algorithm for game playing. How does alpha-beta pruning optimize it? Show with a game tree example.

(b) Define a Constraint Satisfaction Problem (CSP). Explain how Means-End Analysis can be used to reduce the difference between current and goal states.

(a) Given the following premises:

1. $P \rightarrow (Q \rightarrow R)$
2. $P \land Q$

(i) Using rules of inference, derive $R$ step by step.
(ii) Verify the validity of your conclusion using a truth table.

(b) What are Semantic Networks and Conceptual Dependencies? Explain how conceptual dependencies capture meaning of the event better than a semantic net. Represent the following situation using both representations and compare them:

"John gave a book to Mary."

Explain how conceptual dependencies capture the meaning of the event better than a semantic net.

(a) Describe the Resolution principle in First-Order Predicate Logic. Show how resolution can be used to prove that "Socrates is mortal" from the given premises:

1. All men are mortal.
2. Socrates is a man.

Include all intermediate steps like conversion to CNF, substitution, and resolution steps.

(b) Define parsing and semantics in the context of formal language processing. Explain with an example how a parser analyzes the syntactic structure of a sentence and how semantic analysis ensures that the sentence has a valid meaning.

(a) Classify the following grammars according to Chomsky's hierarchy, giving justification for each:
(i) $S \rightarrow aS | b$
(ii) $S \rightarrow aA$, $A \rightarrow b|e$
(iii) $S \rightarrow aSbS | \epsilon$
(iv) $S \rightarrow aSb | bSa | \epsilon$

(b) Consider the grammar:
$E \rightarrow E + T | T$
$T \rightarrow T \times F | F$
$F \rightarrow (E) | id$
Construct the parse tree and show the derivation steps for the input string: $id + id \times id$.

(a) What is a Recursive Transition Network (RTN)? Explain how RTNs extend finite-state machines to represent recursive syntactic structures in language. Draw an RTN to represent the structure of a simple English sentence: "The boy eats an apple."

(b) Explain Utility Theory in Artificial Intelligence. How is utility used to model an agent's preferences and rational decision-making under uncertainty? Illustrate with an example of an AI agent choosing between risky actions based on expected utility.

(a) Explain the concept of Game Theory in AI. Differentiate between cooperative and non-cooperative games, and describe how the Nash Equilibrium is used to find stable strategies. Illustrate with a payoff matrix example for the Prisoner's Dilemma.

(b) Discuss how AI and Machine Learning can provide solutions to real-time decision-making problems. Explain with a case study or example from one of the following domains:

(i) Smart traffic management
(ii) Fraud detection
(iii) Healthcare diagnostics
(iv) Personalized recommendation systems

(a) Differentiate between Passive RL and Active RL. Explain how exploration and exploitation play a role in Active RL. Use an example (e.g., robot navigation or game playing) to show how an agent updates both its policy and utility estimates.

(b) Write short note on any two:

(i) Deep Reinforcement Learning
(ii) Context-Free Grammar
(iii) Breadth-first search vs depth-first search