GATE DA & AI Engineering AI Syllabus

AI syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for AI in GATE DA & AI Engineering, not a summary of it.

1. 1

   Search

   3 topics

   • Informed Search
   • Uninformed Search
   • Adversarial Search
2. 2

   Logic

   2 topics

   • Propositional Logic
   • Predicate Logic
3. 3

   Reasoning Under Uncertainty

   3 topics

   • Conditional Independence Representation
   • Exact Inference through Variable Elimination
   • Approximate Inference through Sampling

AI flashcards for GATE DA & AI Engineering

25 of 64 cards from the AI deck — real questions with worked answers.

1. What is the difference between informed (heuristic) search and uninformed (blind) search?

   Uninformed search uses only the problem definition (no domain knowledge beyond goal test and successors), e.g. BFS, DFS, UCS. Informed search uses a problem-specific heuristic function $h(n)$ that estimates the cost from node $n$ to the goal, guiding the search toward promising nodes.

2. Define the heuristic function $h(n)$ and evaluation function $f(n)$ used in best-first search.

   $h(n)$ estimates the cheapest cost of the path from node $n$ to a goal. $f(n)$ is the node-ordering function used to select which node to expand; the frontier is a priority queue ordered by $f(n)$ (smaller first).

3. What evaluation function does Greedy Best-First Search use, and is it optimal or complete?

   It uses $f(n) = h(n)$ (expands the node that appears closest to the goal). It is neither optimal nor complete in general (can get stuck in loops in graph form it is complete in finite spaces, but still not optimal).

4. State the A* search evaluation function and the meaning of each term.

   $$f(n) = g(n) + h(n)$$ where $g(n)$ is the actual cost from the start node to $n$, and $h(n)$ is the estimated cost from $n$ to the goal. A* expands the node with the lowest $f(n)$.

5. What is an admissible heuristic, and what does it guarantee in A*?

   A heuristic is admissible if it never overestimates the true cost to the goal: $h(n) \leq h^{*}(n)$ for all $n$, where $h^{*}(n)$ is the true optimal cost. Admissibility guarantees that tree-search A* is optimal.

6. Define a consistent (monotone) heuristic and give the condition for consistency.

   A heuristic $h$ is consistent if for every node $n$ and every successor $n'$ generated by action $a$ with step cost $c(n,a,n')$: $$h(n) \leq c(n,a,n') + h(n')$$ Consistency implies admissibility and guarantees graph-search A* is optimal (with non-decreasing $f$ along any path).

7. Compare the relationship between consistency and admissibility of heuristics.

   Every consistent heuristic is admissible, but not every admissible heuristic is consistent. Consistency is the stronger condition needed to guarantee optimality of A* in graph search.

8. What does it mean for heuristic $h_2$ to dominate $h_1$, and why is dominance desirable?

   $h_2$ dominates $h_1$ if $h_2(n) \geq h_1(n)$ for all $n$ (both admissible). Dominance is desirable because a higher admissible heuristic expands fewer nodes, so $h_2$ is never less efficient than $h_1$.

9. How can an admissible heuristic be derived from a relaxed problem?

   By removing restrictions on actions, you create a relaxed problem whose optimal solution cost is an admissible (and consistent) heuristic for the original problem, because any solution to the original is also a solution to the relaxed problem.

10. What is Iterative-Deepening A* (IDA*) and what does it improve over A*?

    IDA* performs depth-first searches with an increasing cutoff on $f(n)$ rather than depth. Each iteration's cutoff is the smallest $f$ value that exceeded the previous cutoff. It reduces A*'s memory use to linear while remaining optimal with an admissible heuristic.

11. List the four standard criteria used to evaluate any search algorithm.

    Completeness (does it always find a solution if one exists?), Optimality (does it find the least-cost solution?), Time complexity (number of nodes generated), and Space complexity (maximum number of nodes in memory).

12. Describe Breadth-First Search (BFS): data structure, completeness, and optimality.

    BFS expands the shallowest unexpanded node using a FIFO queue. It is complete (if branching factor $b$ is finite) and optimal when all step costs are equal. Time and space complexity are $O(b^{d})$ where $d$ is the depth of the shallowest goal.

13. Give the time and space complexity of Breadth-First Search and explain its main drawback.

    Both time and space are $O(b^{d})$. The main drawback is memory: BFS must store every generated node in the frontier, so exponential memory usually exhausts before time does.

14. Describe Uniform-Cost Search (UCS): ordering rule and optimality condition.

    UCS expands the node with the lowest path cost $g(n)$ using a priority queue. It is complete and optimal for any step costs $\geq \epsilon > 0$ (non-negative). It is essentially A* with $h(n)=0$ (Dijkstra's algorithm).

15. What is the worst-case time/space complexity of Uniform-Cost Search in terms of cost?

    $$O\!\left(b^{1 + \lfloor C^{*}/\epsilon \rfloor}\right)$$ where $C^{*}$ is the optimal solution cost and $\epsilon$ is the minimum step cost. This can be much greater than $b^{d}$.

16. Describe Depth-First Search (DFS): data structure, completeness, optimality, and space complexity.

    DFS expands the deepest node using a LIFO stack. It is not optimal and not complete in infinite or looping spaces (complete only for finite graph search). Its key advantage is space complexity $O(bm)$, where $m$ is the maximum depth; time is $O(b^{m})$.

17. What is Depth-Limited Search and what problem does it address?

    DFS with a predetermined depth limit $\ell$: nodes at depth $\ell$ have no successors. It addresses DFS's failure in infinite-depth spaces, but is incomplete if $\ell < d$ and non-optimal if $\ell > d$.

18. Describe Iterative Deepening Search (IDS) and why it is often preferred for uninformed search.

    IDS runs depth-limited search with increasing limits $\ell = 0, 1, 2, \dots$ until a goal is found. It combines DFS's space efficiency $O(bd)$ with BFS's completeness and optimality (equal step costs). Time is $O(b^{d})$; repeated work is negligible because lower levels are small.

19. What is Bidirectional Search and what is its main complexity advantage?

    Two simultaneous searches run forward from the start and backward from the goal, stopping when frontiers meet. Time and space complexity reduce to roughly $O(b^{d/2})$, which is much smaller than $O(b^{d})$.

20. In a search problem, distinguish 'tree search' from 'graph search'.

    Tree search does not remember visited states and may re-expand them (risking infinite loops). Graph search keeps an explored/closed set so each state is expanded at most once, avoiding redundant paths and loops.

21. What is the goal of adversarial search, and what defines a zero-sum two-player game?

    Adversarial search finds optimal moves in competitive multi-agent environments. A zero-sum two-player game is one where the players' utilities are exactly opposed: one player's gain equals the other's loss, so utilities sum to a constant (e.g., $+1$ and $-1$).

22. State the minimax value recurrence for a game with MAX and MIN players.

    $$\text{MINIMAX}(s) = \begin{cases} \text{UTILITY}(s) & \text{if } s \text{ is terminal} \\ \max_{a} \text{MINIMAX}(\text{RESULT}(s,a)) & \text{if MAX to move} \\ \min_{a} \text{MINIMAX}(\text{RESULT}(s,a)) & \text{if MIN to move} \end{cases}$$

23. Give the time and space complexity of the minimax algorithm for a game with branching factor $b$ and depth $m$.

    Time complexity is $O(b^{m})$ and space complexity is $O(bm)$ (it performs a depth-first exploration of the game tree).

24. What is alpha-beta pruning and what do $\alpha$ and $\beta$ represent?

    Alpha-beta pruning eliminates branches that cannot affect the minimax decision. $\alpha$ is the best (highest) value found so far for MAX along the path; $\beta$ is the best (lowest) value found so far for MIN. A branch is pruned when $\alpha \geq \beta$.

25. How much can optimal move ordering improve alpha-beta pruning's complexity?

    With perfect move ordering, alpha-beta examines only $O(b^{m/2})$ nodes instead of $O(b^{m})$, effectively reducing the branching factor to $\sqrt{b}$ and doubling the searchable depth.

See more AI flashcards →

Planning AI for GATE DA & AI Engineering

AI (GATE DA & AI Engineering) FAQ