cs3003_2025T3_Q1_NA.pdf
AI: Search Methods for Problem Solving · Quiz 1 · Sep 2025
← Course papers · Start practice / exam
Questions and published explanations below are available without starting a test. Some questions may not have a published solution yet.
Question 117 MSQ · 3.0 marks
[[IMAGE:906f4e4af6984c56_1_4]]
Process Q1 is in the RUNNABLE state.
Process Q2 is in the RUNNING state.
Process Q3 is in the RUNNABLE state.
Process Q3 is in the SLEEPING state.
Process Q4 is in the ZOMBIE state.
Process Q4 is in the SLEEPING state.
**AI**
**Section Id :** 640653106435
**Section Number :** 8
**Section type :** Online
**Mandatory or Optional :** Mandatory
**Number of Questions :** 5
**Number of Questions to be attempted :** 5
**Section Marks :** 20
**Display Number Panel :** Yes
**Section Negative Marks :** 0
**Group All Questions :** No
**Enable Mark as Answered Mark for Review and**
No
**Clear Response :**
**Section Maximum Duration :** 0
**Section Minimum Duration :** 0
**Section Time In :** Minutes
**Maximum Instruction Time :** 0
A published solution is not available for this question yet.
Question 119 MSQ · 1.0 marks
**STATE SPACE**
Consider 3-puzzle (a smaller version of 8-puzzle) where a tile (carrying a numeric label) can slide
one position either horizontally or vertically into the **adjacent empty spot,** effectively swapping
the tile and the adjacent empty spot. A tile cannot slide diagonally.
[[IMAGE:906f4e4af6984c56_3_5]]
Begin from the start state and build the state space graph by generating valid moves, call it Graph-
1230, use this graph to answer the sub-questions.
[[IMAGE:906f4e4af6984c56_3_6]]
State A
State B
State C
State D
A published solution is not available for this question yet.
Question 120 MSQ · 1.0 marks
**STATE SPACE**
Consider 3-puzzle (a smaller version of 8-puzzle) where a tile (carrying a numeric label) can slide
one position either horizontally or vertically into the **adjacent empty spot,** effectively swapping
the tile and the adjacent empty spot. A tile cannot slide diagonally.
[[IMAGE:906f4e4af6984c56_3_5]]
Begin from the start state and build the state space graph by generating valid moves, call it Graph-
1230, use this graph to answer the sub-questions.
Select the statements that are true about Graph-1230.
Every move is reversible.
Every state has a path to every other state.
Some states have more than two neighbours.
Every state has exactly two neighbours.
Every state has exactly one neighbour.
A published solution is not available for this question yet.
Question 121 MCQ · 1.0 marks
**STATE SPACE**
Consider 3-puzzle (a smaller version of 8-puzzle) where a tile (carrying a numeric label) can slide
one position either horizontally or vertically into the **adjacent empty spot,** effectively swapping
the tile and the adjacent empty spot. A tile cannot slide diagonally.
[[IMAGE:906f4e4af6984c56_3_5]]
Begin from the start state and build the state space graph by generating valid moves, call it Graph-
1230, use this graph to answer the sub-questions.
The number of unique states in Graph-1230 is __________ .
less than 8
equal to 8
more than 8
A published solution is not available for this question yet.
Question 122 SHORT_TEXT · 1.0 marks
**SEARCH**
The MoveGen function and the heuristic function for a state space is provided below. Take S as the
start node and G as the goal node.
When required use alphabetical order to break ties.
[[IMAGE:906f4e4af6984c56_4_7]]
When we say a node is inspected/expanded/refined it means: the node is picked up from OPEN,
and goal test is called, if goal test fails then MoveGen is called and, depending on the algorithm,
the neighbours are selectively placed in OPEN.
Assume that the RemoveSeen procedure will drop the neighbours that are already present in the
OPEN or CLOSED list.
Based on the above data, answer the given subquestions.
List the first 4 nodes inspected by Depth First Search. List the nodes in the order they are
inspected. If the algorithm terminates early then list the nodes inspected up until termination.
Enter a comma separated list of node labels.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: S,X,Y,Z**
A published solution is not available for this question yet.
Question 123 SHORT_TEXT · 1.0 marks
**SEARCH**
The MoveGen function and the heuristic function for a state space is provided below. Take S as the
start node and G as the goal node.
When required use alphabetical order to break ties.
[[IMAGE:906f4e4af6984c56_4_7]]
When we say a node is inspected/expanded/refined it means: the node is picked up from OPEN,
and goal test is called, if goal test fails then MoveGen is called and, depending on the algorithm,
the neighbours are selectively placed in OPEN.
Assume that the RemoveSeen procedure will drop the neighbours that are already present in the
OPEN or CLOSED list.
Based on the above data, answer the given subquestions.
What is the path found by Depth First Search?
Enter the path as a comma separated list of node labels.
Enter NIL if a path to goal is not found.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: S,X,Y,G**
A published solution is not available for this question yet.
Question 124 SHORT_TEXT · 1.0 marks
**SEARCH**
The MoveGen function and the heuristic function for a state space is provided below. Take S as the
start node and G as the goal node.
When required use alphabetical order to break ties.
[[IMAGE:906f4e4af6984c56_4_7]]
When we say a node is inspected/expanded/refined it means: the node is picked up from OPEN,
and goal test is called, if goal test fails then MoveGen is called and, depending on the algorithm,
the neighbours are selectively placed in OPEN.
Assume that the RemoveSeen procedure will drop the neighbours that are already present in the
OPEN or CLOSED list.
Based on the above data, answer the given subquestions.
List the first 4 nodes inspected by **Breadth First Search.** List the nodes in the order they are
inspected. If the algorithm terminates early then list the nodes inspected up until termination.
Enter a comma separated list of node labels.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: S,X,Y,Z**
A published solution is not available for this question yet.
Question 125 SHORT_TEXT · 1.0 marks
**SEARCH**
The MoveGen function and the heuristic function for a state space is provided below. Take S as the
start node and G as the goal node.
When required use alphabetical order to break ties.
[[IMAGE:906f4e4af6984c56_4_7]]
When we say a node is inspected/expanded/refined it means: the node is picked up from OPEN,
and goal test is called, if goal test fails then MoveGen is called and, depending on the algorithm,
the neighbours are selectively placed in OPEN.
Assume that the RemoveSeen procedure will drop the neighbours that are already present in the
OPEN or CLOSED list.
Based on the above data, answer the given subquestions.
What is the path found by Breadth First Search?
Enter the path as a comma separated list of node labels.
Enter NIL if a path to goal is not found.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: S,X,Y,G**
A published solution is not available for this question yet.
Question 126 SHORT_TEXT · 1.0 marks
**SEARCH**
The MoveGen function and the heuristic function for a state space is provided below. Take S as the
start node and G as the goal node.
When required use alphabetical order to break ties.
[[IMAGE:906f4e4af6984c56_4_7]]
When we say a node is inspected/expanded/refined it means: the node is picked up from OPEN,
and goal test is called, if goal test fails then MoveGen is called and, depending on the algorithm,
the neighbours are selectively placed in OPEN.
Assume that the RemoveSeen procedure will drop the neighbours that are already present in the
OPEN or CLOSED list.
Based on the above data, answer the given subquestions.
List the first 4 nodes inspected by **Best First Search.** List the nodes in the order they are
inspected. If the algorithm terminates early then list the nodes inspected up until termination.
Enter a comma separated list of node labels.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: S,X,Y,Z**
A published solution is not available for this question yet.
Question 127 SHORT_TEXT · 1.0 marks
**SEARCH**
The MoveGen function and the heuristic function for a state space is provided below. Take S as the
start node and G as the goal node.
When required use alphabetical order to break ties.
[[IMAGE:906f4e4af6984c56_4_7]]
When we say a node is inspected/expanded/refined it means: the node is picked up from OPEN,
and goal test is called, if goal test fails then MoveGen is called and, depending on the algorithm,
the neighbours are selectively placed in OPEN.
Assume that the RemoveSeen procedure will drop the neighbours that are already present in the
OPEN or CLOSED list.
Based on the above data, answer the given subquestions.
What is the path found by Best First Search?
Enter the path as a comma separated list of node labels.
Enter NIL if a path to goal is not found.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: S,X,Y,G**
A published solution is not available for this question yet.
Question 128 SHORT_TEXT · 1.0 marks
**SEARCH**
The MoveGen function and the heuristic function for a state space is provided below. Take S as the
start node and G as the goal node.
When required use alphabetical order to break ties.
[[IMAGE:906f4e4af6984c56_4_7]]
When we say a node is inspected/expanded/refined it means: the node is picked up from OPEN,
and goal test is called, if goal test fails then MoveGen is called and, depending on the algorithm,
the neighbours are selectively placed in OPEN.
Assume that the RemoveSeen procedure will drop the neighbours that are already present in the
OPEN or CLOSED list.
Based on the above data, answer the given subquestions.
List the first 4 nodes inspected by Hill Climbing. List the nodes in the order they are inspected. If
the algorithm terminates early then list the nodes inspected up until termination.
Enter a comma separated list of node labels.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: S,X,Y,Z**
A published solution is not available for this question yet.
Question 129 SHORT_TEXT · 1.0 marks
**SEARCH**
The MoveGen function and the heuristic function for a state space is provided below. Take S as the
start node and G as the goal node.
When required use alphabetical order to break ties.
[[IMAGE:906f4e4af6984c56_4_7]]
When we say a node is inspected/expanded/refined it means: the node is picked up from OPEN,
and goal test is called, if goal test fails then MoveGen is called and, depending on the algorithm,
the neighbours are selectively placed in OPEN.
Assume that the RemoveSeen procedure will drop the neighbours that are already present in the
OPEN or CLOSED list.
Based on the above data, answer the given subquestions.
What is the path found by Hill Climbing?
Enter the path as a comma separated list of node labels.
Enter NIL if a path to goal is not found.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: S,X,Y,G**
A published solution is not available for this question yet.
Question 130 MCQ · 1.0 marks
**Genetic Algorithm**
Answer the given subquestions.
Convert the path representation A,C,K,F,B,H,G,I,D,L,E,J to ordinal representation. Use A,B,C,...,L as
the reference (index) sequence.
1,2,9,4,1,4,3,3,1,3,1,1
9,4,10,4,2,1,1,5,3,3,1,1
1,2,9,8,1,3,3,4,1,3,1,1
3,10,8,3,2,2,5,1,3,3,2,1
A published solution is not available for this question yet.
Question 131 MSQ · 1.0 marks
**Genetic Algorithm**
Answer the given subquestions.
Path representations of two tours are given below. Generate offspring using Cycle Crossover.
**P1:** I,D,L,E,J,A,C,K,F,B,H,G
**P2:** C,K,I,D,B,E,J,A,H,L,G,F
Select the child tours.
I,K,L,D,J,E,C,A,F,B,H,G
C,D,I,E,B,A,J,K,H,L,G,F
I,D,L,K,B,A,E,H,C,J,F,G
A,L,I,E,J,D,C,K,H,F,G,B
A published solution is not available for this question yet.
Question 132 MCQ · 1.0 marks
**Genetic Algorithm**
Answer the given subquestions.
Single-point crossover can be used with __________ .
Adjacency Representation.
Path Representation
Ordinal Representation
All of these
A published solution is not available for this question yet.
Question 133 NAT · 1.0 marks
**Genetic Algorithm**
Answer the given subquestions.
For the case of 3-edge exchange, how many child tours are possible? Enter the number of child
tours in the text box. (Assume that no pair of edges from the selected 3 edges share any city in
common.)
Enter an integer.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: 17**
A published solution is not available for this question yet.
Question 134 SHORT_TEXT · 1.0 marks
**TSP**
Use the distance matrix to construct TSP tours.
[[IMAGE:906f4e4af6984c56_10_8]]
Based on the above data, answer the given subquestions.
Use “A” as the starting city, construct a tour using Nearest Neighbour Heuristic. The tour is
__________ . Enter the path representation of the tour, starting from “A” and tracing the cities as
selected by the Nearest Neighbour Heuristic.
Enter a comma separated list of city names.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer format: A,X,Y,Z
A published solution is not available for this question yet.
Question 135 SHORT_TEXT · 1.0 marks
**TSP**
Use the distance matrix to construct TSP tours.
[[IMAGE:906f4e4af6984c56_10_8]]
Based on the above data, answer the given subquestions.
Use “A” as the fulcrum (base) node and use Savings Heuristic to construct the TSP tour. Identify the
new edge added in the first merge operation. Enter the new edge and its savings.
Enter an edge XY and an integer as a comma separated list.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer format: XY,17
A published solution is not available for this question yet.
Question 136 SHORT_TEXT · 1.0 marks
**TSP**
Use the distance matrix to construct TSP tours.
[[IMAGE:906f4e4af6984c56_10_8]]
Based on the above data, answer the given subquestions.
Use “A” as the fulcrum (base) node and use Savings Heuristic to construct the TSP tour. Enter the
path representation of the Savings tour, starting from “A”.
Enter a comma separated list of city names.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer format: A,X,Y,Z
A published solution is not available for this question yet.
Question 137 NAT · 1.0 marks
**TSP**
Use the distance matrix to construct TSP tours.
[[IMAGE:906f4e4af6984c56_10_8]]
Based on the above data, answer the given subquestions.
What is the cost of the tour generated by Savings Heuristic?
A published solution is not available for this question yet.