VCE Vault

Year 9 Digital Technologies · Creating Digital Solutions · 18m read

Algorithms and Computational Thinking

Ever noticed how you follow the same steps every time you make a sandwich? That's an algorithm — a step-by-step set of instructions. In computing, you'll learn to break down tricky problems into smaller pieces (decomposition), focus on what really matters (abstraction), and spot patterns to solve them efficiently. This skill is pure gold for VCE success and beyond, whether you're coding or tackling any messy real-world problem that needs a logical solution.

Learning objective: Design and validate algorithms using decomposition, abstraction and pattern recognition.

By the end of this lesson you can:

  • I can decompose a complex problem into smaller sub-problems.
  • I can design an algorithm using pseudocode or flowcharts.
  • I can trace an algorithm to verify its correctness.

Algorithms are recipes. Exact, ordered steps that always produce the same dish. Computational thinking helps you write good recipes.

Computational thinking tools

COMPUTATIONAL THINKING — four pillars:
1. DECOMPOSITION: break a big problem into smaller, manageable sub-problems.
2. PATTERN RECOGNITION: identify similarities and reusable solutions.
3. ABSTRACTION: focus on essential details; ignore irrelevant ones.
4. ALGORITHM DESIGN: create step-by-step instructions.

ALGORITHMS:
• Precise, ordered steps to solve a problem.
• Must be: CORRECT, EFFICIENT, and CLEAR.

PSEUDOCODE:
• Human-readable description of algorithm logic.
• Not code syntax — focus on logic.
• Example:
INPUT temperature
IF temperature > 37.5 THEN
PRINT "Fever detected"
ELSE
PRINT "Normal"
ENDIF

FLOWCHARTS:
• Visual representation of algorithm flow.
• Shapes: oval (start/end), rectangle (process), diamond (decision), arrows (flow).

COMMON ALGORITHM PATTERNS:
• SEQUENTIAL: steps in order.
• SELECTION: IF...ELSE branching.
• ITERATION: WHILE or FOR loops.
• SEARCH: linear search, binary search.
• SORT: bubble sort, merge sort.

### Searching Algorithms Compared

LINEAR SEARCH: check every element in order.
Best case: O(1) — first element is a match.
Worst case: O(n) — check all n elements.
Works on unsorted data.

BINARY SEARCH: repeatedly halve the search space.
Requires SORTED data.
Worst case: O(log n) — halve n until 1 element remains.

Example — find 72 in [45, 52, 61, 72, 85, 90, 99]:
Step 1: mid = 61 (index 2); 72 > 61, search right half.
Step 2: mid = 85 (index 4); 72 < 85, search left half.
Step 3: mid = 72 (index 3); found! 3 steps vs 4 steps linear.

### Sorting Algorithms

BUBBLE SORT: compare adjacent pairs, swap if out of order, repeat.
Simple but inefficient for large lists: O(n²).
Each pass "bubbles" the largest unsorted element to its correct position.

MERGE SORT: divide list in half recursively, then merge sorted halves.
Much more efficient: O(n log n).
Used in professional applications.

### Algorithm Tracing Table

For algorithm: SET max = list[0]; FOR each x in list: IF x > max THEN max = x
Input: [45, 72, 38, 90, 61]

| Step | x | max |
|------|---|-----|
| Init | - | 45 |
| 1 | 45 | 45 |
| 2 | 72 | 72 |
| 3 | 38 | 72 |
| 4 | 90 | 90 |
| 5 | 61 | 90 |
Output: 90 ✓

TRACING AN ALGORITHM:
• Walk through each step with test values.
• Verify the output matches expected results.
• Identify errors ("bugs") before coding.

EFFICIENCY:
• BIG-O NOTATION: describes how time grows with input size.
• Linear search: O(n). Binary search: O(log n).

AARI TIP: Ask Aari to help you trace an algorithm or design pseudocode for a specific problem.

Algorithm principles

  • Decompose first: Break complex problems down before designing solutions.
  • Test with examples: Trace through your algorithm with actual values.
  • Edge cases: What happens with empty input, max values, invalid input?

Worked example (Medium)

Write pseudocode to find the highest score in a list of test results.

  1. Decompose. We need to: (1) read all scores, (2) keep track of the highest, (3) output the result.
  2. Pseudocode. SET highest = 0 FOR EACH score IN scores IF score > highest THEN SET highest = score ENDIF ENDFOR PRINT "Highest score: " + highest
  3. Trace. Scores: [72, 85, 61, 90, 78]. After loop: highest = 90. ✓
  4. Edge case. If all scores are 0, highest = 0 — correct. If list is empty, highest = 0 — should handle with a check.

Answer: A correct algorithm finds the maximum by comparing each element to a running "highest" variable — O(n) linear complexity.

Common mistakes

  • Writing pseudocode with actual Python/Java syntax Pseudocode is language-agnostic — examiners want logic, not syntax. Using "print()" instead of "OUTPUT" suggests you're writing code not pseudocode Fix: Use natural language constructs: INPUT, OUTPUT, SET, IF...THEN...ENDIF, FOR...ENDFOR, WHILE...ENDWHILE
  • Applying binary search to an unsorted list Binary search relies on the sorted order to determine which half to discard — on an unsorted list it will produce wrong results Fix: Always verify the list is sorted before using binary search; use linear search on unsorted data
  • Ignoring edge cases in algorithm design Algorithms that work on normal inputs but fail on empty lists, zero values, or maximum inputs have bugs that will cause crashes or wrong answers Fix: Explicitly test: empty input, single element, all-same values, minimum and maximum values

Worked example (Hard)

Trace a bubble sort algorithm on [64, 34, 25, 12, 22, 11, 90]. Show the full trace table and count the comparisons.

  1. Algorithm. BUBBLE SORT: For each pass, compare adjacent pairs and swap if left > right. Repeat until no swaps occur in a full pass.
  2. Pass 1. [64,34,25,12,22,11,90] → [34,64,25,12,22,11,90] → [34,25,64,12,22,11,90] → [34,25,12,64,22,11,90] → [34,25,12,22,64,11,90] → [34,25,12,22,11,64,90] → 90 already largest. After pass 1: [34,25,12,22,11,64,90]. Comparisons: 6.
  3. Pass 2. [34,25,12,22,11,64,90] → [25,34,12,22,11,64,90] → [25,12,34,22,11,64,90] → [25,12,22,34,11,64,90] → [25,12,22,11,34,64,90]. After pass 2: [25,12,22,11,34,64,90]. Comparisons: 5.
  4. Remaining passes. Pass 3: [12,22,11,25,34,64,90] — Comparisons: 4. Pass 4: [12,11,22,25,34,64,90] — Comparisons: 3. Pass 5: [11,12,22,25,34,64,90] — Comparisons: 2. Pass 6: no swaps — sorted!
  5. Total comparisons. 6+5+4+3+2+1 = 21 comparisons for 7 elements. General formula: n(n-1)/2 = 7×6/2 = 21. This confirms O(n²) complexity.
  6. Reflection. For 1000 elements, bubble sort would need ~500,000 comparisons. Merge sort would need only ~10,000. This is why algorithm efficiency matters in real systems.

Answer: Bubble sort is simple but inefficient (O(n²)). The trace table method verifies correctness step by step. For large datasets, O(n log n) algorithms like merge sort are essential.

Practice questions

  1. Decomposition in computational thinking means:

    1. Deleting unnecessary code.
    2. Breaking a complex problem into smaller, manageable sub-problems.
    3. Finding patterns in data.
    4. Writing pseudocode.

    (1 marks)

  2. Write pseudocode to check whether a password meets these requirements: at least 8 characters, contains at least one number.

    (3 marks)

  3. Binary search requires the list to be:

    1. Sorted in ascending or descending order
    2. Unsorted
    3. Containing no duplicates
    4. Stored in a database

    (1 marks)

  4. Trace the following algorithm with the input list [3, 7, 1, 9, 4, 6] and show the final output:

    SET total = 0
    SET count = 0
    FOR EACH number IN list:
    SET total = total + number
    SET count = count + 1
    ENDFOR
    SET average = total / count
    OUTPUT average

    (3 marks)

  5. Explain why binary search is more efficient than linear search for large datasets.

    (2 marks)

Deeper Understanding: Algorithm Complexity and the Real World

Big-O notation is a mathematical way of describing how an algorithm's time (or space) requirements grow as the input size n increases. O(1) means constant time regardless of input size — a dictionary lookup. O(log n) algorithms (like binary search) grow very slowly and remain practical for enormous inputs. O(n) algorithms scale linearly. O(n²) algorithms (like bubble sort) become impractical for large inputs — doubling the input size quadruples the time.

Why does this matter in the real world? Google's search index contains hundreds of billions of web pages. Every search query must retrieve relevant results in under a second. This is only possible because of highly efficient algorithms (inverted indices, B-trees, parallelism) that operate in O(log n) or O(1) time. An O(n²) search across 100 billion pages would take hours, not milliseconds.

Algorithmic thinking has applications far beyond computing. Epidemiologists design algorithms to model disease spread; economists design auction mechanisms; logistics companies use routing algorithms to optimise delivery networks. The Victorian government uses algorithmic tools to allocate school resources and model traffic flow. Understanding how algorithms work — and fail — is becoming a fundamental literacy skill, not just a technical one.

There is also an emerging field called "algorithm auditing" — examining automated decision-making systems to identify bias, errors and unintended consequences. In Australia, the Australian Human Rights Commission has examined the use of automated decision-making in government services and highlighted risks to vulnerable populations when systems make errors that humans previously would have caught through common sense and contextual judgment.

Summary

  • Computational thinking: decomposition, pattern recognition, abstraction, algorithm design.
  • Algorithms must be correct, efficient and clear; expressed in pseudocode or flowcharts.
  • Linear search O(n); binary search O(log n) — requires sorted data.
  • Bubble sort O(n²); merge sort O(n log n) — efficiency matters for large datasets.
  • Algorithm tracing uses a table to track variable values step by step.
  • Edge cases (empty input, extremes, invalid values) must be explicitly handled.

More from Year 9 Digital Technologies