(5th sem)AIML Chapter 1: Questions & Answers
Chapter 1: Problems and Search -> Generated and Prepared By Thiruselvan (ThiruXD)
A. Multiple Choice Questions (with Answers)
1. Who coined the term “Artificial Intelligence”?
a) Alan Turing b) John McCarthy c) Elaine Rich d) Marvin Minsky
Answer: b) John McCarthy
2. According to Elaine Rich, AI is the study of how to make computers do things at which:
a) Machines are better b) People are better c) Animals are better d) Robots are better
Answer: b) People are better
3. Which of the following is not a major concept of AI?
a) Learning b) Reasoning c) Compilation d) Perception
Answer: c) Compilation
4. The three fundamental assumptions of AI are:
a) Speed, Memory, Accuracy b) Rationality, Knowledge-based, Learning
c) Search, Sort, Store d) Hardware, Software, Data
Answer: b) Rationality, Knowledge-based, Learning
5. An AI problem is generally:
a) Simple and fixed b) Complex, uncertain and dynamic
c) Always deterministic d) Solved by fixed algorithms only
Answer: b) Complex, uncertain and dynamic
6. The collection of all possible states in a problem is called:
a) Solution space b) Problem space c) Search tree d) Goal set
Answer: b) Problem space
7. In a problem space, the starting condition is called:
a) Goal state b) Intermediate state c) Initial state d) Operator
Answer: c) Initial state
8. Actions that transform one state into another are called:
a) Heuristics b) Operators c) Constraints d) Rules
Answer: b) Operators
9. Breadth-First Search uses which data structure?
a) Stack b) Queue c) Tree d) Graph only
Answer: b) Queue
10. Depth-First Search uses which data structure?
a) Queue b) Stack c) Priority Queue d) Linked List
Answer: b) Stack
11. Which search is guaranteed to find the shortest path (in terms of number of steps)?
a) DFS b) BFS c) Hill Climbing d) Generate and Test
Answer: b) BFS
12. A heuristic function estimates:
a) Exact cost to goal b) Cost from start to current node
c) Cost from current node to goal d) Total path cost only
Answer: c) Cost from current node to goal
13. Hill Climbing can get stuck in:
a) Global maximum b) Local maxima c) Optimal path d) Queue overflow
Answer: b) Local maxima
14. Which technique always expands the most promising node first?
a) BFS b) DFS c) Best-First Search d) Random Search
Answer: c) Best-First Search
15. CSP stands for:
a) Computer System Programming b) Constraint Satisfaction Problem
c) Central Search Process d) Complex State Planning
Answer: b) Constraint Satisfaction Problem
16. The three components of a CSP are:
a) States, Operators, Goals b) Variables, Domains, Constraints
c) Nodes, Edges, Weights d) Facts, Rules, Inference
Answer: b) Variables, Domains, Constraints
17. Means-Ends Analysis works by:
a) Generating all possible solutions b) Reducing the difference between current and goal state
c) Using only BFS d) Ignoring constraints
Answer: b) Reducing the difference between current and goal state
18. Which of the following is an example of a CSP?
a) Chess playing b) Map colouring / Sudoku / Timetable scheduling
c) Simple arithmetic d) File sorting
Answer: b) Map colouring / Sudoku / Timetable scheduling
19. Forward Chaining starts from:
a) Goal b) Known facts c) Heuristic d) Random state
Answer: b) Known facts
20. Which search technique is uninformed?
a) A* b) Best-First c) BFS d) Hill Climbing
Answer: c) BFS
B. Theory Questions with Answers
1. Define Artificial Intelligence. Give any two standard definitions.
Answer:
Artificial Intelligence is the branch of computer science that focuses on creating systems capable of performing tasks that normally require human intelligence such as learning, reasoning, problem-solving, perception and decision-making.
- John McCarthy: “AI is the science and engineering of making intelligent machines, especially intelligent computer programs.”
- Elaine Rich: “AI is the study of how to make computers do things at which, at the moment, people are better.”
2. List and explain the five major concepts of AI.
Answer:
- Learning – Ability to improve performance from experience.
- Reasoning – Drawing conclusions from available information.
- Problem Solving – Finding suitable solutions to complex situations.
- Knowledge Representation – Storing information in a structured form usable by computers.
- Perception – Interpreting data from sensors, images, speech etc.
3. What are the characteristics of AI Problems? Give examples.
Answer:
- Complexity – Large number of variables and solutions (e.g., Chess)
- Uncertainty – Incomplete information (e.g., Medical diagnosis)
- Dynamic Nature – Environment changes (e.g., Autonomous driving)
- Knowledge Intensive – Needs domain knowledge (e.g., Expert systems)
- Goal-Oriented – Aims to achieve a specific objective
4. Explain the components of a Problem Space with an example.
Answer:
A Problem Space consists of:
- Initial State – Starting condition
- Goal State – Desired final condition
- Operators – Actions that change one state to another
- State Space – All possible reachable states
Example (Route Finding):
Initial State = Bengaluru, Goal State = Mysuru, Operators = roads between cities, State Space = all cities and connecting routes.
5. Differentiate between BFS and DFS.
Answer:
| Feature | BFS | DFS |
|---|---|---|
| Data Structure | Queue (FIFO) | Stack (LIFO) |
| Exploration | Level by level | Depth-wise |
| Shortest Path | Yes (uniform cost) | Not guaranteed |
| Memory Requirement | High | Low |
| Completeness | Yes | No (in infinite spaces) |
| Optimality | Yes | No |
6. What is a Heuristic? Explain the role of heuristic function.
Answer:
A heuristic is a rule of thumb or educated guess that helps guide the search towards the goal.
The heuristic function h(n) estimates the cost of the cheapest path from the current node n to the goal. It makes search more efficient by focusing on promising paths.
7. Explain Hill Climbing algorithm. What are its limitations?
Answer:
Hill Climbing is a heuristic search technique that always moves to a neighbouring state that is better than the current state (like climbing a hill).
Limitations:
- Can get stuck in local maxima
- Cannot handle plateaus or ridges well
- May miss the global optimum
8. What is a Constraint Satisfaction Problem (CSP)? Give its components and examples.
Answer:
A CSP is a problem defined by:
- Variables – Things to which values must be assigned
- Domains – Possible values for each variable
- Constraints – Restrictions that must be satisfied
Examples: Map colouring, Sudoku, exam timetable, job scheduling, resource allocation.
9. Explain Means-Ends Analysis.
Answer:
Means-Ends Analysis is a problem-solving strategy that:
- Compares the current state with the goal state
- Identifies the difference
- Selects an operator that reduces the difference
- Applies the operator and repeats until the goal is reached
It is widely used in planning systems and expert systems.
10. List the four components of an AI Technique and explain each briefly.
Answer:
- Knowledge Base – Stores facts, rules and domain knowledge
- Inference Mechanism – Reasons and draws conclusions (Forward/Backward chaining)
- Search Strategy – Explores possible solutions
- Learning Mechanism – Improves performance through experience
C. Analytical / Application Questions with Answers
1. Represent the following problem as a Problem Space:
“A robot has to move from room A to room D in a building with rooms A, B, C, D connected by doors.”
Answer:
- Initial State: Robot in Room A
- Goal State: Robot in Room D
- Operators: Move through door (A→B, B→C, C→D, etc.)
- State Space: All possible locations of the robot (A, B, C, D)
2. Why is BFS preferred over DFS when the solution is expected at a shallow depth?
Answer:
BFS explores level by level, so it finds the shallowest (shortest) solution first. DFS may go very deep along a wrong path and take much longer or get stuck, even if a short solution exists.
3. A medical expert system diagnoses diseases using symptoms. Identify which AI Technique components are used.
Answer:
- Knowledge Base → Stores disease-symptom rules
- Inference Mechanism → Applies rules to patient symptoms (usually Backward or Forward chaining)
- Search Strategy → Explores possible diseases
- Learning Mechanism → Can improve accuracy with new cases
4. Why does Hill Climbing fail in some problems? Suggest a solution.
Answer:
Hill Climbing fails because it can get stuck in local maxima, plateaus or ridges.
Solutions: Use random restarts, simulated annealing, or switch to Best-First / A* search.
5. Formulate “Exam Timetable Generation” as a CSP.
Answer:
- Variables: Each exam slot / subject
- Domains: Possible time slots and rooms
- Constraints:
- No student should have two exams at the same time
- Room capacity should not be exceeded
- Some subjects cannot be scheduled on the same day
6. Compare Generate-and-Test with Hill Climbing.
Answer:
- Generate-and-Test generates complete solutions and tests them. It is simple but inefficient for large spaces.
- Hill Climbing improves the current state step-by-step. It is faster but can get stuck in local maxima.
7. A navigation app finds the best route from home to college. Which search techniques can be used and why?
Answer:
- BFS – If we want the route with minimum number of turns/roads
- Heuristic Search (Best-First or A)– If we want the fastest or shortest distance route (using distance or traffic as heuristic) Heuristic search is preferred in real systems because the search space is very large.
Quick Revision Checklist for Chapter 1
- Definitions of AI (McCarthy & Rich)
- 5 Concepts + Goals + Characteristics of AI
- AI vs Natural Intelligence table
- Components of Problem Space
- BFS vs DFS table
- Heuristic, Hill Climbing & its limitations
- CSP components + examples
- Means-Ends Analysis
- 4 Components of AI Techniques