Computing · JC 2 · Abstract Data Structures and Algorithms · Semester 1

Introduction to Computational Thinking

Students will be introduced to the core concepts of computational thinking: decomposition, pattern recognition, abstraction, and algorithms, as problem-solving tools.

• MOE Syllabus Outcomes
• MOE: Computational Thinking - Middle School

About This Topic

Linked lists represent a fundamental shift from static to dynamic memory management in the JC 2 Computing syllabus. Unlike arrays, which require a contiguous block of memory and a fixed size, linked lists use pointers to connect nodes scattered across the heap. This topic introduces students to the elegance of dynamic allocation, where memory is used only when needed. Understanding how to manipulate these pointers is essential for mastering more complex structures like trees and graphs later in the A-Level journey.

Students must grasp the mechanics of insertion and deletion, specifically how to update pointers without losing the reference to the rest of the list. This requires a strong mental model of memory addresses and node structures. In the Singapore context, where computational thinking is a core pillar, being able to weigh the trade-offs between array-based and pointer-based implementations is a key assessment objective. This topic comes alive when students can physically model the pointer connections and trace the movement of data through collaborative visualization.

Key Questions

1. How does the choice of abstract data structure affect the time and space complexity of an algorithm, and what trade-offs must be considered when selecting between linear and non-linear structures?
2. When is a non-linear data structure such as a tree or graph preferable to a linear structure, and what properties of the problem determine this choice?
3. Compare the algorithm design paradigms of divide-and-conquer, greedy, and dynamic programming and analyse which paradigm yields provably optimal solutions for a given problem class.

Learning Objectives

• Decompose a complex problem into smaller, manageable sub-problems, identifying the core components of each.
• Recognize recurring patterns and similarities within a problem or across different problems to simplify solutions.
• Abstract essential features of a problem by ignoring irrelevant details to focus on critical information.
• Design and represent an algorithm as a sequence of precise steps to solve a given computational problem.

Before You Start

Introduction to Programming Concepts

Why: Students need a basic understanding of variables, data types, and control structures (like loops and conditionals) to grasp how algorithms are implemented.

Problem Solving Strategies

Why: Familiarity with general problem-solving approaches provides a foundation for understanding the more specific techniques of computational thinking.

Key Vocabulary

Decomposition	Breaking down a complex problem or system into smaller, more manageable parts. This makes the problem easier to understand and solve.
Pattern Recognition	Identifying similarities, trends, or regularities within data or problems. This helps in making predictions and developing efficient solutions.
Abstraction	Focusing on the essential qualities of something while ignoring unnecessary details. This simplifies complex systems by creating a higher-level view.
Algorithm	A step-by-step set of instructions or rules designed to perform a specific task or solve a particular problem.

Watch Out for These Misconceptions

Common Misconception

Deleting a node simply means setting its value to null.

What to Teach Instead

In a linked list, deletion requires rerouting the pointer of the previous node to the successor of the node being removed. Peer-led tracing of the 'next' references helps students see that the connection, not just the data, must be managed.

Common Misconception

Linked lists are always faster than arrays because they are dynamic.

What to Teach Instead

While insertion is efficient, searching a linked list is O(n) because you cannot jump to an index. Hands-on 'race' activities between an array-index lookup and a list-traversal help students internalize this performance difference.

Active Learning Ideas

Human Linked List Simulation

Assign each student to be a 'node' holding a piece of data and a card representing the 'pointer' (the name of another student). Students must physically rearrange themselves to perform operations like inserting a new person into the middle of the line or deleting a member while maintaining the chain.

30 min·Whole Class

Think-Pair-Share: The Memory Trade-off

Provide a scenario involving a real-time transport app tracking SBS buses. Students individually list the pros and cons of using an array versus a linked list for this data, then pair up to reach a consensus on the most memory-efficient approach before sharing with the class.

15 min·Pairs

Collaborative Debugging: The Broken Chain

Give small groups a snippet of Python or pseudocode for a linked list deletion that contains a logic error, such as a memory leak or a null pointer exception. Groups must trace the code on a whiteboard and present the corrected pointer logic to their peers.

25 min·Small Groups

Real-World Connections

• Software developers at Google use decomposition to break down large application features into smaller coding tasks for individual team members. Abstraction is used to design user interfaces that hide complex underlying processes.
• Roboticists designing autonomous vehicles employ pattern recognition to identify road signs and pedestrians, and abstraction to model the vehicle's environment without needing to process every single sensor input.
• Financial analysts use algorithms to process vast amounts of market data, identifying patterns for trading strategies and abstracting complex economic indicators into simpler metrics for decision-making.

Assessment Ideas

Quick Check

Present students with a common task, such as making a cup of tea. Ask them to write down the steps (algorithm). Then, ask them to identify how they decomposed the task, any patterns they noticed (e.g., heating water is common to many hot drinks), and what details they abstracted away (e.g., the exact temperature of the water).

Discussion Prompt

Pose a real-world problem, like planning a school event. Facilitate a class discussion using these prompts: 'How can we decompose this event into smaller parts?' 'What patterns do we see in successful past events?' 'What details can we abstract to focus on the main goals?' 'What would be the core steps in an algorithm to plan this?'

Exit Ticket

Provide students with a short description of a simple problem (e.g., sorting a list of numbers). Ask them to write one sentence explaining how they would decompose it, one sentence identifying a potential pattern, and one sentence describing an abstraction they might use.

Frequently Asked Questions

Why do we teach linked lists if Python's built-in lists are already dynamic?

Python lists are actually dynamic arrays, not linked lists. Teaching linked lists is crucial for understanding low-level memory management and pointers, which are foundational for the MOE syllabus and for understanding how data structures actually work under the hood in languages like C or Java.

What is the most difficult part of this topic for JC students?

Most students struggle with the logic of 'losing' the list. If a pointer is updated in the wrong order, the rest of the nodes become unreachable in memory. Visualizing these connections through diagrams or physical models is the best way to overcome this hurdle.

How can active learning help students understand linked lists?

Active learning, such as physical simulations or collaborative diagramming, forces students to externalize their mental models. When students have to 'be' the node and decide which peer to point to, the abstract concept of a memory address becomes a concrete relationship, making the logic of pointer manipulation much more intuitive.

Are doubly linked lists required for the A-Level exam?

Yes, students should understand the concept of nodes having both 'next' and 'previous' pointers. They should be able to explain the advantages, such as bi-directional traversal, and the costs, such as increased memory usage per node.