Open the editorEditor
Lesson plan

Data structures and algorithms lesson plan

The ideas every programmer is asked about, built and measured on an Uno: big O, linked lists, stacks and queues, hash maps, sorting and binary search. Ends with a leaderboard that needs them all.

4 chapters, 7 lessons, about 6 hours, on the Arduino Uno R3. Every lesson runs in the browser, with nothing to install.

Start a class from this course
The unit

Objectives and materials

By the end, students can

  • Arrays, big O, and lists made from a fixed pool of nodes.
  • Stacks, queues and a hash map: limits that make things fast.
  • Three sorts raced and counted, then binary search and its off-by-one.
  • A leaderboard for a reaction game, built from the whole course.

Materials for the whole unit

  • Arduino Uno R3
  • Full-size breadboard
  • LED x 3
  • Pushbutton
  • Resistor x 3

Every part is already on the simulator’s bench, so there is nothing to buy or hand out. The counts are the most any one lesson uses, if you build it on real breadboards too.

Chapter 1. About 1 h 40 min

What things cost

Arrays, big O, and lists made from a fixed pool of nodes.

LessonTimeWhat students do
Arrays and big OOne block of 64 ints: an index lookup that costs one step, a scan that costs up to n, a pair check that costs n squared over two, and a table that shows each cost as n doubles.50 min
  1. Run it: 64 ints in a row
  2. An index lookup is O(1)
  3. Finding a value is O(n)
  4. The worst case
  5. Count the work as n doubles
  6. O(n^2): every pair
  7. Double n yourself
Linked listsNodes joined by pointers, taken from a fixed pool of 16 so nothing can fragment: add at the head, insert and delete in the middle, run the pool dry, and fix a reverse that leaks.50 min
  1. Run it: a pool of nodes
  2. Add at the head: O(1)
  3. Insert in the middle
  4. Delete, and the pointer to a pointer
  5. Run the pool dry
  6. Reverse it, and watch it vanish
  7. Fix the reverse

Materials

  • Arduino Uno R3
  • Full-size breadboard
  • LED x 3
  • Pushbutton
  • Resistor x 3

Check for understanding

Each student finishes "Linked lists" on their own, without opening the hints. The simulator checks 7 of its 7 steps as they go.

Then ask each one to explain, in a sentence or two, the last thing it asked of them: "Fix the reverse".

Chapter 2. About 1 h 35 min

Structures with rules

Stacks, queues and a hash map: limits that make things fast.

LessonTimeWhat students do
Stacks and queuesAn array stack that matches brackets and undoes a running total, and a ring-buffer queue of lamp tasks fed by the serial monitor and the button. Then a stack that overflows, and the fix.50 min
  1. Run it: two shapes
  2. Match brackets with a stack
  3. Catch a mismatch
  4. Undo is a stack
  5. A queue of tasks
  6. A full queue says no
  7. Stack overflow
Hash mapsAn 8 slot open-addressing table: a hash function turns a name into a home slot, collisions probe onward, tombstones keep chains whole, the load factor lights a lamp, and a better hash spreads the names out.45 min
  1. Run it: names to slots
  2. Set and get in one probe
  3. A collision
  4. The load factor
  5. Delete with a tombstone
  6. A better hash

Materials

  • Arduino Uno R3
  • Full-size breadboard
  • LED x 3
  • Pushbutton
  • Resistor x 3

Check for understanding

Each student finishes "Hash maps" on their own, without opening the hints. The simulator checks 6 of its 6 steps as they go.

Then ask each one to explain, in a sentence or two, the last thing it asked of them: "A better hash".

Chapter 3. About 1 h 40 min

Put it in order, find it fast

Three sorts raced and counted, then binary search and its off-by-one.

LessonTimeWhat students do
SortingBubble, insertion and quick sort on the same 16 numbers with every comparison and swap counted, best and worst cases, stability shown with tags, a race to 64, and an early exit that makes bubble sort smart.50 min
  1. Run it: 16 numbers
  2. Bubble sort
  3. Insertion sort
  4. Quick sort, and its bad day
  5. Stability
  6. Race them as n doubles
  7. Teach bubble sort to stop
Searching and binary searchLinear against binary search on 100 sorted numbers with comparisons counted, a slow-motion search on the lamps, a guessing game in ten tries, and an off-by-one found by a self-test.50 min
  1. Run it: 100 sorted values
  2. Linear: 51 looks
  3. Binary: 6 looks
  4. Watch it on the lamps
  5. Play: I guess your number
  6. A self-test finds an off-by-one
  7. Fix the off-by-one

Materials

  • Arduino Uno R3
  • Full-size breadboard
  • LED x 3
  • Pushbutton
  • Resistor x 3

Check for understanding

Each student finishes "Searching and binary search" on their own, without opening the hints. The simulator checks 7 of its 7 steps as they go.

Then ask each one to explain, in a sentence or two, the last thing it asked of them: "Fix the off-by-one".

Chapter 4. About 1 h

Boss

A leaderboard for a reaction game, built from the whole course.

LessonTimeWhat students do
Boss: a leaderboardA reaction game and its leaderboard built from the course: players in a hash map, a ranking kept sorted by one insertion pass, binary search for where a score would land, and a stable rule for ties.60 min
  1. Run it: the board is open
  2. Submit scores
  3. Look up by name
  4. A new best moves up
  5. Where would 500 rank?
  6. Play: the button game
  7. Make ties fair
  8. Make it yours

Materials

  • Arduino Uno R3
  • Full-size breadboard
  • LED x 3
  • Pushbutton
  • Resistor x 3

Check for understanding

Each student finishes "Boss: a leaderboard" on their own, without opening the hints. The simulator checks 8 of its 8 steps as they go.

Then ask each one to explain, in a sentence or two, the last thing it asked of them: "Make it yours".

Your class

Teach this unit as a class

Start a class from this course and its 7 lessons are assigned in one go, in order. Students join with a six-character code or printed login cards, and each one’s work comes back to you.

The class tools are free for 30 days for one class of up to 20 students, with no card. The lessons themselves are free either way.

Start a class from this courseSee the demo class
More units

Other lesson plans

Electronics basics20 lessons, about 10 h.Embedded on the Arduino Uno16 lessons, about 12 h.Embedded on the ESP32-C313 lessons, about 11 h.Embedded on the Raspberry Pi Pico7 lessons, about 6 h.Build your own fight stick5 lessons, about 4 h.Embedded on the STM32F4116 lessons, about 6 h.C++ on a board13 lessons, about 10 h.Digital logic and memory4 lessons, about 4 h.Interactive devices on the Uno9 lessons, about 8 h.From gates to a computer23 lessons, about 16 h.Build a claw machine8 lessons, about 6 h.Every unitAll the courses as ready-made units, on the teachers page.