Graph_Search_Student_Led_Observation_Lesson

• newEditor
• Computer Science
• Secondary Education

GRAPH SEARCH | LESSON OBSERVATION

Year 13 • Chapter 18: Artificial Intelligence

Purpose and structure of graphs | Dijkstra’s | A*

Driving question: How does a navigation app choose the best route?

BIG QUESTION | THINK • PAIR • SHARE

Two routes lead to the same destination.

Is the route with the fewest roads always the shortest?

What information would an intelligent route planner need?

3 MIN • DISCUSS • Chapter 18.1 • A Level Computer Science

PRE-ASSESSMENT | QUICK VOTE

1. What does a vertex represent?

2. What is an edge?

3. Can the fewest edges give a longer route?

4. What does a weight represent in a road network?

5. How could an estimate of remaining distance help?

4 MIN • INDIVIDUAL → PAIR • Chapter 18.1 • A Level Computer Science

HANDS-ON STARTER | BUILD THE NETWORK

In teams of four, use paper node cards A, B, C, D, E and string to build a road map.

Add these road weights: A–B 6, A–D 1, D–B 2, D–E 1, B–E 2, B–C 5, E–C 5.

Find the cheapest A → C route. Record two competing routes and their costs.

Challenge: How do you prove that your choice is optimal?

7 MIN • MANIPULATIVES • Chapter 18.1 • A Level Computer Science

LEARNING OBJECTIVES & SUCCESS CRITERIA

I can identify vertices, edges, weights and directed/undirected graphs.

I can trace Dijkstra’s algorithm using distance and previous-node records.

I can trace A* using g(n), h(n) and f(n).

I can justify a route and compare the searches using evidence.

STUDENTS SELF-ASSESS • Chapter 18.1 • A Level Computer Science

DISCOVER | WHAT MAKES A GRAPH?

Look back at your physical network.

Label: vertices (nodes), edges (connections), weights (costs).

Discuss: What changes if a road is one-way?

Create your own real-world example: Dubai Metro, school routes or delivery logistics.

5 MIN • PEER EXPLANATION • Chapter 18.1 • A Level Computer Science

INVESTIGATE | DIJKSTRA’S RULES

Using the starter network, independently devise a repeatable procedure.

Hint cards: start distance = 0; all others = ∞.

Choose the unvisited node with the smallest tentative distance.

Update neighbouring distances and record previous nodes.

Mark the current node visited; repeat until the target is settled.

6 MIN • GUIDED DISCOVERY • Chapter 18.1 • A Level Computer Science

TEAM CHALLENGE | TRACE DIJKSTRA

Find shortest paths from A to every vertex in the starter network.

Complete a table: Node | Tentative distance | Previous node | Visited?

Use colour-coded counters to show the order visited.

Explain why a direct-looking road may not be the cheapest.

7 MIN • TEAM ROLES • Chapter 18.1 • A Level Computer Science

AFL | CONVINCE YOUR PARTNER

Claim: “A → B → C is best because it has only two edges.”

Agree or disagree? Calculate both paths.

Explain why Dijkstra’s algorithm requires non-negative edge weights.

Peer feedback: one strength and one correction.

3 MIN • MINI WHITEBOARDS • Chapter 18.1 • A Level Computer Science

INQUIRY | CAN WE SEARCH SMARTER?

Imagine a navigation app knows the approximate remaining distance to the destination.

What should it prioritise: distance travelled or estimated distance left?

Predict a score that combines both.

Reveal and interpret: f(n) = g(n) + h(n).

4 MIN • PREDICT → REVEAL • Chapter 18.1 • A Level Computer Science

A* | CARD SORT INVESTIGATION

Start A, goal C. Use the SAME weighted graph.

Heuristic estimates to C: A=6, D=5, E=4, B=4, C=0.

Calculate f=g+h for each candidate and choose the smallest f.

Keep a record of updated g-values and predecessor nodes.

Can you reach C with cost 7?

7 MIN • STUDENT ALGORITHM TRACE • Chapter 18.1 • A Level Computer Science

COMPARE | TWO SEARCH STRATEGIES

Dijkstra: prioritises smallest known distance from start (g).

A*: prioritises known distance plus estimated remaining cost (g+h).

Investigate: when h=0, what does A* resemble?

Debate: Can a misleading heuristic cause problems?

4 MIN • GROUP DISCUSSION • Chapter 18.1 • A Level Computer Science

DIFFERENTIATED TASKS | CHOICE BOARD

TASK 1 • SUPPORT: Build a graph using cut-outs; label vertices, edges and weights. Trace Dijkstra with a partially completed table.

TASK 2 • CORE: Independently calculate Dijkstra’s shortest route and explain updates.

TASK 3 • STRETCH: Trace A* with the supplied heuristic table; compare node selection.

TASK 4 • EXPERT: Design a new graph and admissible heuristic; challenge a peer to verify.

10 MIN • STUDENT CHOICE • Chapter 18.1 • A Level Computer Science

PAST-PAPER STYLE | INDIVIDUAL

A weighted graph has edges A–B 4, A–C 2, C–B 1, B–D 5, C–D 9.

(a) State the purpose of a weighted graph. [2]

(b) Apply Dijkstra’s algorithm to find the shortest A → D path. [4]

(c) Explain how A* uses a heuristic to guide the search. [3]

6 MIN • INDEPENDENT • Chapter 18.1 • A Level Computer Science

WAGOLL | PEER MARKING

(a) A graph models connected entities as vertices and relationships as weighted edges.

(b) A → C → B → D; total = 2 + 1 + 5 = 8.

(c) A* combines cost so far g(n) and estimated remaining cost h(n); selects the lowest f(n).

Check: Did your explanation justify the path?

3 MIN • SUCCESS CRITERIA • Chapter 18.1 • A Level Computer Science

EXTRA CHALLENGE | REAL-WORLD AI

A delivery robot must travel through a school building.

Propose graph vertices, edge weights and a suitable heuristic.

What happens if a corridor becomes blocked?

Evaluate whether shortest distance always means the best journey.

EXTENSION • TRANSFER • Chapter 18.1 • A Level Computer Science

PLENARY | EXIT TICKET

3 things you now know about graphs and search.

2 differences between Dijkstra’s and A*.

1 question you still have.

Traffic light your confidence against each success criterion.

4 MIN • INDIVIDUAL REFLECTION • Chapter 18.1 • A Level Computer Science

TEACHER OBSERVATION | EVIDENCE

Student agency: physical modelling, inquiry questions and task choice.

AfL: pre-assessment, mini-whiteboards, peer checking, exit ticket.

Differentiation: scaffolded trace, independent application, heuristic challenge.

Real-world transfer: navigation, Dubai transport and delivery routes.

Resources: printed cards, string, counters, graph worksheets.

FACILITATOR REFERENCE • Chapter 18.1 • A Level Computer Science