CA1 SAMPLE MODULE 1 QUESTIONS:
PART A:
1. Define state space.
2. What is the initial state in a search problem?
3. Mention two data structures used in search.
4. What is the difference between BFS and DFS?
5. State the time complexity of BFS.
6. State the space complexity of DFS.
7. Which uninformed search guarantees optimality?
8. What is the branching factor in a search tree?
9. Define iterative deepening search.
10. Write another name of Uniform Cost Search.
11. What is the role of path cost in UCS?
12. Define heuristic function.
13. What is an admissible heuristic?
14. State the evaluation function of Greedy Best-First Search.
15. Write the evaluation function of A* Search.
16. What is Weighted A* Search?
17. State the completeness of A* algorithm.
18. Which algorithm combines the advantages of BFS and DFS?
19. Define goal test in search problems.
20. Which search algorithm is equivalent to Dijkstra’s algorithm?
21. Differentiate between state space and search tree.
22. Why is BFS both complete and optimal?
23. Why is DFS not optimal?
24. State the space complexity of Iterative Deepening Search.
25. What is the major drawback of Uniform Cost Search?
26. When does UCS behave like BFS?
27. Why is DFS memory efficient compared to BFS?
28. Define effective branching factor.
29. What condition ensures optimality of A* Search?
30. Compare admissible and consistent heuristic.
31. State the time complexity of Uniform Cost Search.
32. What is the impact of heuristic accuracy on A* performance?
33. Why is Greedy Best-First Search incomplete in some cases?
34. What is the weighted factor ‘w’ in Weighted A* used for?
35. Why does Iterative Deepening Search combine advantages of BFS and DFS?
36. Explain how path cost g(n) influences A* Search.
37. Which search strategy may revisit the same node multiple times and why?
38. How does memory requirement of A* compare with BFS?
39. What happens if a heuristic overestimates the true cost?
PART B:
1. Explain the general formulation of search problems with suitable examples.
2. Compare BFS, DFS, and UCS in terms of completeness, optimality, time, and space
complexity.
3. Describe Iterative Deepening Depth-First Search (IDDFS). Why is it considered better
than DFS and BFS in some cases?
4. Derive the time and space complexity of BFS and DFS.
5. Explain the concept of heuristic functions. What is admissibility? Give examples.
6. With a neat diagram, explain the working of A* Search algorithm.
7. Differentiate between Greedy Best-First Search and A* Search with suitable examples.
8. Write short notes on: (a) State Space Search (b) Branching Factor (c) Goal Test.
9. Explain Dijkstra’s Algorithm (Generalized UCS) with an example graph.
10. Discuss the effect of heuristic accuracy on the performance of heuristic search
algorithms.
11. Perform Breadth-First Search (BFS) and Depth-First Search (DFS) on the following
graph starting from node A. Write the order of traversal.
Graph (Adjacency):
A → B, C
B → D, E
C→F
D → (none)
E→F
F → (none)
12. Apply Uniform Cost Search (UCS) on the given weighted graph to find the least-cost
path from S to G. Show the steps.
Edges with costs:
S → A (1), S → B (4)
A → C (2), B → C (1)
C → G (3)
13. Using Dijkstra’s Algorithm, find the shortest distance from source A to all other nodes.
Graph (Weighted):
A–B (4), A–C (2)
B–C (5), B–D (10)
C–E (3)
E–D (4)
D–F (11)
14. Apply A* Search on the following graph to find the optimal path from S to G using the
given heuristic values. Show f(n) = g(n)+h(n) table.
Edges with costs:
S → A (1), S → B (4)
A → C (2), B → D (5)
C → G (3), D → G (1)
Heuristic (h):
h(S)=6, h(A)=3, h(B)=5, h(C)=2, h(D)=1, h(G)=0
15. Perform Iterative Deepening Depth-First Search (IDDFS) from node S to goal G on
the following graph. Show the search order at each depth.
Graph:
S → A, B
A → C, D
B→E
C→G
D → (none)
E → (none)
