AI/ML Unit 1 & 2: Book-Back Questions form Syllabus PDF
Generated and Prepared By Thiruselvan (ThiruXD)
Short Answer Questions
1. Define Artificial Intelligence.
Artificial Intelligence (AI) is the branch of computer science that aims to create machines or systems capable of performing tasks that normally require human intelligence. These tasks include learning, reasoning, problem-solving, perception, understanding language, and decision-making.
2. What is a production system?
A production system is a knowledge representation and problem-solving model consisting of:
- A set of production rules (if-then rules),
- A working memory (global database of facts),
- A control strategy (which decides which rule to apply).
It is widely used in expert systems and rule-based AI systems.
3. Explain state space representation.
State space representation is a way of modeling a problem as a graph where:
- Nodes represent states of the problem,
- Edges represent operators/actions that transform one state into another,
- The goal is to find a path from the initial state to a goal state.
It is the foundation of most search algorithms in AI.
4. Define heuristic function.
A heuristic function ( h(n) ) is an estimate of the cost or distance from a given state ( n ) to the goal state. It is used in informed search algorithms (like A*, Best-First Search, Hill Climbing) to guide the search towards promising paths and reduce the search space.
5. What is problem reduction?
Problem reduction is a technique in which a complex problem is broken down into smaller, simpler sub-problems. Solving all the sub-problems leads to the solution of the original problem. It is commonly represented using AND-OR graphs.
6. Explain constraint satisfaction problems.
Constraint Satisfaction Problems (CSPs) are problems defined by:
- A set of variables,
- A set of domains (possible values for each variable),
- A set of constraints that restrict the allowed combinations of values.
The goal is to assign values to all variables such that all constraints are satisfied. Examples: Map coloring, Sudoku, N-Queens, scheduling.
7. What is hill climbing?
Hill Climbing is a local search heuristic algorithm that starts from an initial state and repeatedly moves to a neighboring state that improves the evaluation function (heuristic). It is called “hill climbing” because it tries to climb towards a peak (better solution). It can get stuck in local maxima.
8. Differentiate BFS and DFS.
| Feature | Breadth-First Search (BFS) | Depth-First Search (DFS) |
|---|---|---|
| Strategy | Explores level by level | Explores as deep as possible first |
| Data Structure | Queue | Stack (or recursion) |
| Completeness | Complete (if branching factor finite) | Not complete (can go infinite depth) |
| Optimality | Optimal (for uniform cost) | Not optimal |
| Space Complexity | High (O(b^d)) | Lower (O(bd)) |
| Time Complexity | O(b^d) | O(b^d) |
9. Define Means-End Analysis.
Means-End Analysis is a problem-solving technique that identifies the difference between the current state and the goal state, then selects operators that reduce this difference. It is used in GPS (General Problem Solver) and planning systems.
10. What are AI applications?
Common applications of AI include:
- Expert systems
- Natural Language Processing (chatbots, translation)
- Computer Vision (face recognition, autonomous vehicles)
- Robotics
- Game playing (Chess, Go)
- Recommendation systems
- Speech recognition
- Medical diagnosis
- Fraud detection
Long Answer Questions
1. Explain the characteristics and applications of Artificial Intelligence.
Characteristics of AI:
- Ability to learn from experience (machine learning)
- Reasoning and decision-making under uncertainty
- Perception of the environment (vision, speech)
- Natural language understanding
- Problem-solving and planning
- Knowledge representation
- Adaptation to new situations
Applications of AI:
- Healthcare: disease diagnosis, drug discovery
- Finance: fraud detection, algorithmic trading
- Transportation: self-driving cars
- Education: intelligent tutoring systems
- Entertainment: recommendation engines, game AI
- Manufacturing: predictive maintenance, robotics
- Customer service: chatbots and virtual assistants
- Security: facial recognition, anomaly detection
2. Discuss state space search with suitable examples.
State space search represents a problem as a graph of states connected by operators.
Components:
- Initial state
- Operators (actions)
- Goal test
- Path cost
Example 1 – 8-Puzzle:
States are different arrangements of tiles. Operators are moving the blank space up/down/left/right. Goal is a specific arrangement.
Example 2 – Travelling Salesman Problem:
States are partial tours. Operators add a new city. Goal is a complete tour of minimum cost.
Search algorithms (BFS, DFS, A*, etc.) explore this state space to find a solution path.
3. Explain Breadth First Search and Depth First Search with algorithms.
Breadth-First Search (BFS):
- Explores all nodes at the current depth before going deeper.
- Uses a Queue.
- Guarantees shortest path in terms of number of edges.
Algorithm (BFS):
- Enqueue the start node.
- While queue is not empty:
- Dequeue a node.
- If it is the goal → return solution.
- Enqueue all its unvisited children.
Depth-First Search (DFS):
- Explores as far as possible along each branch before backtracking.
- Uses a Stack (or recursion).
- May not find the shortest path and can get stuck in infinite paths.
Algorithm (DFS):
- Push the start node onto the stack.
- While stack is not empty:
- Pop a node.
- If it is the goal → return solution.
- Push all its unvisited children onto the stack.
4. Describe heuristic search techniques in detail.
Heuristic search uses domain-specific knowledge (heuristic function) to guide the search.
Main techniques:
- Generate-and-Test: Generate possible solutions and test them.
- Hill Climbing: Move to the best neighboring state.
- Best-First Search: Always expand the most promising node according to the heuristic.
- A Search: Uses ( f(n) = g(n) + h(n) ) where ( g(n) ) is cost so far and ( h(n) ) is estimated cost to goal.
- Means-End Analysis: Reduce differences between current and goal state.
- Constraint Satisfaction: Assign values while satisfying constraints.
These techniques reduce the effective search space compared to uninformed search (BFS/DFS).
5. Explain Best First Search and Hill Climbing algorithms.
Best-First Search:
- Uses a priority queue ordered by a heuristic evaluation function.
- At each step, the most promising node is selected for expansion.
- Variants: Greedy Best-First (uses only ( h(n) )) and A* (uses ( g(n) + h(n) )).
Hill Climbing:
- A local search algorithm.
- Starts from a current state.
- Evaluates all neighbors.
- Moves to the neighbor with the best (highest/lowest) heuristic value.
- Stops when no better neighbor exists (local optimum).
Limitations of Hill Climbing: Local maxima, plateau, and ridges.
6. Discuss constraint satisfaction problems with examples.
A CSP consists of variables, domains, and constraints.
Goal: Find an assignment of values to variables that satisfies all constraints.
Examples:
- Map Coloring: Variables = regions, Domain = colors, Constraint = adjacent regions must have different colors.
- N-Queens: Place N queens on an N×N chessboard so that no two attack each other.
- Sudoku: Fill a 9×9 grid so that each row, column, and 3×3 box contains digits 1–9 exactly once.
- Job Scheduling: Assign jobs to time slots without resource conflicts.
Techniques used: Backtracking, Forward Checking, Arc Consistency, Heuristics (MRV, LCV).
7. Explain Means-End Analysis with a suitable example.
Means-End Analysis works by detecting differences between the current state and the goal state, then selecting operators that reduce those differences.
Steps:
- Compare current state with goal state → find differences.
- Select an operator that reduces the most significant difference.
- Apply the operator (may create sub-goals).
- Repeat until the goal is reached.
Example – Travelling from home to college:
- Difference: Distance
- Operator: Take a bus/car
- Sub-goal: Reach the bus stop
- New difference: Not at bus stop
- Operator: Walk to bus stop
- Continue until goal is achieved.
8. Write notes on production systems and problem characteristics.
Production Systems: A production system has three main components:
- Set of production rules (condition → action)
- Working memory / Global database
- Control strategy / Inference engine (decides which rule to fire)
Control strategies can be:
- Irrevocable
- Tentative (with backtracking)
- Data-driven (forward chaining)
- Goal-driven (backward chaining)
Problem Characteristics (that affect the choice of search method):
- Is the problem decomposable?
- Can solution steps be ignored or undone?
- Is the universe predictable?
- Is a good solution absolute or relative?
- Is the knowledge base consistent?
- Does the problem require interaction with humans?
These characteristics help decide whether to use forward/backward chaining, search algorithms, or planning techniques.