In-Course Examinations & Solutions

2024 (27th Batch) In-Course Examination

Question 1

1. Consider the following four search algorithms, Dijkstra, Greedy Best-first search, A* and Weighted A* used for pathfinding and decision-making: [6+2+2+2]

a) For each of the above algorithms, explain how the choice of the evaluation function $f(n)$, particularly the role of the heuristic function $h(n)$ and actual cost function $g(n)$ shape the algorithm's behavior in terms of:

• Path optimality
• Search speed
• Dependence on heuristic accuracy
• Amount of search space explored

In your answer, clearly state the conditions under which a heuristic is admissible and/or consistent and explain how these properties affect the outcome of the relevant algorithms.

A* Search and Extensions

---

b) You are designing a navigation agent for a life-critical application (e.g., emergency medical drone delivery). Which algorithm would you choose and why? Justify your decision in terms of path reliability, safety, and computational trade-offs.

---

c) For a time-sensitive but non-critical application (e.g., food delivery in a city), which algorithm would be the most appropriate? Explain your reasoning with reference to the trade-offs between speed, solution quality, and resource efficiency.

---

d) Under what specific condition(s) will all four algorithms return the same path from the start node to the goal node? Provide a brief explanation in terms of cost structure and heuristic values.

---

Question 2

2. In an adversarial search setting, consider the following normal-form game between Player A (Alice) and Player B (Bob): [4*3=12]

Game Theory and Nash Equilibrium

a) Does either player have a dominant strategy? If so, identify it with justification.

---

b) Identify all Pareto optimal outcomes. Show that no other outcome strictly dominates them.

---

c) Determine all Nash equilibria of the game. For each strategy profile, evaluate whether any player has an incentive to deviate.

---

d) Analyze how the strategic tension between individual rationality (Nash equilibrium) and collective benefit (Pareto optimality) is exhibited in this game. Is the Nash equilibrium always Pareto optimal?

---

2023 (26th Batch) In-Course Examination

Question 1

1 a) It is both desirable and challenging to obtain a heuristic function, $h(n)$, that is also admissible. Is this statement correct? What condition a heuristic must satisfy to be considered as an admissible heuristic? [2+3+3+2]

---

b) Is there a method to achieve admissibility without utilizing the so-called relaxed versions of the problem or subproblems (i.e. pattern database)? Discuss that solution within the context of the n-Queen problem.

Heuristic Functions and Optimality

---

c) In a CSP search algorithm, why it is a good heuristic to choose the variable that is most constrained but the value that is least constraining, discuss this with an appropriate example(s).

---

d) What benefit can be directly achieved from the change of CSP formulation to COP formulation? What part of the formulation needs to be changed to achieve this?

Constraint Satisfaction Problems

---

Question 2

2 a) Precision MedTech, a medical technology startup, is developing a "smart diagnostic advisor". Initially focused on general health advice, they now prioritize a system that assists physicians in diagnosing complex or atypical patient cases. They consider three options: A) a traditional rule-based system using crisp logic, B) a backward-chaining expert system designed for differential diagnosis, and C) a fuzzy inference system to handle uncertain or incomplete patient data. Precision MedTech must select one system for development, considering the need for collaboration with physicians (varying tech expertise), a structured diagnostic process, and the inherent uncertainties of medical presentations. In light of the above, list the trade-offs selecting each of the options. [9, 6]

---

b) If you pick the fuzzy inference system, what are the steps required to complete its inference process, and which of them relies on human cognitive intelligence the most, and why?

Fuzzy Expert Systems

---

c) You are given the snapshot of the running calculation of MCTS method shown below.

Starting from this point, you need to proceed with the method and complete two more rollouts (terminal values 15 and 75), and then find out the strategy. If you need to make a random choice, always prefer the right node.

---

d) Finally, what are the pros and cons of MCTS compared to the Alpha-Beta pruning algorithm while performing adversarial search?

Minimax and Alpha-Beta Pruning

Monte Carlo Tree Search