Part 4: Uninformed Search
Fundamentals of Artificial Intelligence, KU Leuven, 2025-26. Lecturer: Prof. dr. Mathias Verbeke.
Source deck: FAI_Part4_UninformedSearch_25-26.pdf, 85 PDF pages. Transcript coverage: T2 (deck pp.1 to 67) and T3 (deck pp.68 to 85).
Printed copy: all hidden answers are revealed. Do the task before you read down the page.
What this chapter assumes
- The five ingredients of a search problem (states, actions, initial state, goal formulation, and optionally costs). This chapter never re-derives them; it assumes you can already write them down for a new problem. See Part 3. The deck restates them on p.3 before starting.
- That a bad state representation makes the search space explode. Part 3's water-jug example is the one where naive states let the agent pour back and forth forever; that loop is exactly the problem GENERIC-SEARCH on p.27 fixes. See Part 3.
- The task-environment vocabulary. The summary slide p.81 opens with "Assume known, discrete, observable, deterministic, atomic environment". Every algorithm here silently depends on those five words. See Part 2.
dependent on how you defined each of these aspects, how you formulated the problem, the problem will be easier or will be harder to solve. And that's something very important to realize.(Lecturer, T1, restated in T2). This is why Part 3 is a prerequisite and not a warm-up.
Two separate skills, and the exam tests both in different halves: reason about the four properties (theory exam, closed book) and execute the algorithm by hand writing the frontier (exercise exam, open book). Part 4 is one of the two chapters where hand-execution speed decides your mark.
1. State space graphs versus search trees (pp.4 to 8)
A state space graph is a mathematical picture of the whole problem: nodes are abstracted world configurations, arcs are successors labelled with the action that produces them, and the goal test is a set of goal nodes. The property that matters, printed in colour on both p.5 and p.6, is: in a state space graph each state occurs only once. It is a picture of the world, not of the search.
The bullet list contains one thing you rarely can do and one thing you often must do. Name both, and say which of the five ingredients from Part 3 decides how bad the first one is.
Show answer
One bullet on this slide is false about the object drawn on p.8. Which one, and what replaces it?
Show answer
Slide p.7 fixes the vocabulary that the rest of the course reuses: a directed graph is a set of nodes plus a set of ordered pairs called arcs; n2 is a neighbour of n1 if the arc (n1, n2) exists; a path is a sequence of nodes in which consecutive pairs are arcs; the length of the path n0 to nk is k (the number of arcs, not the number of nodes); and when arcs carry costs, the cost of a path is the sum of its arc costs. The lecturer stresses the word "neighbour": in a graph you do not say "child node", because there is no descendant structure. Child nodes exist only in the search tree.
In the right-hand tree, point at the node labelled d just under the root. What object is it, precisely? And the tree contains two nodes labelled a in the third row: what is the difference between them?
Show answer
Constructed, in the sample paper's format (2023 theory exam, part 1, true or false)
In a search tree, each state of the state space graph occurs only once.
it's very important to realize that in this type of problem a note in this tree actually represents an entire path um you took from the starting node.(Lecturer, T2). He says it while pointing at p.8, and he repeats it when the frontier appears. Every downstream mistake in this Part comes from forgetting it.
2. TREE-SEARCH, the algorithm everything else extends (pp.9 to 26)
Slides pp.9 to 24 are one long animation of a single algorithm on a four-state graph. The pseudocode never changes; only the variable values do. Here it is as printed on p.9:
function TREE-SEARCH(problem) # return a solution or failure
start-node := MAKE-NODE(problem.INITIAL-STATE())
frontier := set consisting of start-node
while not IS-EMPTY(frontier) do:
node := select and remove an element from frontier
if problem.IS-GOAL(node.STATE) then
return node
for child-state in problem.NEIGHBORS(node.STATE) do:
child-node := MAKE-NODE(child-state, node)
frontier := INSERT(child-node, frontier)
return FAILUREFour things in this listing carry the whole chapter:
MAKE-NODE(child-state, node)takes the parent node as its second argument. That is how a node ends up being a path: the child node is the parent path extended by one state. On p.10 the deck writes it out:start-node = <S>, "sequence with one element: S".node.STATEis the last state of the path. The goal test is applied to that last state only.- The goal test happens when a node is removed from the frontier, not when it is generated. This is the late goal test, and it is the reason UCS works at all (Section 10).
select and remove an element from frontieris deliberately vague. That one line is the only difference between depth-first, breadth-first, iterative deepening and uniform cost search.
Exactly one line of this pseudocode is different in DFS, BFS, iterative deepening (ID) and UCS. Which line, and what does each of the four algorithms put in its place?
Show answer
node := select and remove an element from frontier. DFS makes it last in, first out (a stack). BFS makes it first in, first out (a queue). UCS makes it remove the path with the smallest g (a priority queue). Iterative deepening keeps DFS's rule and adds an outer loop over a depth limit. The lecturer puts it the same way in the lecture: the difference between the algorithms boils down entirely to the behaviour of the pop operation.
Constructed, in the sample paper's format (2023 theory exam, part 1, true or false)
In TREE-SEARCH, a node is tested against the goal at the moment it is generated and inserted into the frontier.
node := select and remove an element from frontier, so it is applied to the node removed from the frontier. The children are inserted untested. True describes the early goal check, which this deck uses only in the depth-limited pseudocode on p.66, and which the exercise session 2 solutions restrict by name: "it's only applicable to DFS and BFS, and not algorithms that involve costs (like UCS) or heuristics (like A*)". Answering True is also the habit that makes you stop a UCS or A* trace one expansion too early, which is worth more lost marks in the exercise exam than this half point. Marking: +0.5 / -0.25 / 0.The animation on pp.10 to 24 is worth stepping through once by hand. Its own trace, in the deck's notation, is: frontier = {<S>}, pop <S>, not a goal, expand to <S,a> and <S,b>, giving {<S,a>, <S,b>}; pop <S,a>, not a goal, expand to <S,a,b> and <S,a,G>; and so on. Note that the deck writes frontier as a mathematical set, which is why the ordering question is left open until p.42.
The graph has four states with neighbours S → {a, b}, a → {b, G}, b → {a, G}. Run plain TREE-SEARCH with a last in, first out frontier and write the first five paths that get popped. Then say in one sentence why the search tree is infinite even though the graph has four nodes.
Show answer
3. GENERIC-SEARCH: loop breaking is one extra set (p.27)
The fix is three added lines. GENERIC-SEARCH keeps a set called reached, containing states (not paths), and refuses to expand a node whose last state has been reached before.
function GENERIC-SEARCH(problem) # return a solution or failure
start-node := MAKE-NODE(problem.INITIAL-STATE())
frontier := set consisting of start-node
reached := an empty set
while not IS-EMPTY(frontier) do:
node := select and remove an element from frontier
if problem.IS-GOAL(node.STATE) then
return node
if node.STATE not in reached then
add node.STATE to reached
for child-state in problem.NEIGHBORS(node.STATE) do:
child-node := MAKE-NODE(child-state, node)
frontier := INSERT(child-node, frontier)
return FAILUREThree details that the exam can turn into a question:
- The
reachedtest is after the goal test. A node whose state was already reached is still goal-tested before being discarded. - The test happens at pop time, not at insert time. Redundant children are generated and do sit on the frontier for a while; they are simply never expanded. You will see this on the Romania frames in Section 4.
reachedholds states, so it costs memory proportional to the number of distinct states, not to the number of paths.
Run GENERIC-SEARCH with a last in, first out frontier on the same four-state graph (S → {a, b}, a → {b, G}, b → {a, G}). Which path is returned? Is it the path with the fewest arcs?
Show answer
in the project this is also referred to as graph search because it works on any graph while the algorithm that we saw previously uh only works on uh on trees.(Lecturer, T2, on p.27; this is also printed on the slide). "Generic search" in this course, "graph search" in the Pacman project and in Russell and Norvig, are the same algorithm. If an exam question says "graph search", it means the version with the reached set.
There are two ways to break loops, and the 2025-26 exercise session 2 solutions spell out both on their slides 8 and 9:
- Approach 1, global state history: exactly the
reachedset of p.27. It "will eliminate all duplicate states across the search tree". - Approach 2, per-branch state history: only removes duplicates "within each respective branch", that is, a path may not revisit a state that already occurs on itself.
The exercise-session solutions then say: "The following slides employ approach 2." The lecture deck's GENERIC-SEARCH uses approach 1. The solutions also give the cost of approach 1: "DFS using approach 1 as loop detection will sacrifice its O(b.m) memory complexity into O(V)", where V is the state-space size.
Classic mistake (archetype A2): silently mixing the two, so that some frontier lines look global and others per-branch. Pick one, write one line saying which you picked, and be consistent. Either is accepted; an unstated mixture is not.
Exercise session 2 (2025-26), exercise 1, task line verbatim
Farmer, fox, goose and grain, in the state representation built in session 1: states are [L|R], start [Fa Fo Go Gr|], goal [|Fa Fo Go Gr], and no (Fo, Go) or (Go, Gr) may sit on a bank without the farmer.
"Use this representation to solve this problem using the following algorithms. Assume tree search with loop detection is used. Perform depth-first search. Explicitly write down the frontier at each iteration of the algorithm. Perform breadth-first search. Write down the search tree."
Show the model approach
- The start has exactly one legal successor. Taking nobody leaves the fox with the goose; taking the fox leaves the goose with the grain; taking the grain leaves the fox with the goose. Only "farmer takes the goose" survives, so the first frontier after the root holds a single path. Illegal states are not generated at all, they are excluded by the transition rules, not filtered afterwards.
- Loop detection does visible work at the second expansion. Expanding <...[Fo Gr|Fa Go]> generates two children: rule R2 gives [Fa Fo Gr|Go] and rule R4 gives [Fa Fo Go Gr|], which is the start state again. Only the first enters Q2. Note where the deck kills the second one: at generation. GENERIC-SEARCH on p.27 kills it later, at pop time. Both are accepted, an unstated mixture is not.
- Say which scope you used. These solution slides use approach 2, per branch (their slide 9: "The following slides employ approach 2"). Writing "loop breaking per branch" as your first line costs four words and covers the second of the four mark-losers listed in Section 11.
4. Romania and systematic search: watching the frontier move (pp.28 to 34)
The Romania frames replay GENERIC-SEARCH on the map from Part 3, with the search tree drawn and the frontier and explored sets shaded.
Name the node that moved from frontier to explored, list the paths that entered the frontier, and answer this: does the child <Arad, Sibiu, Arad> get generated at all?
Show answer
Yes, <Arad, Sibiu, Arad> is generated and does sit on the frontier, drawn on the slide. The lecturer confirms this in the lecture: the path back to Arad is added to the frontier, and only when it is later selected does the loop-breaking check notice that Arad has already been reached and refuse to continue that path. The reached test kills it when it is popped, not when it is created.
The slide states two properties. Suppose you expanded a frontier node, moved it into explored, and forgot to add its unexplored neighbours. Which of the two properties breaks, and what would the picture look like?
Show answer
Slide p.34 names the four concepts you will use in every trace: node expansion (generating all successor nodes for the available actions), explored nodes (already expanded), frontier (all nodes available for expansion, also called the fringe in some textbooks and on several of these slides), and search strategy (defines which node is expanded next).
5. Depth-first search (pp.35 to 47)
The strategy and its data structure
Strategy: expand a deepest node first. Implementation: the frontier is a LIFO stack. Those two are the same statement, because the children just generated are the deepest paths in existence, and pushing them to the front of the frontier guarantees one of them is popped next.
The slide gives a strategy ("expand a deepest node first") and an implementation ("frontier is a LIFO stack") without proving they agree. Give the one-sentence argument. Then say what the label "DAG!" on this slide is warning you about.
Show answer
"DAG!" flags that this particular example graph is a directed acyclic graph, so it has no cycles and DFS terminates here without loop breaking. That is a property of the example, not of DFS. On a graph with cycles, DFS without loop breaking does not terminate.
The frontier trace you will be asked to reproduce
Slides pp.37 to 41 animate DFS on a complete binary tree with nodes A (root), B and C, then D, E, F, G, then leaves H, I, J, K, L, M, N, O. The right-hand column is the frontier written as an ordered list of paths, with the angle brackets dropped: <A,B> is written AB.
for simplicity of notation we uh omitted the brackets here. So the paths are shown as a sequence of letters while in principle this should be the notation because it's actually representing a path.(Lecturer, T2, on pp.37 to 42). You may use the short form in the exam, but you must be writing paths. Writing single letters is writing states, which is the mistake below.
The frontier is {ABDH, ABDI, ABE, AC}. Write the frontier after the next pop, and after the pop following that. Then say why two pops in a row shrink the frontier instead of growing it.
Show answer
For reference, the deck's complete printed sequence (all thirteen lines) is:
Constructed, in the exercise exam's format (archetype A2, predict the frontier)
Same tree as the deck's trace (A; then B, C; then D, E, F, G; then leaves H to O), depth-first search, left-to-right. The frontier is {ABD, ABE, AC} and you now pop and expand the first path. Which is the new frontier?
Why the others are the three mistakes that cost marks on 2023 exercise Q1:
B appends the children at the end. That is FIFO, so it is breadth-first search, not depth-first; if you write B you have answered the wrong sub-question.
C writes states instead of paths. The frontier holds paths, which is why the sample theory exam says "select paths from the frontier", and it is the single most common lost mark on this archetype.
D inserts the children right to left, so ABDI would be expanded before ABDH. The rulebook on p.42 fixes the tie the other way: "Convention: we go from left to right", and the exam paper repeats it ("employ the familiar left-to-right order or lexicographic order as tie-breaker").
The frontier is the ordered list [AB, AC, AD] and AB expands into ABX and ABY. Write the new frontier. Then answer: when is AC selected?
Show answer
2023 sample theory exam, part 1 multiple choice, item 1.2, verbatim
Depth-first search follows a Last-In First-Out strategy to select paths from the frontier.
False would require the oldest path to be selected first, which is FIFO, and that is breadth-first search (p.50). Note the word paths in the official wording. The examiner is checking that you know the frontier holds paths, not states.
Marking rule: +0.5 if correct, -0.25 if wrong, 0 if both boxes empty. A true or false item you guess at random has expected value +0.125, so leaving one blank is strictly worse than guessing. Never leave a true or false item blank.
This is the only Part 4 item in the sample theory exam, and each of the eight multiple-choice items comes from a different lecture.
2023 sample exercise exam, question 1 (2 points), sub-question 1; full stem in Section 11
The paper's search space, read off the sheet: S (h = 9) has three arcs, to A (h = 2) at cost 7, to G2 (h = 0) at cost 12, and to G3 (h = 0) at cost 11; A has one arc, to G1 (h = 0) at cost 3. G1, G2 and G3 are all goals. The instruction is "Execute each of the following search algorithms until termination and write down their frontier at every step", with left-to-right or lexicographic tie-breaking. Sub-question 1: Depth-first search.
Show the model answer (verified by execution)
One line is worth adding above your trace: "late goal test, loop breaking per branch". This graph has no cycles, so loop breaking changes nothing, but the sentence costs nothing and it is one of the four things this question is marked on. The goal-test convention does matter here: with the early check of p.66 you would test G2 while expanding S and return <S, G2> at cost 12 instead. Both conventions are defensible for DFS; an unstated one is not.
Note what DFS did to the cost: it returned the cost-10 path, which happens to be the cheapest, purely because A sits leftmost. Move the drawing around and DFS returns something else. It is not optimal, it is left-handed.
Drill this until it is mechanical: viz-uninformed.html runs the same trace step by step with the frontier shown as an ordered list of paths.
Count roughly how many orange nodes exist at any moment, and turn that count into the space complexity formula printed on p.47.
Show answer
Which shaded goal does DFS reach first? Then name the wrong answer that the picture invites, and say why it is wrong.
Show answer
The trap is answering C or A because they are drawn higher up, at depth 3. Depth is irrelevant to DFS: it finds the leftmost solution "regardless of depth or cost" (p.47). Answering C is the correct answer to the breadth-first version of this quiz on p.53, which is exactly why the deck puts the two slides in the same deck.
The four properties, defined once (p.46) and instantiated for DFS (p.47)
Slide p.46 is the definition slide for the whole course. Learn these four words in the deck's own phrasing:
- Complete: "Guaranteed to find a solution if one exists?"
- Optimal: "Guaranteed to find the least cost path?" Note: least cost, not shortest and not "good".
- Time complexity: how many nodes the algorithm expands.
- Space complexity: how large the frontier gets.
The counting picture on the same slide: with branching factor b and maximum depth m, the tree has 1 + b + b2 + ... + bm = (bm+1 - 1)/(b - 1) = O(bm) nodes. The lecturer also states what is deliberately left out of these analyses: the extra time spent avoiding loops, and the space saved by representing paths efficiently (storing a pointer to the parent instead of the full path), are both ignored. The analysis is at the level of orders of magnitude.
Without looking at p.47, complete: DFS time is O(___), space is O(___) from the exact count (___), it is complete only if ___, and it is not optimal because ___.
Show answer
Careful with the summary table on p.82: it lists DFS as not complete, because that table assumes no repeated-state check ("Note: we are not checking for repeated states yet"). p.47 says complete if cycles are prevented. Both are on the slides; quote the assumption when you answer.
6. Breadth-first search (pp.48 to 54)
Strategy: expand a shallowest node first. Implementation: the frontier is a FIFO queue. The only change to the algorithm is that new children go to the end of the frontier instead of the front.
State the invariant that the tier bands express, and then derive from it the exact condition under which BFS is optimal.
Show answer
Consequence: the first goal it pops has the fewest arcs. That equals the least cost path only if every arc costs the same, which is precisely the condition p.54 attaches to optimality and the superscript c on the p.82 summary table ("if step costs are all identical").
![Slide: FIFO explanation in words, select the oldest element from [AB, AC, AD]](assets/part04/23-215e6651.jpg)
Same binary tree as the DFS trace (A; B, C; D, E, F, G; H to O). BFS starts with frontier {A}, which becomes {AB, AC}. Write the next three frontiers, in order, keeping the queue sorted from oldest to youngest.
Show answer
Constructed, in the exercise exam's format (archetype A2, predict the frontier)
Same tree again (A; then B, C; then D, E, F, G; then leaves H to O), breadth-first search, left-to-right. The frontier is {AC, ABD, ABE}, written oldest first, and you now pop and expand the first path. Which is the new frontier?
Why the others are the classic errors:
A puts the new children at the front. That is LIFO, so it is depth-first search wearing a BFS label, and the frontier order it produces is the one you would write for sub-question 1 of the exam paper, not sub-question 2.
B leaves the expanded path AC on the frontier. The pseudocode says "select and remove": a path that has been expanded is gone from the frontier, it lives on only inside its children. Frontiers that keep growing at the head are the visible symptom of this one.
D writes states instead of paths, the same lost mark as in the depth-first item above.
(a) On p.52 the expanded nodes are numbered 1 to 16 and the fringe is shaded. Count the shaded nodes and give their depths. Is the fringe one horizontal band? (b) On p.53, which shaded goal does BFS find first, and how does that differ from the DFS answer on p.44?
Show answer
The general rule to take away: the frontier holds the unexpanded tail of tier k plus the already-generated head of tier k+1. It is a single clean band only at the instant a tier has just been finished. FIFO order is still respected: reading the queue from old to young gives the six depth-4 nodes first (children of 10, then 12, then 14), then the three depth-5 nodes (child of 15, then the two children of 16). This is exactly why p.54 hedges its space bound with the word "roughly": "Has roughly the last tier, so O(bs)".
(b) C. The lecturer's reason: it is the highest goal in the tree and the furthest to the left. Shallowest wins first; left-to-right breaks the tie between C and A, which sit at the same depth. On the identical tree DFS answered D, a much deeper goal. This pair of slides is the cheapest way to remember the difference between the two algorithms.
BFS has time O(bs) and space O(bs). Both are exponential in s, so why does the lecturer call memory, and not time, the bottleneck?
Show answer
it will also find optimal solutions and this assumes that every step you take... costs the same amount.(Lecturer, T2). "BFS is optimal" written without the precondition is a wrong answer. On the exam, write "optimal if all step costs are equal", which is the deck's own superscript c.
2023 sample exercise exam, question 1 (2 points), sub-question 2; full stem in Section 11
The same search space as sub-question 1: S to A at cost 7, to G2 at cost 12, to G3 at cost 11; A to G1 at cost 3; G1, G2, G3 all goals; "write down their frontier at every step", left-to-right or lexicographic tie-break. Sub-question 2: Breadth-first search.
Show the model answer (verified by execution)
The point the examiner can build a follow-up on. BFS returns <S, G2>, one arc, cost 12. DFS returned <S, A, G1>, two arcs, cost 10. The cheapest solution is the one BFS did not find. That is licensed quote 20 (Lecturer, T2) made concrete: BFS finds the fewest-arc solution, and that equals the least-cost solution only when every step costs the same, which is exactly what this graph violates. If a question asks whether BFS is optimal, this three-node graph is your counterexample, and producing a counterexample is what quote 8 (Lecturer, T4) says the theory exam wants.
Same drill companion as before: viz-uninformed.html, which runs DFS and BFS on the same graph side by side so the single differing line is visible.
7. DFS versus BFS: choosing (pp.55 to 61)
Which hill is depth-first and which is breadth-first? Then answer precisely: at the moment drawn, has either robot uncovered a gem, and has either found the yellow one?
Show answer
Neither robot has found the yellow gem, and neither has found the blue one: both still lie in the untouched bottom layer of both hills. The left robot has uncovered no gem at all. Its shaft has gone past a rock, a bolt and a fish bone, and all three gems (blue, yellow, red) are still below its drill head. The right robot, by removing a whole layer, has exposed the red gem, which on the left hill is still buried at the bottom.
That is the trade-off in one picture. DFS has committed enormous depth to a single column and has nothing to show for it, but it is holding almost no memory. BFS has less depth but it cannot miss anything shallower than where it has reached, which is precisely the completeness and optimality argument, paid for by holding a whole layer at once.
These are stills; in the lecture they are animations. Give the two visual signatures that let you name the algorithm from the animation, and give the lecturer's answers for the four runs in order.
Show answer
The lecturer's answers, in order: run 1 BFS, run 2 DFS, run 3 BFS (with walls, the same concentric expansion, now deformed around the obstacles), run 4 DFS. He also makes an important side point about run 2: DFS took a terrible path only because the action order was fixed as up, left, down, right. Had the order started with right, it would have walked almost straight to the goal, but you cannot count on that, because the search space might be laid out any way at all. Action order changes DFS's running time; it changes nothing about DFS's guarantees.
(a) When does BFS outperform DFS, and when the reverse? Answer in terms of s and m. (b) In the table (b = 10, one million nodes per second, one kilobyte per node), what are the time and the memory at depth 10, and which of the two kills you?
Show answer
(b) Depth 10 means 1010 nodes: 3 hours and 10 terabytes. The memory kills you. The slide's conclusion, in orange: "Memory is usually the bottleneck for BFS."
8. Iterative deepening and depth-limited search (pp.62 to 67)
Iterative deepening runs DFS with a depth limit of 1; if no solution, DFS with a limit of 2; then 3; and so on. Each round restarts from the start node. The point is to buy BFS's guarantees at DFS's memory cost.
Across the four rounds drawn on this slide, how many rounds generate node B (depth 1)? How many generate node H (depth 3)? What does the ratio of those two numbers tell you about where the wasted work is?
Show answer
most nodes will be at the deepest level where most of the work needs to be done. Um and redoing the work for this initial triangles doesn't cost a lot of overhead.(Lecturer, T2). Slide p.62 poses the challenge itself ("Isn't that wastefully redundant?"); this sentence plus the arithmetic below is the full answer.
Slide p.64 gives the properties, all inherited: ID finds the same solutions as BFS; its space is the same as DFS but only down to the level of the first solution, so O(b·s); it is complete if s is finite; and it is optimal only if all costs are 1, just like BFS.
With b = 10 and s = 5, compute the node count for BFS and for ID, term by term, and check the claimed overhead of 11 percent against the closed form b/(b-1).
Show answer
Constructed, in the sample paper's format (2023 theory exam, part 1, true or false)
Because iterative deepening regenerates the shallow levels of the tree in every round, its time complexity is asymptotically worse than that of breadth-first search.
True is the trap, and the reason it feels right is that the redundancy is real; it is just concentrated in the cheap levels. Licensed quote 38 (Lecturer, T2) is the one-line answer to write: "most nodes will be at the deepest level where most of the work needs to be done. Um and redoing the work for this initial triangles doesn't cost a lot of overhead." The statement that is true, and the reason the algorithm exists, concerns space: iterative deepening is O(b·s) where BFS is O(bs). Marking: +0.5 / -0.25 / 0.
Slide p.66 gives depth-limited search as pseudocode. It is depth-first search (select and remove the first path, add new paths to the start of the frontier), and it differs from the TREE-SEARCH baseline of Section 2 in two places, not one. Both are marked in the listing:
procedure depth-limited-search(
Input: a graph,
a set of start nodes,
Boolean procedure goal(n) that tests if n is a goal node,
depthlimit: natural number
)
frontier := {<s> : s is a start node}
while frontier is not empty:
select and remove first path <n0,...,nk> from frontier
if k < depthlimit # difference 1: the depth test
for every neighbor n of nk
if goal(n) # difference 2: the goal test moved here
then return <n0,...,nk,N>
else add <n0,...,nk,n> to start of frontier
end while- The depth test.
if k < depthlimitgates the whole expansion block: a path that has already reached the limit is popped, and then simply dropped. The lecturer states the rule in words:the path will only be expanded if the path has a length k that is smaller than the permitted depth limit
(Lecturer, T2). Note it is the path length k, the number of arcs, that is compared, matching the definition on p.7. - The goal test has moved. In TREE-SEARCH and GENERIC-SEARCH the goal test is applied to the node just popped. Here it sits inside the neighbour loop and is applied to each child
nthe moment it is generated, returning <n0,...,nk,N> without that path ever entering the frontier. That is the early goal check, discussed in the exam box in Section 10 below.
The early check is legitimate here because depth-limited search is plain depth-first search with no costs and no heuristic, which is exactly the case the exercise-session solutions license. Writing the same shortcut into a uniform cost search or A* trace would change the answer. One small typographic quirk on the slide, worth knowing so it does not confuse you in the exam: the returned path is printed as <n0,...,nk,N> with a capital N while the loop variable is lower-case n. It is the same node.
The slide also carries the note "written without loopbreaking". Slide p.67 wraps this procedure in the outer loop: start at depth limit 1, return if the goal is found, otherwise increase the limit and search again.
Slide p.67 carries the note "you can also write ID recursively". On this the lecturer is explicit: recursion is the standard implementation of depth-first search, but it makes the complexity harder to analyse, and so, in his words, "we don't do it here" (Lecturer, T2). Recursive formulations of DFS and iterative deepening are out of scope. Learn the stack-and-frontier version. He does, however, expect you to reason about the loop breaking that p.66 leaves out (the slide says so itself, in its footer note "written without loopbreaking"): you should be able to say where a reached set would go in that pseudocode.
9. Bidirectional search (pp.68 to 72)
Search forward from the start and backward from the goal at the same time, and stop when the two meet. If both halves are symmetric, each only has to reach depth s/2.
With b = 10 and s = 6, show where 1,111,110 and 2,220 come from, and state the ratio.
Show answer
Slide p.70 lists why you often cannot do it: the branching factor can differ in the two directions; backward search is not always possible ("e.g. in chess when starting from all checkmate states", because there are too many of them to enumerate); and it can be impossible to invert actions.
Name the line that fixes the search order, the line that alternates the two directions, and the line that detects the meeting point. Then say what breaks if you change the first of these to insert at the front instead.
Show answer
- Order:
else add <n0,...,nk,n> to end of frontier_i. Appending at the end is FIFO, therefore breadth-first. - Alternation:
i := i + 1 mod 2; j := i + 1 mod 2; (swap i and j), so consecutive iterations take a path from the other frontier. - Meeting point:
if n occurs in path <n'0,...,n'l> of frontier_j then return solution based on <n'0,...,n'l> and <n0,...,nk>. The returned solution is the forward path, plus the meeting node, plus the reverse of the backward path.
The slide answers "complete? Yes" and "optimal? Yes". Name the three requirements printed on the right of the same slide, and match them to the superscripts on the p.82 summary table.
Show answer
On p.82 bidirectional carries superscripts a and d for completeness (b finite, both directions breadth-first) and c and d for optimality (step costs all identical, both directions breadth-first). Requirement (1) is the unwritten precondition for "if applicable", the phrase in the table's column heading.
Exercise session 2 (2025-26), exercise 2, verbatim
"Which methods other than breadth-first can be used in bidirectional search, and is it possible to replace breadth-first for either or both of the directions (forward and backward)?"
Show the model answer
- "Bidirectional search is complete for each combination with at least one complete search-strategy." The list it gives: 2 x breadth-first; 2 x depth-first (printed with an asterisk); breadth-first and depth-first; "any other complete unweighted search algorithm, e.g. iterative deepening".
- "Not each combination benefits from searching at both ends."
Two readings to add, both flagged as inference rather than slide text. The asterisk on "2 x depth-first" is not glossed on that slide, and the bullet above it is the natural explanation: that combination is the one with zero complete strategies, so it is the case where the guarantee is inherited from neither side. And "not each combination benefits" is about the arithmetic on p.69: the factor-500 saving (1,111,110 against 2,220) assumes both halves sweep outwards level by level and therefore meet near depth s/2. Two depth-first halves can plunge down different branches and pass each other, so you pay for two searches and collect neither half's saving.
What earns the marks in an open question of this shape: name the completeness criterion first, then answer the yes or no, then give the cost. Do not stop at p.72's requirement "here breadth-first": that is the condition for the optimality claim and the p.82 superscript d, not a ban on other strategies.
10. Uniform cost search (pp.73 to 80)
Everything so far has ignored costs. Slide p.74 makes the point on Romania: BFS "finds the shortest path in terms of number of actions. It does not find the least-cost path." UCS is still uninformed, since it knows nothing about where the goal is, but it does use the cost of the path built so far.
Definition: g(n) is the cost from the root to n. Strategy: expand a cheapest node, the one with lowest g(n), first. Implementation: the frontier is a priority queue sorted by g(n).
Using the edge costs printed on this slide (S to d 3, S to e 9, S to p 1, p to q 15, d to b 1, d to e 2, d to c 8), the frontier just before the third pop is
Write the frontier after popping and expanding Sd, keeping it sorted by g. Then say which path is popped next.
Show answer
Why the goal test must stay late
This is the single most examinable subtlety in the UCS section, and the lecturer spends a full minute on it in T3. Continue the run above and you reach a state where the goal path SderfG has cost 10 while Se, cost 9, is still on the frontier. Both numbers are printed on the slide's tree (G is annotated 10, e is annotated 9).
If you tested for the goal when the child was generated, you would return the cost-10 path immediately. That would be wrong, because a path of cost 9 is still unexplored and could conceivably reach G with one further cheap arc. The lecturer makes the point with a concrete number: for all UCS knows there could be an arc of cost one half leading from e to G, making a total of 9.5, which beats 10. So the cost-10 path cannot be declared the solution yet. Only after Se is popped and expanded, and nothing cheaper turns up, is the cost-10 path returned.
Exercise session 2 (2025-26) solutions, sidenote question, verbatim
The solution deck for exercise session 2 poses "Where best to place the goal check?" and answers with two options: check when a node is popped (late), or check when a child is generated (early). Which of the three readings below is the one it endorses?
A is the dangerous one: in UCS the early check returns the first goal path generated, and the paragraph above shows why that is wrong, the cost-10 goal path is generated while a cost-9 path is still on the frontier. B is too strong: p.66's depth-limited search does exactly the early check and is correct there, because there are no costs and no heuristic to be ordered by.
The lecture deck itself uses both conventions, so read any pseudocode before you trace it: TREE-SEARCH (p.9) and GENERIC-SEARCH (p.27) test the goal at pop time, while depth-limited search (p.66) tests it inside the neighbour loop at generation time.
Classic mistake (archetype A2 and A3): using the early goal check in a UCS or A* trace and stopping one expansion too soon. In DFS and BFS it is allowed and saves you a line; in UCS and A* it changes the answer.
Tie-breaking. Asked in the lecture what happens when two paths have equal g, the lecturer answers that this is the designer's choice and must be made explicit. The two tie-breakers he names are alphabetical order and path length (the number of nodes already traversed). His worked illustration: if you also want to avoid traffic lights, a path over one long road can be preferred to a path over four crossroads at the same distance. The 2023 exercise exam fixes the rule for you: left-to-right or lexicographic.
(a) Why is the exponent C*/ε rather than a depth? (b) The slide insists the minimum arc cost ε must be strictly greater than zero and gives a counterexample. Reproduce it and say what goes wrong.
Show answer
(b) The counterexample on the slide: an infinite path <n0, n1, ..., nk> with cost(<ni-1, ni>) = 1/2i. The costs sum to a finite total (they are a geometric series), so this infinite path never exceeds a finite g, and UCS can go on expanding deeper prefixes of it forever without ever reaching the cheapest solution. With ε > 0, any infinite path has infinite cost and is eventually abandoned.
The slide's own answers for the other two properties: complete "assuming best solution has a finite cost and minimum arc cost is positive", optimal "Yes! (Proof will follow later)". The proof arrives in Part 5 as the A* optimality proof with h = 0.
The downside slide is also the bridge to Part 5: UCS "explores options in every direction" and has "no information about goal location". Slide p.76 draws it as concentric g-contours around the start. The lecturer's image: travelling from Kortrijk to Brussels, UCS expands in circles towards Lille, Bruges, Ypres and Veurne just as eagerly as towards Brussels (the transcript renders the four town names phonetically as "Leil", "Brush", "Ipers" and "Vam"; the verified reading is Lille, Bruges, Ypres, Veurne).
Three animations run on this maze. Give the visual test that separates them. Then say what the class in the lecture used as its reason for identifying the first one, and why that reason is the right one.
Show answer
- BFS: the expansion keeps growing concentrically and enters dark and light water at exactly the same rate. Cost is invisible to it.
- UCS: the expansion is visibly more reluctant to enter the dark blue deep water than the light blue shallow water. The frontier bulges through cheap terrain and creeps through expensive terrain.
- DFS: one long committed snake, producing a path far longer than necessary.
11. The summary table, and how it is examined (pp.81 to 82)
Slide p.81 closes the loop back to Part 2 and Part 3: a known, discrete, observable, deterministic, atomic environment; five ingredients; the right state representation is key; one general algorithm; "The difference is which node on the frontier to explore next!"; and four judging criteria.
Cover the image. Write the four rows for the six algorithms. Then answer: why does UCS have the exponent 1 + ⌊C*/ε⌋ here when p.76 said C*/ε, and why is DFS listed as not complete when p.47 said it is complete without cycles?
Show answer
| Criterion | Breadth-First | Uniform-Cost | Depth-First | Depth-Limited | Iterative Deepening | Bidirectional (if applicable) |
|---|---|---|---|---|---|---|
| Complete? | Yes a | Yes a,b | No | No | Yes a | Yes a,d |
| Time | O(bs) | O(b1+⌊C*/ε⌋) | O(bm) | O(bl) | O(bs) | O(bs/2) |
| Space | O(bs) | O(b1+⌊C*/ε⌋) | O(bm) | O(bl) | O(bs) | O(bs/2) |
| Optimal? | Yes c | Yes | No | No | Yes c | Yes c,d |
The +1 in the UCS exponent is the late goal test: in the worst case one extra layer has to be expanded before the goal path is finally removed from the priority queue. The lecturer's own comparison of the two forms: the p.76 version captures the essence better (time is exponential in the effective depth), and the p.82 version is the more correct one. He explicitly links the +1 to the late goal test practised in the exercise sessions.
DFS is listed as not complete because of the note under the table: "we are not checking for repeated states yet". Without the reached set, a cycle traps DFS forever. With it, p.47's statement holds. If an exam question asks whether DFS is complete, the full-mark answer names the assumption.
Constructed, in the sample paper's format (2023 theory exam, part 1, true or false)
In the summary table of p.82, depth-first search has space complexity O(bm).
True is the trap because the two cells look alike at a glance and because the BFS column really does carry O(bs) twice. Linear memory is the entire reason DFS exists, and the whole argument for iterative deepening (O(b·s), BFS's answers at DFS's memory) collapses if you misremember this row.
One caveat worth a line if the question is open rather than true or false: the exercise session 2 solutions note that global loop detection sacrifices this bound, "DFS using approach 1 as loop detection will sacrifice its O(b.m) memory complexity into O(V)", where V is the state-space size. Marking: +0.5 / -0.25 / 0.
2023 sample exercise exam, question 1 (2 points), verbatim; archetype A2
"The following image depicts a simple search space. S represents a start node. G1, G2, and G3 are all possible goal nodes. The numbers shown in parentheses are the heuristic estimate at their associated node, the edge weights are the costs of the transition. Execute each of the following search algorithms until termination and write down their frontier at every step. Where appropriate employ the familiar left-to-right order or lexicographic order as tie-breaker. 1. Depth-first search: 2. Breadth-first search: 3. Greedy-search: 4. A*:"
Two of the four algorithms are this Part; the other two are Part 5.
Show the model approach
- Write the conventions first, one line, before any trace. "Late goal test; loop breaking per branch; ties left to right." Three of the four mistakes below are pre-empted by that line, and it takes fifteen seconds.
- One line per frontier, paths not states, in the order the algorithm holds them. The answer box is small: the boxes "give an indication of the expected length" (Lecturer, T9), and a trace of this graph is three or four lines.
- Depth-first and breadth-first are worked in full in Sections 5 and 6 above. Short forms: DFS gives [S], [SA, SG2, SG3], [SAG1, SG2, SG3], then pops the goal <S, A, G1> at cost 10. BFS gives [S], [SA, SG2, SG3], [SG2, SG3, SAG1], then pops the goal <S, G2> at cost 12. One line differs, and it changes which goal is reported.
- Greedy and A* are the same frontier with a different sort key (Part 5): h for greedy, g + h for A*, against g for uniform cost search here. Nothing else in the machinery changes, which is why practising this frontier pays for two chapters.
The four mistakes that lose marks on this exact question:
- Writing nodes instead of paths. The frontier is a list of paths. Writing [b, c, d] instead of [Sb, Sc, Sd] is the archetypal error, and the official multiple-choice wording ("select paths from the frontier") shows the examiner cares.
- Not stating your loop-detection scope (global reached set versus per-branch). Write one line: "loop breaking per branch" or "global reached set".
- Using the early goal check in UCS or A*. Legal for DFS and BFS, wrong for the cost-based and heuristic algorithms.
- Silently breaking ties. The question hands you the rule (left-to-right, lexicographic). Use it, and use the same one in all four traces.
What this sets up
- Part 5, Informed Search. Nothing in the algorithm changes; only the frontier's sort key does. Greedy sorts by h, UCS sorts by g, A* sorts by g + h. The whole of Part 5 is a re-ordering of the priority queue you just built, plus the question of which heuristics keep the optimality that UCS had for free.
- Part 6, Constraint Satisfaction. Backtracking search is depth-first search over partial assignments: the same stack, the same left-to-right convention, the same O(b·m) memory. Forward checking and arc consistency are pruning added to that DFS, not a new algorithm.
- Part 11, Planning. STRIPS (Stanford Research Institute Problem Solver) progression planning searches the space of world states with exactly this machinery, including the loop problem. The lecturer says so directly (T10): "this is equivalent to the loop breaking that we added to the algorithms that we have seen before." The A* over planning states in that Part reuses both this frontier and Part 5's f-values.
Term box
| Term | Precise definition | Plain paraphrase | Exam phrasing |
|---|---|---|---|
| State space graph | Nodes are abstracted world configurations, arcs are successors labelled with the action; each state occurs exactly once; the goal test is a set of goal nodes. | A map of the world, drawn once. | "A mathematical representation of a search problem" (p.5) |
| Search tree | The unrolling of the state space graph from the initial state; every node is a distinct path, so one state can appear many times or infinitely often. | A map of the searching, not of the world. | "Each node in the search tree is an entire path in the state space graph." (p.8) |
| Node (in this course) | A path <n0, ..., nk> from the initial state. node.STATE is nk. Written AB as shorthand for <A, B>. |
Not a state. A whole route ending in a state. | "a note in this tree actually represents an entire path" (Lecturer, T2) |
| Frontier (fringe) | The set of nodes generated but not yet expanded. It separates the explored from the unexplored region of the state space graph. | The to-do list, holding paths. | "write down their frontier at every step" (2023 exercise exam Q1) |
| Expansion | Generating all successor nodes of a node, one per available action, and inserting them into the frontier. | Opening one path and listing everything it leads to. | "node expansion: generating all successor nodes considering the available actions" (p.34) |
| Reached set | A set of states already expanded; a popped node whose last state is in the set is goal-tested and then discarded without expansion. | The memory that stops you walking in circles. | "On-demand tree search, with loop detection" (p.27) |
| Generic search / graph search | TREE-SEARCH plus the reached set. Same algorithm under two names. | Tree search that remembers where it has been. | "In the project, this is referred to as graph search because it works on any graph, while tree search only works on trees." (p.27) |
| Late goal test | The goal test is applied when a node is removed from the frontier, not when it is generated. Required for UCS and A*, optional for DFS and BFS. | Check for the goal when you pick a path up, not when you write it down. | "the early goal check ... is only applicable to DFS and BFS, and not algorithms that involve costs (like UCS) or heuristics (like A*)" (exercise session 2 solutions) |
| LIFO stack | Frontier discipline in which the most recently inserted path is removed first; new children are inserted at the front. | Pile of papers: take the top one. | "Depth-first search follows a Last-In First-Out strategy to select paths from the frontier." (2023 theory MC 1.2, True) |
| FIFO queue | Frontier discipline in which the oldest path is removed first; new children are appended at the end. | Supermarket queue: first in, first served. | "Select the element from [AB, AC, AD] that is the oldest, that was added first" (p.50) |
| Priority queue | Frontier sorted by a key; in UCS the key is g(n), the cumulative cost from the root to n. | Always serve the cheapest path so far. | "Frontier is a priority queue, sorted by g(n) (priority: cumulative cost)" (p.75) |
| Complete | The algorithm is guaranteed to find a solution if one exists. | It will not miss a solution that is there. | "Complete: Guaranteed to find a solution if one exists?" (p.46) |
| Optimal | The algorithm is guaranteed to find the least cost path, not merely some path. | Finds the cheapest, not just any. | "Optimal: Guaranteed to find the least cost path?" (p.46). BFS and ID only "if step costs are all identical" (p.82, superscript c) |
| b, s, m, l, C*, ε | Branching factor; depth of the (shallowest) solution; maximum depth of the search tree; depth limit; cost of the optimal solution; minimal cost of any single action, assumed strictly positive. UCS runs in O(b1+⌊C*/ε⌋). | Width; how deep the answer is; how deep it can go; how deep you allow; the price of the best answer; the price of the cheapest possible step. | The legend under the summary table (p.82). Also: "If that solution costs C* and arcs cost at least ε, then the effective depth is roughly C*/ε" (p.76) |
| Cost contour | A band of the search tree containing all paths whose g falls in a given range; UCS's replacement for BFS's depth tiers. | Equal-price rings around the start. | "Cost contours" (p.75); "C*/ε tiers" (p.76) |
Constructed, in the sample paper's format (2023 theory exam, part 1, true or false)
In this course, an algorithm is called optimal if it is guaranteed to find the solution path with the fewest arcs.
True is the trap, and the sample exercise exam contains the counterexample: on that graph BFS returns the one-arc path <S, G2> at cost 12 while <S, A, G1> costs 10 (Section 6). Because fill-in questions are marked on the definition you write down, use the deck's four words, "least cost path", and add the precondition whenever you call BFS optimal. Marking: +0.5 / -0.25 / 0.