Computing · JC 2

Active learning ideas

Graphs and Shortest Path Algorithms

Active learning helps students grasp stacks and queues because these abstract concepts become concrete when they manipulate real implementations and see them perform. When students code, simulate, or trace operations, they connect theory to practice, which builds intuition for trade-offs between time and space complexity.

• MOE Syllabus Outcomes
• MOE H2 Computing (Syllabus 9569), Section 1: Algorithms and Data Structures - 1.2 Data Structures (Graphs: Adjacency Matrix and Adjacency List)
• MOE H2 Computing (Syllabus 9569), Section 1: Algorithms and Data Structures - 1.1 Algorithms (Shortest Path Algorithms)

• 25–45 min
• Pairs → Whole Class
• 4 activities

Activity 01

• Plan-Do-Review
• 45 min · Pairs

Pair Programming: Stack Implementations

Pairs implement array-based and linked-list stacks in pseudocode or Python, adding push, pop, and peek methods. They test with sequences of operations and measure simulated time costs. Compare results in a shared class document.

How can real-world networks be represented as graphs?

Facilitation Tip

During Pair Programming: Stack Implementations, circulate and ask students to explain why their chosen implementation handles edge cases like full arrays or null pointers.

What to look for

Present students with two code snippets: one implementing a stack using an array and another using a linked list. Ask them to identify one advantage and one disadvantage of each implementation in terms of memory usage and performance for a large number of operations.

• Remember
• Apply
• Analyze
• Self-Management
• Decision-Making
• Self-Awareness

Activity 02

• Plan-Do-Review
• 30 min · Small Groups

Small Groups: Postfix Evaluator Game

Groups receive cards with postfix expressions like '3 4 + 5 *'. They use physical tokens on a stack model to evaluate step-by-step, recording stack states. Discuss errors and complexities as a group.

What is the difference between breadth-first and depth-first search?

Facilitation Tip

During Small Groups: Postfix Evaluator Game, require each group to present their evaluation steps on a whiteboard to ensure everyone follows the stack operations.

What to look for

Provide students with a postfix expression, e.g., '5 2 + 3 *'. Ask them to trace the evaluation using a stack, showing the stack's state after each operation. Then, ask them to state the final result.

• Remember
• Apply
• Analyze
• Self-Management
• Decision-Making
• Self-Awareness

Activity 03

• Plan-Do-Review
• 35 min · Whole Class

Whole Class: Graph Traversal Simulation

Project a simple graph. Class votes on next moves using stack (DFS) or queue (BFS) rules, with teacher facilitating pushes/pops on a board. Students note visited order and path properties.

How does Dijkstra's algorithm find the shortest path?

Facilitation Tip

During Whole Class: Graph Traversal Simulation, assign roles so each student represents a node or edge to make the traversal process visible to all.

What to look for

Pose the question: 'Imagine you are designing a system to manage customer support tickets. Would you use a stack or a queue? Justify your choice by explaining how the ADT's properties align with the system's requirements for handling incoming requests.'

• Remember
• Apply
• Analyze
• Self-Management
• Decision-Making
• Self-Awareness

Activity 04

• Plan-Do-Review
• 25 min · Individual

Individual: Queue vs Stack Challenges

Students solve puzzles like reversing a word (stack) or round-robin scheduling (queue) using everyday objects. Submit traces showing operation sequences and rationale for ADT choice.

How can real-world networks be represented as graphs?

Facilitation Tip

During Individual: Queue vs Stack Challenges, let students compare their answers with a peer before discussing as a class to encourage reflection.

What to look for

Present students with two code snippets: one implementing a stack using an array and another using a linked list. Ask them to identify one advantage and one disadvantage of each implementation in terms of memory usage and performance for a large number of operations.

• Remember
• Apply
• Analyze
• Self-Management
• Decision-Making
• Self-Awareness

A few notes on teaching this unit

Teach these topics through iterative cycles of coding, testing, and discussion. Start with small, fixed-size problems so students see errors like stack overflow clearly, then scale up to dynamic cases. Avoid rushing to optimizations; let students experience the inefficiencies first. Research shows that hands-on manipulation of data structures, especially with visual aids, improves retention of abstract concepts like LIFO and FIFO.

Successful learning looks like students confidently choosing between array and linked implementations based on problem constraints, tracing postfix expressions correctly using stacks, and explaining why a queue or stack fits a real-world scenario. They should justify their choices with evidence from simulated operations or code behavior.

---

Watch Out for These Misconceptions

• During Pair Programming: Stack Implementations, watch for students assuming array-based stacks always outperform linked-list versions.

  Ask the pair to run timing tests on both versions with increasing input sizes, noting that linked lists avoid resizing costs but add pointer overhead.

• During Whole Class: Graph Traversal Simulation, watch for students believing stacks and queues can be swapped for any traversal.

  Have students physically mark nodes in a graph with colored stickers to show how LIFO backtracking differs from FIFO breadth-first paths.

• During Small Groups: Postfix Evaluator Game, watch for students assuming postfix evaluation requires recursion.

  Ask the group to trace their expression on paper, step-by-step, to see how a single stack handles the evaluation iteratively.

---

Methods used in this brief

• Plan-Do-Review