English:Algorithms and Computational Thinking
Algorithms and Computational Thinking
Introduction
Algorithms are everywhere: when a navigation app chooses a route, when a search engine orders results, when a game reacts to a player's actions, and when a person follows a recipe. In computer science, an algorithm is a finite, unambiguous sequence of steps for solving a problem or completing a task. Computational thinking is a broader problem-solving approach that helps you describe problems so that solutions can be carried out systematically by people or computers.
This Grade 9–10 aiMOOC develops the habits behind good problem solving. You will learn to break complex problems into manageable parts, notice useful patterns, ignore irrelevant detail, design algorithms, represent them with pseudocode and flowcharts, test them, compare their efficiency, and improve them.
By the end of the course, you should be able to explain how computational thinking supports problem solving, create and trace algorithms that use sequence, selection, and iteration, compare linear and binary search, explain simple sorting strategies, test algorithms with suitable cases, and justify why one solution may be more efficient or reliable than another.
Computational Thinking
Computational thinking is useful well beyond programming. You can use it to plan a school event, organize research, design a science experiment, analyze a repeated process at work, or create a strategy for a game. The goal is not merely to "think like a computer." The goal is to express a problem and its solution in a clear, structured form.
Decomposition
Decomposition means breaking a large problem into smaller subproblems. Imagine designing a school library app. Instead of treating "build the app" as one huge task, you might separate it into login, searching for books, borrowing, returning, overdue notices, and user help. Each part can then be understood, designed, tested, and improved separately.
Good decomposition makes teamwork easier because different people can work on different components. It also helps you locate errors: if borrowing works but returning does not, you know where to investigate.
Pattern Recognition
Pattern recognition means noticing similarities, repetitions, or regularities. If several subproblems can be solved in similar ways, you may be able to reuse one idea instead of inventing a new solution each time.
For example, a program that checks whether a username is valid and one that checks whether a password is valid may both need to test length, allowed characters, and missing input. Recognizing this pattern can lead to reusable procedures.
Abstraction
Abstraction means focusing on information that matters for the current problem while leaving out details that do not. A map is an abstraction: a subway map emphasizes stations and connections but usually ignores the exact shape of buildings and streets.
In computing, abstraction lets you work with a useful model instead of every low-level detail. When you use a function such as "sort this list," you can often use the function correctly without knowing every instruction inside it.
Algorithm Design
Once you understand the problem, you can design a sequence of steps that transforms inputs into the required outputs. Good algorithm design asks several questions: What data is available? What result is required? Which decisions must be made? What must repeat? What happens in unusual or invalid cases?
An algorithm should be precise enough that two careful readers would perform the same actions for the same input.
What Makes an Algorithm?
An algorithm normally has a clear purpose, defined inputs when inputs are needed, ordered steps, a stopping point, and an expected output or result. A useful algorithm must also be correct for the cases it is supposed to handle.
Consider an algorithm for finding the largest value in a non-empty list. It can start by treating the first value as the current largest value. It then compares each remaining value with the current largest value and replaces the current largest value whenever a bigger value is found. After the last comparison, the current largest value is the result.
This simple example shows an important idea: an algorithm often stores a temporary state that changes while the algorithm runs.
Control Structures
Most school-level algorithms can be described with three fundamental control structures: sequence, selection, and iteration. These structures appear in many programming languages even though the exact syntax differs.
Sequence
A sequence performs instructions in order. For example, an online form may read a name, read an email address, validate the entries, and then display a message. Changing the order can change the result.
Selection
Selection chooses between alternatives based on a condition. A typical pattern is "IF a condition is true, do one action; ELSE, do another." For example, if a test score is at least the passing threshold, display "pass"; otherwise display "review needed."
Selection is also called branching because the algorithm can follow different paths.
Iteration
Iteration repeats instructions. A loop may repeat a fixed number of times, repeat once for every item in a collection, or continue while a condition remains true. For example, an algorithm can add all values in a list by repeating the same addition step for each value.
A loop must be designed so that it eventually stops. A loop whose stopping condition can never become false may run forever.
Representing Algorithms
You can represent the same algorithm in several ways. Natural language is easy to begin with, but it can become ambiguous. Pseudocode is a structured, language-independent description that resembles programming. A flowchart uses standardized shapes and arrows to show control flow.
A flowchart usually uses an oval or rounded shape for start or end, a rectangle for a process, a diamond for a decision, and arrows for direction of flow. The exact visual conventions can vary, so a good diagram should include enough labels to be understood without guessing.
Example pseudocode for deciding whether a learner may enter a school competition could read:
INPUT age
IF age >= 14 AND age <= 16 THEN
OUTPUT "eligible"
ELSE
OUTPUT "not eligible"
END IF
Pseudocode is not a single formal programming language. Its value is clarity. Use meaningful names, consistent indentation, explicit decisions, and clear loop boundaries.
Tracing Algorithms
Tracing means following an algorithm step by step for a chosen input. A trace table records how important variables change. Tracing helps you predict output, understand loops, and find logic errors before you write or run code.
Suppose an algorithm starts with total = 0 and then adds each value from the list 4, 7, 2. After the first addition, total is 4. After the second, total is 11. After the third, total is 13. A trace makes the changing state visible.
When you trace a conditional algorithm, record which condition was tested and which branch was taken. When you trace a loop, record each repetition so that skipped or repeated steps become easier to spot.
Searching Algorithms
Searching means locating a target item or determining that it is absent. The choice of search algorithm depends strongly on how the data is organized.
Linear Search
Linear search checks items one by one until the target is found or the list ends. It works on unsorted data. If the target is near the beginning, it may finish quickly, but in the worst case it may need to inspect every item.
For a list of n items, linear search has worst-case running time proportional to n, commonly written as O(n).
Binary Search
Binary search is much faster on large sorted lists, but it requires the data to be in sorted order. It compares the target with the middle item. If they are equal, the search stops. If the target is smaller, the search continues in the lower half; if larger, it continues in the upper half. Each comparison removes about half of the remaining possibilities.
For n sorted items, binary search has worst-case running time proportional to log n, commonly written as O(log n). This is why repeatedly halving a search range scales efficiently.
Sorting Algorithms
Sorting arranges data into an order, such as smallest to largest or alphabetical order. Sorted data can be easier to search, compare, group, or display. There are many sorting algorithms, and they make different trade-offs.
Selection Sort
Selection sort repeatedly finds the smallest remaining item and moves it into the next position in the sorted part of the list. It is conceptually simple, but for large lists it performs many comparisons.
Insertion Sort
Insertion sort builds a sorted section one item at a time. Each new item is inserted into its correct position among the items already processed. It can be efficient for small or nearly sorted data, but its worst-case running time grows quadratically with the number of items.
Comparing Sorts
Two algorithms can produce the same sorted output yet require very different amounts of work. Comparison should consider input size, data order, memory requirements, implementation complexity, and whether stability or other properties matter.
Datei:15 Sorting Algorithms in 6 Minutes.webm
For Grades 9–10, the most important idea is not memorizing every sorting algorithm. It is learning to trace a strategy, explain why it works, and compare its behavior with alternatives.
Efficiency and Big O
Algorithmic efficiency asks how the resources used by an algorithm grow as the input grows. Two common resources are execution time and memory. Big O notation describes an upper-bound growth rate and is often used to discuss worst-case running time.
At this level, focus on qualitative comparisons. O(1) means work that does not grow with input size. O(log n) grows slowly because the problem is repeatedly reduced. O(n) grows in direct proportion to the number of items. O(n²) grows much faster because the amount of work can involve pairs of items or nested passes.
Big O does not tell you the exact time in seconds. Hardware, programming language, implementation details, and small constant factors still matter. Big O helps compare how algorithms scale as inputs become large.
Correctness, Testing, and Debugging
An algorithm is useful only if it gives the intended result for the cases it is meant to handle. Testing checks behavior with chosen inputs. Debugging is the process of finding and correcting errors.
Strong tests include normal cases, boundary cases, and invalid cases when invalid input is possible. For an algorithm that accepts ages from 14 through 16, useful tests include a value in the middle, both boundary values, values just outside the boundaries, and inappropriate input such as missing data if the system permits it.
A logic error occurs when an algorithm runs but produces an incorrect result. An off-by-one error happens when a loop or index processes one item too many or one item too few. A failure to update a loop-control variable can cause an infinite loop.
Testing should be planned, not improvised. State the input, expected result, actual result, and whether the test passed. If a test fails, use the evidence to locate the problem and revise the algorithm.
Computational Thinking in Real Life
Computational thinking is transferable. A science investigation can be decomposed into variables, procedure, data collection, and analysis. A history project can abstract a large collection of sources into categories and patterns. A business process can be modeled as decisions and repeated steps. A language-learning app can use algorithms to schedule practice based on previous answers.
However, not every problem should be automated. An algorithm reflects the goals, assumptions, and data chosen by people. If those choices are incomplete or unfair, the output may also be poor. Responsible computational thinking therefore includes asking what is being optimized, whose needs are represented, what information is missing, and how errors could affect people.
Interactive Tasks
Quiz: Test Your Knowledge
What best describes an algorithm? (A finite sequence of unambiguous steps for solving a problem) (!A random collection of computer commands) (!Any diagram that contains arrows) (!A computer that performs calculations)
Which computational-thinking practice breaks a complex problem into smaller parts? (Decomposition) (!Abstraction) (!Encryption) (!Compilation)
What is the main purpose of abstraction in problem solving? (To focus on relevant details and ignore unnecessary detail) (!To make every problem more complicated) (!To replace all testing) (!To store every possible detail)
Which control structure chooses between alternative actions? (Selection) (!Sequence) (!Storage) (!Sorting)
What must be true before ordinary binary search can be used correctly on a list? (The list must be sorted) (!The list must contain duplicate values) (!The list must contain exactly ten items) (!The list must be stored on paper)
What does linear search do? (It checks items one by one) (!It always starts with the middle item) (!It requires a sorted list) (!It sorts the list before every comparison)
Which growth rate is associated with the worst case of binary search? (O log n) (!O n squared) (!O n cubed) (!O two to the n)
What is tracing an algorithm? (Following its steps for a chosen input) (!Translating it into every programming language) (!Deleting all of its conditions) (!Measuring only the computer screen size)
Which test is especially useful for checking a boundary condition? (A value exactly at an allowed limit) (!A value chosen only because it is easy to type) (!A repeated copy of the same normal value) (!A value unrelated to the allowed range)
Why can two correct algorithms still be meaningfully compared? (They may use different amounts of time or memory) (!Only one correct algorithm can exist for a problem) (!Correct algorithms always perform the same number of steps) (!Correct algorithms cannot be tested)
Memory Game
| Decomposition | Breaking a complex problem into smaller subproblems |
| Pattern recognition | Finding similarities or repeated structures that can guide a solution |
| Abstraction | Keeping relevant information while ignoring unnecessary detail |
| Algorithm design | Creating precise ordered steps that transform input into a result |
| Debugging | Finding and correcting errors in an algorithm or program |
| Efficiency | Considering how resource use grows as input size increases |
Drag and Drop
| Match the correct terms. | Topic |
|---|---|
| Checks items in sequence | Linear search |
| Repeatedly halves a sorted search range | Binary search |
| Finds the smallest remaining item for the next position | Selection sort |
| Repeats a set of instructions | Iteration |
| Tests whether an expression is true or false | Condition |
...
Crossword Puzzle
| Algorithm | What is a finite set of clear steps for solving a problem? |
| Decomposition | What process breaks a large problem into smaller parts? |
| Abstraction | What process focuses on relevant details and hides unnecessary detail? |
| Iteration | What control structure repeats instructions? |
| Branching | What idea describes taking different paths based on a condition? |
| Efficiency | What quality concerns the resources an algorithm uses as input grows? |
LearningApps
Cloze Text
Open-Ended Tasks
Easy
- Everyday algorithm: Choose an everyday task such as making a snack or organizing a backpack. Write a clear algorithm for it, then ask a partner to follow your steps exactly and note where clarification is needed.
- Flowchart challenge: Create a flowchart for deciding what to wear based on at least two conditions such as temperature and rain. Use clear start, decision, process, and end symbols.
- Search experiment: Use a sorted list of at least 30 words. Search for five targets with linear search and binary search, recording the number of comparisons for each method.
- Trace table: Write pseudocode for finding the total of a short list of numbers. Create a trace table that shows how the total changes after each item.
Standard
- Sorting investigation: Use cards with ten different numbers. Perform selection sort and insertion sort by hand, record each comparison or movement, and explain which method felt more efficient for your starting order.
- Debugging clinic: Create a short algorithm containing at least three logic errors, exchange it with a partner, and produce a corrected version with explanations of the fixes.
- Interview on algorithms: Interview a person who uses step-by-step procedures in work, sport, art, cooking, or another field. Identify decomposition, decisions, repetition, and testing in the person's process.
- Computational thinking poster: Design an image or digital poster that explains decomposition, pattern recognition, abstraction, and algorithm design through one shared real-world example.
Advanced
- Algorithm comparison study: Design a fair experiment that compares linear and binary search over several list sizes. Collect data, graph your results, and explain how the observed growth relates to O(n) and O(log n).
- Route planning model: Represent a small set of locations and connections as a graph, invent a clear route-finding strategy, test it on several start and end points, and discuss where the strategy succeeds or fails.
- Responsible automation video: Produce a short video that explains a real automated decision system, identifies its inputs and outputs, and analyzes how missing data or biased assumptions could affect people.
- Mini software design: Plan and build a small program in a language or block-based environment of your choice. Document the problem decomposition, pseudocode, tests, debugging evidence, and one efficiency improvement.
Learning Assessment
- Algorithm explanation: Given an unfamiliar piece of pseudocode, trace it for two contrasting inputs, explain its purpose, and justify your explanation with evidence from the trace.
- Search strategy decision: Decide whether linear or binary search is more appropriate for three different data scenarios and explain how data order, list size, and preparation cost affect your choices.
- Test design: Create a test plan for an algorithm with valid and invalid input, including normal and boundary cases, and explain what each test is intended to reveal.
- Efficiency reasoning: Compare two correct algorithms that solve the same problem and argue which you would choose for small inputs and for very large inputs.
- Abstraction transfer: Take a real process from another school subject and construct an abstraction that preserves what is important for solving a chosen problem while explaining what you deliberately left out.
- Algorithm redesign: Improve a flawed or inefficient algorithm, then defend your changes in terms of correctness, clarity, termination, and resource use.
Evidence of Learning
Knowledge: You can explain algorithms, decomposition, pattern recognition, abstraction, sequence, selection, iteration, searching, sorting, tracing, testing, debugging, and basic efficiency concepts in your own words.
Skills: You can decompose problems, write and interpret pseudocode, build flowcharts, trace variables, choose test cases, identify logic errors, compare searching strategies, and reason about how running time grows.
Products: Useful evidence includes annotated pseudocode, flowcharts, trace tables, test plans, search or sort experiments, graphs, posters, videos, and working programs.
Transfer: Strong evidence shows that you can apply computational thinking to a new context such as science, mathematics, business, media, language learning, or an everyday process and can justify the choices you make.
OERs on the Topic
Linked Learning Areas
