This page contains the reliably extracted subset, not the complete original paper.
Questions and published explanations below are available without starting a test. Some questions may not have a published solution yet.
20 / 21 published solutions
Question 38 MSQ · 0.0 marks
6406533822364.
Printed graph sheets were provided on time.
6406533822365.
Printed graph sheets were provided late.
6406533822366.
Printed graph sheets were not provided.
6406533822367.
I used the graph sheets.
6406533822368.
I did not use graph sheets.
Published solution
**1. Interpret the zero-mark item:** The prompt asks about printed graph-sheet availability and usage. Its supplied key selects “provided on time” and “used”; these are administrative reports rather than mathematical conclusions.
**Answer: A, D — A and D — supplied administrative responses.**
**Convention note:** The retained selections are not evidence about an individual candidate’s actual experience.
A: **Correct:** The source key records timely provision.
B: **Incorrect:** The key does not record late provision.
C: **Incorrect:** The key records provision, rather than non-provision.
D: **Correct:** The source key records use of the graph sheets.
E: **Incorrect:** This contradicts the keyed usage report.
**STATE SPACE**
Select the algorithms that find the shortest path (measured in number of hops).
6406533822369.
Breadth-First Search
6406533822370.
Best-First Search
6406533822371.
Depth-First Search
6406533822372.
DFID-N (opens only new nodes)
6406533822373.
DFID-C (reopens closed nodes)
6406533822374.
Hill Climbing
Published solution
**1. Use level order for minimum hops:** BFS inspects every shallower depth before a deeper one, so its first discovered goal depth is shortest when each edge counts as one hop.
**2. Handle repeated states in iterative deepening:** A state first reached on a deep branch can have too little remaining depth budget. DFID-C permits closed states to be reopened when needed at a shallower arrival, preserving the depth-limit search’s reachability guarantee.
**3. Exclude the other methods:** Greedy best-first and hill climbing use heuristic values rather than depth; DFS can return a longer branch. A new-nodes-only depth-limited search can incorrectly prune a shallower revisit.
**Answer: A, E — A and E.**
**Convention note:** This uses the course’s DFID-N/DFID-C duplicate-handling definitions, with each iterative-deepening pass reset appropriately. Tree-search iterative deepening with path-cycle checking is also minimum-depth, but that is not the new-nodes-only graph variant listed here.
A: **Correct:** FIFO level expansion guarantees minimum-hop depth.
B: **Incorrect:** A low heuristic value does not guarantee the shortest path.
C: **Incorrect:** DFS can find a deeper goal before a shallower one.
D: **Incorrect:** Suppressing all repeated states can lose shallower routes within a depth limit.
E: **Correct:** The reopening variant preserves the intended iterative-deepening shortest-hop guarantee.
F: **Incorrect:** It can become trapped or take a longer improving route.
There is at least one move that is not reversible.
6406533822381.
There is a path from every state to every other state.
6406533822382.
Every state has two neighbours.
Published solution
**1. Check reversibility:** Every move XORs a fixed neighbour mask. Applying the same mask again restores the original board, so all moves are reversible.
**2. Build the reachable graph:** The two distinct masks generate boards 00/00,01/10,10/01,11/11. At every board, either mask gives a different neighbour, producing a connected four-cycle.
**3. Count neighbours:** Four touch locations occur in two equivalent pairs, so there are two distinct successor states, not four.
**Answer: A, C, D — A, C and D.**
A: **Correct:** Applying the same touch twice undoes the move.
B: **Incorrect:** Every move is its own inverse.
C: **Correct:** All four states lie on the same connected cycle.
D: **Correct:** Each state has two distinct mask-generated neighbours.
**SEARCH**
The figure shows a map with several locations on a grid where each tile is 1x1 in size.
The locations are at grid points and are connected by two-way edges.
Take S as the start node and G as the goal node.
The MoveGen function returns neighbours in alphabetical order.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
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.
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 were
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**
Published solution
**1. Apply the search rule:** Use a stack with the alphabetically first new successor at the front. RemoveSeen drops successors already in OPEN or CLOSED, so their existing parents are retained.
**2. Track OPEN after expansions:** After S, new=B,D,E and OPEN=B,D,E; After B, new=A,C and OPEN=A,C,D,E; After A, new=NIL and OPEN=C,D,E.
**3. Read the inspected order:** The first removals from OPEN, including a goal if reached, are S,B,A,C.
**Answer: S,B,A,C.**
**SEARCH**
The figure shows a map with several locations on a grid where each tile is 1x1 in size.
The locations are at grid points and are connected by two-way edges.
Take S as the start node and G as the goal node.
The MoveGen function returns neighbours in alphabetical order.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
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.
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 there is no path.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: S,X,Y,G**
Published solution
**1. Apply the search rule:** Use a stack with the alphabetically first new successor at the front. RemoveSeen drops successors already in OPEN or CLOSED, so their existing parents are retained.
**2. Run the frontier to the goal:** The inspected sequence is S → B → A → C → F → G.
**3. Reconstruct from parents:** Follow the goal’s first-discovery parents backward, then reverse them: S → B → C → F → G. This parent chain is the returned path; expanded dead ends need not belong to it.
**Answer: S,B,C,F,G.**
**Convention note:** A is inspected as a dead end because C was already in OPEN with parent B. Thus A appears in the expansion order but not in the returned path S,B,C,F,G.
**SEARCH**
The figure shows a map with several locations on a grid where each tile is 1x1 in size.
The locations are at grid points and are connected by two-way edges.
Take S as the start node and G as the goal node.
The MoveGen function returns neighbours in alphabetical order.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
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.
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 were
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**
Published solution
**1. Apply the search rule:** Use a FIFO queue: append unseen successors in alphabetical order. RemoveSeen preserves the first-discovery parent, so the resulting goal path has the fewest moves.
**2. Track OPEN after expansions:** After S, new=B,D,E and OPEN=B,D,E; After B, new=A,C and OPEN=D,E,A,C; After D, new=H and OPEN=E,A,C,H.
**3. Read the inspected order:** The first removals from OPEN, including a goal if reached, are S,B,D,E.
**Answer: S,B,D,E.**
**SEARCH**
The figure shows a map with several locations on a grid where each tile is 1x1 in size.
The locations are at grid points and are connected by two-way edges.
Take S as the start node and G as the goal node.
The MoveGen function returns neighbours in alphabetical order.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
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.
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 there is no path.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: S,X,Y,G**
Published solution
**1. Apply the search rule:** Use a FIFO queue: append unseen successors in alphabetical order. RemoveSeen preserves the first-discovery parent, so the resulting goal path has the fewest moves.
**2. Run the frontier to the goal:** The inspected sequence is S → B → D → E → A → C → H → I → F → G.
**3. Reconstruct from parents:** Follow the goal’s first-discovery parents backward, then reverse them: S → E → I → G. This parent chain is the returned path; expanded dead ends need not belong to it.
**Answer: S,E,I,G.**
**SEARCH**
The figure shows a map with several locations on a grid where each tile is 1x1 in size.
The locations are at grid points and are connected by two-way edges.
Take S as the start node and G as the goal node.
The MoveGen function returns neighbours in alphabetical order.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
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.
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 were
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**
Published solution
**1. Apply the search rule:** Choose the smallest h from all of OPEN, breaking equal scores alphabetically. This is greedy best-first search, not a search restricted to the current node’s children.
**2. Track OPEN after expansions:** After S, new=B,D,E and OPEN=B,D,E; After D, new=C,H and OPEN=E,B,C,H; After H, new=F,I and OPEN=C,E,B,F,I.
**3. Read the inspected order:** The first removals from OPEN, including a goal if reached, are S,D,H,F.
**Answer: S,D,H,F.**
**SEARCH**
The figure shows a map with several locations on a grid where each tile is 1x1 in size.
The locations are at grid points and are connected by two-way edges.
Take S as the start node and G as the goal node.
The MoveGen function returns neighbours in alphabetical order.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
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.
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 there is no path.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: S,X,Y,G**
Published solution
**1. Apply the search rule:** Choose the smallest h from all of OPEN, breaking equal scores alphabetically. This is greedy best-first search, not a search restricted to the current node’s children.
**2. Run the frontier to the goal:** The inspected sequence is S (h=10) → D (h=6) → H (h=2) → F (h=3) → G (h=0).
**3. Reconstruct from parents:** Follow the goal’s first-discovery parents backward, then reverse them: S → D → H → F → G. This parent chain is the returned path; expanded dead ends need not belong to it.
**Answer: S,D,H,F,G.**
**SEARCH**
The figure shows a map with several locations on a grid where each tile is 1x1 in size.
The locations are at grid points and are connected by two-way edges.
Take S as the start node and G as the goal node.
The MoveGen function returns neighbours in alphabetical order.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
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.
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 were 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**
Published solution
**1. Apply the search rule:** Choose a strictly lower-h neighbour, breaking ties alphabetically. Hill climbing keeps no alternative frontier for later backtracking.
**2. Follow improving moves:** S (h=10) → D (h=6) → H (h=2).
**3. Test the stopping point:** At H, neighbours are C (h=6), D (h=6), F (h=3), I (h=4). No strictly improving move remains, and this state is not the goal G. The algorithm therefore stops without a goal path.
**Answer: S,D,H.**
**SEARCH**
The figure shows a map with several locations on a grid where each tile is 1x1 in size.
The locations are at grid points and are connected by two-way edges.
Take S as the start node and G as the goal node.
The MoveGen function returns neighbours in alphabetical order.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
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.
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 there is no path.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: S,X,Y,G**
Published solution
**1. Apply the search rule:** Choose a strictly lower-h neighbour, breaking ties alphabetically. Hill climbing keeps no alternative frontier for later backtracking.
**2. Follow improving moves:** S (h=10) → D (h=6) → H (h=2).
**3. Test the stopping point:** At H, neighbours are C (h=6), D (h=6), F (h=3), I (h=4). No strictly improving move remains, and this state is not the goal G. The algorithm therefore stops without a goal path.
**Answer: NIL.**
**Genetic Algorithm**
A tour of 10 cities is shown below. The edges are bi-directional. Use **D, E, F,..., M** as the reference
(index) sequence to prepare tour representations.
Based on the above data, answer the given subquestions.
Select the valid path representations of the tour.
6406533822391.
J, G, F, I, L, M, E, D, H, K
6406533822392.
J, G, F, I, L, M, E, D, H, K, J
6406533822393.
M, E, D, H, K, J, G, F, I, L
6406533822394.
M, E, D, H, K, J, G, F, I, L, M
Published solution
**1. Use the path-encoding convention:** A ten-city chromosome lists each city exactly once, with the edge from the last city back to the first implicit.
**2. Trace the drawn cycle:** J→G→F→I→L→M→E→D→H→K→J follows all drawn edges. Starting at M instead merely rotates that same cycle, so A and C are valid ten-entry representations.
**Answer: A, C — A and C.**
**Convention note:** A closed-walk notation may repeat the start, but the tour path representation used in this genetic-algorithm question is an n-entry permutation.
A: **Correct:** It lists each city once and follows the drawn cycle.
B: **Incorrect:** It repeats J as an eleventh entry, contrary to the chromosome convention.
C: **Correct:** It rotates the same cycle to start at M.
D: **Incorrect:** It repeats M as an eleventh entry, contrary to the chromosome convention.
**Genetic Algorithm**
A tour of 10 cities is shown below. The edges are bi-directional. Use **D, E, F,..., M** as the reference
(index) sequence to prepare tour representations.
Based on the above data, answer the given subquestions.
Select the valid adjacency representations of the tour.
6406533822395.
F, D, I, M, K, L, G, J, H, E
6406533822396.
H, D, I, F, K, L, G, J, M, E
6406533822397.
E, M, D, J, L, F, K, H, I, G
6406533822398.
E, M, G, J, D, F, K, H, I, L
Published solution
**1. Use the fixed reference order:** For D,E,F,G,H,I,J,K,L,M, each adjacency-list entry names that reference city’s successor.
**2. Encode one traversal:** For D→H→K→J→G→F→I→L→M→E→D, the successors in reference order are H,D,I,F,K,L,G,J,M,E, which is B.
**3. Reverse the traversal:** Its successor list becomes E,M,G,J,D,F,K,H,I,L, which is D. Both encode the same bidirectional cycle.
**Answer: B, D — B and D.**
A: **Incorrect:** Its first entry gives D→F, an edge absent from the displayed tour.
B: **Correct:** It encodes the stated traversal in reference-city order.
C: **Incorrect:** Its third entry gives F→D, an edge absent from the displayed tour.
D: **Correct:** It encodes the reverse traversal in reference-city order.
**Genetic Algorithm**
A tour of 10 cities is shown below. The edges are bi-directional. Use **D, E, F,..., M** as the reference
(index) sequence to prepare tour representations.
Based on the above data, answer the given subquestions.
Convert the path representation **I, L, G, D, F, H, J, E, K, M** to ordinal representation.
6406533822399.
7, 4, 3, 4, 5, 5, 2, 1, 1, 1
6406533822400.
6, 8, 4, 1, 2, 2, 2, 1, 1, 1
6406533822401.
6, 4, 8, 2, 1, 5, 2, 1, 1, 1
6406533822402.
7, 3, 6, 4, 2, 3, 3, 3, 2, 1
Published solution
**1. Use one-based ranks in the shrinking D…M list:** Record the current position of each selected city and delete it before locating the next.
**2. Compute the deletions:** I is 6 in DEFGHIJKLM; L is 8 in DEFGHJKLM; G is 4 in DEFGHJKM; D is 1 in DEFHJKM; F is 2 in EFHJKM; H is 2 in EHJKM; J is 2 in EJKM; E is 1 in EKM; K is 1 in KM; M is 1 in M.
**3. Collect the code:** 6,8,4,1,2,2,2,1,1,1.
**Answer: B — 6,8,4,1,2,2,2,1,1,1.**
A: **Incorrect:** Its first rank 7 selects J rather than I.
B: **Correct:** It matches the full shrinking-list calculation.
C: **Incorrect:** After removing I, L has rank 8, not 4.
D: **Incorrect:** Its first rank 7 selects J rather than I.
**Genetic Algorithm**
A tour of 10 cities is shown below. The edges are bi-directional. Use **D, E, F,..., M** as the reference
(index) sequence to prepare tour representations.
Based on the above data, answer the given subquestions.
Two tours in path representation are given below. Generate offspring using Cycle Crossover.
Enter one of the child tours in the textbox.
Enter a comma separated list of cities.
DO NOT ENTER SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Published solution
**1. Determine the crossover cycles:** With P1=J,G,F,I,L,M,E,D,H,K and P2=I,L,G,D,F,H,J,E,K,M, the one-based position cycles are (1,4,8,7), (2,5,3), and (6,9,10).
**2. Alternate cycle inheritance:** Take cycles 1 and 3 from P1 and cycle 2 from P2. This yields J,L,G,I,F,M,E,D,H,K.
**3. Check the complementary child:** Reversing parent sources gives I,G,F,D,L,H,J,E,K,M. Either child is accepted; the answer supplies the first.
**Answer: J,L,G,I,F,M,E,D,H,K.**
**TSP**
The distance matrix for 5 cities and corresponding edge costs (in ascending order) is provided
below. Use this information to construct TSP tours.
Based on the above data, answer the given subquestions.
Start from city C and construct a tour using Nearest Neighbour Heuristic. Enter the path
representation of the tour starting from city C. Use the same order in which cities were added to
the tour.
Enter a comma separated list of city names.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer format: C,X,Y,Z**
Published solution
**1. Select the closest unvisited city at each step:** C: A=92, B=20, D=28, E=53; choose B; B: A=58, D=46, E=70; choose D; D: A=34, E=12; choose E; E: A=81; choose A.
**2. Close the tour:** Return from A to C at cost 92. The path representation lists each city once; this return is implicit.
**Answer: C,B,D,E,A.**
**TSP**
The distance matrix for 5 cities and corresponding edge costs (in ascending order) is provided
below. Use this information to construct TSP tours.
Based on the above data, answer the given subquestions.
What is the cost of the tour generated by Nearest Neighbour Heuristic?
Enter a number.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer format: 17**
Published solution
**1. Select the closest unvisited city at each step:** C: A=92, B=20, D=28, E=53; choose B; B: A=58, D=46, E=70; choose D; D: A=34, E=12; choose E; E: A=81; choose A.
**2. Close the tour:** Return from A to C at cost 92. The path representation lists each city once; this return is implicit.
**3. Add every edge, including the return:** 20+46+12+81+92=251.
**Answer: 251.**
**TSP**
The distance matrix for 5 cities and corresponding edge costs (in ascending order) is provided
below. Use this information to construct TSP tours.
Based on the above data, answer the given subquestions.
Construct a tour using Greedy Heuristic. Enter the path representation of the tour starting from
city C.
Enter a comma separated list of city names.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer format: C,X,Y,Z**
Published solution
**1. Use sorted edges with feasibility checks:** Accept an edge only if no city’s degree exceeds 2 and no cycle forms before all cities can be included.
**2. Process the edge list:** DE (12): accept; BC (20): accept; CD (28): accept; AD (34): skip, degree limit; BD (46): skip, degree limit; CE (53): skip, degree limit; AB (58): accept; BE (70): skip, degree limit; AE (81): accept.
**3. Trace the accepted cycle:** C → B → A → E → D → C. Rotating the starting city or reversing direction represents the same undirected tour.
**Answer: C,B,A,E,D.**
**TSP**
The distance matrix for 5 cities and corresponding edge costs (in ascending order) is provided
below. Use this information to construct TSP tours.
Based on the above data, answer the given subquestions.
What is the cost of the tour generated by Greedy Heuristic?
Enter a number.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer format: 17**
Published solution
**1. Use sorted edges with feasibility checks:** Accept an edge only if no city’s degree exceeds 2 and no cycle forms before all cities can be included.
**2. Process the edge list:** DE (12): accept; BC (20): accept; CD (28): accept; AD (34): skip, degree limit; BD (46): skip, degree limit; CE (53): skip, degree limit; AB (58): accept; BE (70): skip, degree limit; AE (81): accept.
**3. Trace the accepted cycle:** C → B → A → E → D → C. Rotating the starting city or reversing direction represents the same undirected tour.
**4. Sum the cycle:** 20+58+81+12+28=199.
**Answer: 199.**
**TSP**
The distance matrix for 5 cities and corresponding edge costs (in ascending order) is provided
below. Use this information to construct TSP tours.
Based on the above data, answer the given subquestions.
Take C as the fulcrum node and compute the **two** missing values in the savings list (full list) given
below. Construct the savings tour. Enter the path representation of the tour starting from city C.
Enter a comma separated list of city names.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer format: C,X,Y,Z**
Published solution
**1. Calculate savings relative to C:** (s(i,j)=d(C,i)+d(C,j)-d(i,j)). The full list is AB=54, AD=86, AE=64, BD=2, BE=3, DE=69.
**2. Merge by descending savings:** AD (86): merge; DE (69): merge; AE (64): skip, premature cycle; AB (54): merge. Merge only different chains at their endpoints, preventing premature cycles and degree greater than 2.
**3. Connect the two remaining chain ends to the base:** The tour is C → B → A → D → E → C. The path representation omits the final repeated base.
**Answer: C,B,A,D,E.**
