Give

Comparing algorithms

Count how the steps grow as the data grows, and choose the right method.

Back to Coding · Searching and sorting

Planned. This module is part of the plan and is not written yet.

COCO-ALG-SRT-0505Level12–13

Why it matters

The Lantern runs on two small computers serving many stations, so a method whose steps grow slowly as the data grows keeps every learner's screen quick.

Draft outline · in review
For
Level 12–13 · SSS 3 (WASSCE) to A level / JUPEB / foundation year
Inside
5 lessons and a test · about 75 minutes
Topic
Searching and sorting · extension, 3 of 4
Plate CO-ALG-SRT-05: planned.

Inside the module.

5 lessons in order, about 75 minutes in all, then a short test. Learners go at their own pace; the minutes are a guide, not a timetable.

Draft outline · in review

  1. Lesson 1: Counting steps, not seconds

    Why we measure how steps grow with n instead of timing one run.

    Explain15 min, from minute 0

  2. Lesson 2: O(n), O(log n), O(n log n), O(n²)

    The growth rates of the searches and sorts you know.

    Explain15 min, from minute 15

  3. Lesson 3: Timing sorts as n grows

    Time bubble sort and merge sort on growing lists and plot the results.

    Investigate20 min, from minute 30

  4. Lesson 4: Choosing the right tool

    Small data, nearly sorted data, data searched often: which method fits?

    Discussion15 min, from minute 50

  5. Lesson 5: Check your skills

    Match algorithms to growth rates and justify choices.

    Review10 min, from minute 65

  6. End-of-module test

    Compare how the steps of different searches and sorts grow, and choose and justify a method for a given task.

    Mastered at 85% or more. Retake it until you pass; nothing is lost, and each try gives feedback.

    Already know it? A Challenge Test (planned) clears the whole module: 90% overall, no objective below 75%.

    Last stageafter about 75 min

Practicalities

Draft outline · in review

  • Built to run offline

    Planned to run on the Lantern's own computer, with no internet needed.

  • Languages

    Planned first in English; every module aims to reach all of the Lantern's languages.

Try a question.

One question from the module, as a learner would meet it. Have a go, then open the worked solution a step at a time.

Draft outline · in review

A list of 10,000 learner records changes rarely but is searched hundreds of times a day. Which approach is best?

Your answer

Particulars

Where it sits

Coding · Algorithms & data structures · Searching and sorting

What a learner can do after it

  1. Compare how the number of steps grows for different searches and sorts.
  2. Choose a suitable search or sort for a task and justify it.

Needs first

Unlocks

Level

Level 12–13 · SSS 3 (WASSCE) to A level / JUPEB / foundation year

Show levels in

Level mappings are approximate. A qualified teacher or lecturer in each country must check them before they appear in the app. Levels 13–18 describe the content, not the learner: “Level 15” means material usually taught in a second-year university course, whoever chooses to learn it.

Difficulty for its level

3 of 4 · Extension

Time

About 75 minutes

Alignments

  • Aligned to CS2023partial · in reviewCS2023 Algorithmic Foundations: searching and sorting (descriptive ref)

Alignment in review until a qualified teacher or lecturer checks it. No exam body, university or vendor endorses us; learners still sit the real exam. University-level modules give knowledge, not university credit.

Challenge Test

Planned: a Challenge Test to prove you know it and skip it. Pass at 90% overall, with no objective below 75%.

University courses it previews

Computer Science, Software Engineering

On these pathways

The route here.

Everything this module builds on, drawn as a route from its foundations. Solid lanes must be mastered first, or cleared by a Challenge Test; dashed lanes are suggestions that never lock anything.

From Level 1, Instructions in order to Level 8, Loops in Python
  1. CO-BLK-SEQ-01 Instructions in order, Level 1–4, Coding. Planned.
  2. CO-BLK-SEQ-01Instructions in orderCoding · Primary 1 to Primary 4 (Level 1–4) · Planned
  3. CO-BLK-LOP-01 Repeat blocks, Level 3–5, Coding. Sample lesson in the demo.
  4. CO-BLK-LOP-01Repeat blocksCoding · Primary 3 to Primary 5 (Level 3–5) · Sample lesson in the demo Needs Instructions in order (required).Try the sample lesson: Repeat blocks
  5. DS-CMP-TYP-01 The home row, Level 3–6, Digital skills. Planned.
  6. DS-CMP-TYP-01The home rowDigital skills · Primary 3 to Primary 6 (Level 3–6) · Planned · recommended
  7. CO-BLK-CND-01 If this, then that, Level 3–6, Coding. Planned.
  8. CO-BLK-CND-01If this, then thatCoding · Primary 3 to Primary 6 (Level 3–6) · Planned · recommended
  9. CO-BLK-LOP-02 Patterns with loops, Level 4–6, Coding. Planned.
  10. CO-BLK-LOP-02Patterns with loopsCoding · Primary 4 to Primary 6 (Level 4–6) · Planned Needs Repeat blocks (required).
  11. MA-ARI-ORD-01 Order of operations, Level 5–6, Maths. Planned.
  12. MA-ARI-ORD-01Order of operationsMaths · Primary 5 to Primary 6 (Level 5–6) · Planned · recommended
  13. CO-BLK-LOP-03 Loops inside loops, Level 5–7, Coding. Planned.
  14. CO-BLK-LOP-03Loops inside loopsCoding · Primary 5 to JSS 1 (Level 5–7) · Planned · recommended
  15. CO-PRG-PYB-01 Your first Python program, Level 7–9, Coding. Planned.
  16. CO-PRG-PYB-01Your first Python programCoding · JSS 1 to JSS 3 (BECE) (Level 7–9) · Planned Needs Patterns with loops (required), The home row (recommended).
  17. CO-PRG-PYB-02 Variables, Level 7–9, Coding. Sample lesson in the demo.
  18. CO-PRG-PYB-02VariablesCoding · JSS 1 to JSS 3 (BECE) (Level 7–9) · Sample lesson in the demo Needs Your first Python program (required).Try the sample lesson: Variables
  19. CO-PRG-PYB-03 Numbers and calculations, Level 7–9, Coding. Planned.
  20. CO-PRG-PYB-03Numbers and calculationsCoding · JSS 1 to JSS 3 (BECE) (Level 7–9) · Planned Needs Variables (required), Order of operations (recommended).
  21. MA-ALG-FRM-01 Substituting into formulae, Level 7–8, Maths. Planned.
  22. MA-ALG-FRM-01Substituting into formulaeMaths · JSS 1 to JSS 2 (Level 7–8) · Planned · recommended
  23. CO-PRG-PYB-05 Decisions with if, Level 8–10, Coding. Planned.
  24. CO-PRG-PYB-05Decisions with ifCoding · JSS 2 to SSS 1 (Level 8–10) · Planned Needs Numbers and calculations (required), If this, then that (recommended).
  25. CO-PRG-PYB-06 Loops in Python, Level 8–10, Coding. Planned.
  26. CO-PRG-PYB-06Loops in PythonCoding · JSS 2 to SSS 1 (Level 8–10) · Planned Needs Decisions with if (required), Loops inside loops (recommended).
  27. CO-PRG-PYF-01Defining functionsCoding · JSS 2 to SSS 2 (Level 8–11) · Planned Needs Loops in Python (required).
  28. CO-PRG-PYB-07ListsCoding · JSS 2 to SSS 1 (Level 8–10) · Planned Needs Loops in Python (required).
  29. CO-PRG-PYF-02Parameters and return valuesCoding · JSS 3 (BECE) to SSS 2 (Level 9–11) · Planned Needs Defining functions (required), Substituting into formulae (recommended).
  30. CO-ALG-SRT-01Linear searchCoding · JSS 3 (BECE) to SSS 2 (Level 9–11) · Planned Needs Parameters and return values (required), Lists (required).
  31. CO-PRG-PYF-03ScopeCoding · JSS 3 (BECE) to SSS 2 (Level 9–11) · Planned Needs Parameters and return values (required).
  32. CO-ALG-SRT-03Simple sortsCoding · SSS 1 to SSS 3 (WASSCE) (Level 10–12) · Planned Needs Linear search (required).
  33. CO-ALG-SRT-02Binary searchCoding · SSS 1 to SSS 3 (WASSCE) (Level 10–12) · Planned Needs Linear search (required).
  34. CO-PRG-PYF-05RecursionCoding · SSS 2 to A level / JUPEB / foundation year (Level 11–13) · Planned Needs Scope (required).
  35. CO-ALG-SRT-04Merge sortCoding · SSS 2 to A level / JUPEB / foundation year (Level 11–13) · Planned Needs Simple sorts (required), Recursion (required).
  36. CO-ALG-SRT-05Comparing algorithmsCoding · SSS 3 (WASSCE) to A level / JUPEB / foundation year (Level 12–13) · Planned · the destination Needs Binary search (required), Merge sort (required).
23 stops across Coding, Digital skills and Maths. 2 have a sample lesson in the demo; the other 21 are planned and not yet written.

Help light the room where this is learned.

Every route on this map starts in a classroom with 24 stations, a tutor that works offline and a facilitator upstairs. Four are planned and waiting for light.

Help light a LanternTalk to us about a major gift