Computer Science · Grade 11 · Algorithmic Foundations and Complexity · Term 1

Introduction to Algorithms and Problem Solving

Students will define what an algorithm is, explore its characteristics, and practice designing simple algorithms for everyday problems.

• Ontario Curriculum Expectations
• CS.HS.A.1
• CS.HS.A.2

About This Topic

Search and sort efficiency introduces students to the mathematical heart of computer science. In the Ontario Grade 11 curriculum, this topic moves beyond simply making code work to making code work well. Students explore how different algorithms like binary search, quicksort, and mergesort handle data sets of varying sizes. This is a critical transition point where learners begin to think like software engineers, considering the trade-offs between speed and memory usage.

Understanding Big O notation and algorithmic complexity allows students to predict how a system will scale, which is essential for modern software development. By comparing the 'best case' and 'worst case' scenarios, students develop a more nuanced view of problem-solving. This topic comes alive when students can physically model the patterns and compete to find the most efficient way to organize information.

Key Questions

1. Differentiate between an algorithm and a program.
2. Analyze how different representations of an algorithm impact its clarity and implementation.
3. Construct an algorithm to solve a common daily task, justifying each step.

Learning Objectives

• Define an algorithm and identify its key characteristics, including input, output, finiteness, definiteness, and effectiveness.
• Compare and contrast the representation of algorithms using pseudocode and flowcharts, analyzing the impact on clarity and implementation.
• Design a step-by-step algorithm to solve a common daily task, such as making a sandwich or navigating a simple maze.
• Justify each step in a constructed algorithm, explaining its purpose and contribution to the overall solution.

Before You Start

Basic Computer Literacy

Why: Students need to be familiar with fundamental computer operations and terminology to understand the context of algorithms.

Logical Thinking and Sequencing

Why: The ability to think logically and order steps sequentially is foundational for designing any algorithm.

Key Vocabulary

Algorithm	A set of well-defined, step-by-step instructions or rules designed to perform a specific task or solve a particular problem.
Pseudocode	An informal, high-level description of the operating principle of a computer program or other algorithm, using conventions that resemble natural language.
Flowchart	A diagram that represents a workflow or process, showing the steps as boxes of various shapes, and their order by connecting the boxes with arrows.
Input	The data or information that an algorithm receives to process.
Output	The result or solution produced by an algorithm after processing the input.

Watch Out for These Misconceptions

Common Misconception

Faster computers make efficient algorithms unnecessary.

What to Teach Instead

Even the fastest hardware cannot overcome the exponential growth of an inefficient algorithm. Peer discussion about 'scaling' helps students realize that as data grows from thousands to billions of items, the algorithm's logic matters more than the processor's clock speed.

Common Misconception

Binary search can be used on any list.

What to Teach Instead

Students often forget that binary search requires a sorted list to function. Hands-on modeling where students try to perform a binary search on unsorted cards quickly reveals why the logic fails without the initial sort.

Active Learning Ideas

Simulation Game: Human Sorting Network

Clear a space in the classroom and have students represent elements in an unsorted list. Assign each student a random number and have them move through a 'sorting network' taped on the floor, comparing values at each node to physically demonstrate bubble sort versus quicksort logic.

40 min·Whole Class

Inquiry Circle: The Great Search Race

Provide small groups with identical sets of 100 sealed envelopes containing numbers. One group uses linear search while another uses binary search (on a pre-sorted set) to find a specific value, recording the number of 'probes' or checks required to find the target.

25 min·Small Groups

Formal Debate: Merge vs. Quick

Assign teams to defend either Mergesort or Quicksort based on specific constraints like memory limits or nearly-sorted data. Students must argue why their assigned algorithm is the superior choice for a given real-world scenario, such as sorting a massive database on a low-power device.

30 min·Small Groups

Real-World Connections

• Recipe instructions for baking a cake are a real-world algorithm. Each step, from preheating the oven to mixing ingredients, must be followed precisely to achieve the desired output.
• Navigation apps like Google Maps or Waze use complex algorithms to calculate the fastest route between two points, considering traffic conditions, road closures, and speed limits.
• Assembly instructions for furniture, such as those from IKEA, are algorithms designed to guide users through a series of steps to construct a product.

Assessment Ideas

Quick Check

Present students with a simple task, like sorting three colored blocks (red, blue, green) from left to right. Ask them to write the algorithm to accomplish this task using either pseudocode or a flowchart. Review their work for clarity and correctness of steps.

Discussion Prompt

Pose the question: 'When might a flowchart be a better way to represent an algorithm than pseudocode, and vice versa?' Facilitate a class discussion where students share examples and justify their reasoning based on the complexity and nature of the problem.

Exit Ticket

Ask students to write down one characteristic of a good algorithm and provide a brief example of a task that would be difficult to create an algorithm for. Collect these to gauge understanding of algorithm properties and limitations.

Frequently Asked Questions

Why is Big O notation taught in Grade 11?

Big O provides a standardized language for students to describe efficiency. It aligns with Ontario curriculum expectations regarding the analysis of algorithm effectiveness. By learning this early, students can evaluate their own code's performance objectively rather than just guessing if it is 'fast enough' for a small test case.

How can active learning help students understand algorithm efficiency?

Active learning turns abstract mathematical concepts into tangible experiences. When students physically act out a sort or participate in a search simulation, they feel the 'friction' of inefficient steps. These kinesthetic activities make the difference between O(n) and O(log n) visible and memorable, leading to a deeper intuitive grasp of complexity before they ever write a line of code.

Which sorting algorithms are mandatory for the Ontario curriculum?

The curriculum focuses on understanding the principles of sorting. While specific algorithms aren't always mandated by name, teachers typically cover bubble, selection, and insertion sorts as foundations, moving into more complex recursive sorts like mergesort and quicksort to meet high-level expectations for Grade 11 and 12.

How do I explain the trade-off between time and space complexity?

Use a real-world analogy like a kitchen. A chef can cook faster (time) if they have more counter space to spread out ingredients (memory/space). In programming, some algorithms use extra memory to store temporary data to speed up the overall process. Discussing these trade-offs in small groups helps students see coding as a series of design choices.