Lab Session 1 — Fibonacci Algorithms & Big-O

← Back to Data Structures and Algorithms

Course: MAT5EJ302(1) — Data Structures and Algorithms
Where: CS Lab | Duration: ~60 minutes
Prerequisite (already taught in lecture): the 3 Fibonacci algorithms (Module I §2 — naive recursion, memoisation, iterative) and the start of Big-O notation (Module I §3, at least the informal idea and the formal $\mathcal{O}(g(n))$ definition).

This is an instructor-facing lesson plan: what to say/do, and when. Students do not need any new theory — the whole point of this session is to let them see, on their own machine, the gap between an exponential and a polynomial algorithm that lecture described in words.

Learning Goal

By the end of the hour, students should be able to point at real numbers on their own screen and say “this is what $\mathcal{O}(\varphi^n)$ vs $\mathcal{O}(n)$ means” — not just recite the definition.

What You Need

• fibonacci.py (download it from Module V — nothing to write beforehand)
• Students working individually or in pairs, one machine each, Python 3 installed (python --version)
• A board/screen to tabulate results at the end

No new code needs to be authored for this session — everything below reuses fibonacci.py and the exercise already written in Module V §8.

Block 1 — Recap & Setup (0–5 min)

• 2-minute verbal recap only, no re-teaching: “We have three ways to compute Fibonacci numbers — naive recursion, memoisation, and iteration. We said the naive one is exponential and the other two are polynomial. Today we’re going to measure that instead of just saying it.”
• Get every student to a terminal:

  python --version        # confirm Python 3.x
  

Block 2 — Run and Read the Existing Demo (5–20 min)

• Everyone runs:

  python fibonacci.py
  

• Walk through the three sections of output together:
  1. First 15 Fibonacci numbers — sanity check, nothing new.
  2. Call count comparison (n = 5, 10, 15, 20) — how many times fib_recursive calls itself.
  3. Timing comparison at n = 35 — iterative and memoised finish in microseconds; naive recursion takes noticeably longer (seconds).
• Discussion prompt (ask, don’t tell): “Why does fib_recursive make so many more calls than the others as n grows? What is it recomputing?”
  • Steer toward: it re-derives the same sub-Fibonacci-numbers over and over — draw the recursion tree for fib_recursive(5) on the board if useful. This is the reason behind the exponential blow-up, which memoisation and iteration both avoid.

Block 3 — Hands-On Modification Exercise (20–40 min)

Two short exercises, done by editing fibonacci.py directly (or a copy) — reusing the existing count_calls_recursive and fib_iterative functions, not writing new algorithms from scratch.

Exercise A — Extend the call-count table. In the __main__ block, change the list [5, 10, 15, 20] to [5, 10, 15, 20, 22, 25, 28] and re-run.

Safety note (carried over from the script’s own warning): do not run fib_recursive(n) directly for n > ~35–40 — it will take too long. The call-count exercise is safe because count_calls_recursive is still just counting recursive calls, but keep n at or below ~30 for a snappy in-class run.

Ask students to compute, by hand or calculator, the ratio of calls between consecutive n (e.g., calls(25) / calls(22)… calls(n) / calls(n−1)). They should notice the ratio settles around ≈1.618 — the golden ratio $\varphi$. This is a hands-on, empirical encounter with the “$\varphi$” in $\mathcal{O}(\varphi^n)$ from lecture, and it works whether or not the class has formally reached the growth-class table yet.

Exercise B — Count operations in the iterative version. This is the exercise already written in Module V §8: modify fib_iterative to also return the number of loop iterations performed, and verify it is exactly n − 1. This gives students a concrete $\mathcal{O}(n)$ count to contrast against the exponential call counts from Exercise A.

Circulate while students work; this is the core hands-on block — give it the most time.

Block 4 — Discussion: Connecting Numbers to Big-O (40–55 min)

• Collect a couple of groups’ numbers and tabulate them on the board side by side: n, calls(fib_recursive), iterations(fib_iterative).
• Bridge to Big-O in language that works regardless of exactly how far §3 got in lecture:

  “The naive algorithm’s work roughly multiplies by a constant factor (≈1.618) every time n grows by 1 — that’s what we mean by $\mathcal{O}(\varphi^n)$, exponential. The iterative algorithm’s work grows by a constant amount each time n grows by 1 — that’s what we mean by $\mathcal{O}(n)$, linear/polynomial.”

• If the class has already reached §3.3 (growth-class table) or §3.4 (simplification rules): make the callback explicit — today’s exponential numbers are the concrete instance of the “$\mathcal{O}(2^n)$ — Naive Fibonacci” row in that table.
• If not yet reached: skip that callback entirely — nothing above depends on it.

Optional Bonus (last 5 min, or take-home) — Plotting

Only do this if the lab machines have matplotlib installed (python -c "import matplotlib" to check — the core lesson uses standard library only, so this is genuinely optional and not required):

import matplotlib.pyplot as plt

ns = [5, 10, 15, 20, 22, 25, 28]
calls = [count_calls_recursive(n, [0])[1][0] for n in ns]

plt.plot(ns, calls, marker='o')
plt.yscale('log')
plt.xlabel('n')
plt.ylabel('recursive calls (log scale)')
plt.title('fib_recursive call count grows exponentially')
plt.show()

A straight line on a log-y plot is itself a visual signature of exponential growth — worth mentioning if you do run it, but skip this block entirely rather than losing time troubleshooting a missing package.

Wrap-Up / Take-Home

• Point students to Module V §8 for further practice exercises on Fibonacci and beyond.
• One-line preview: “Next in lecture, we move to Module I §4 — Algorithms with Numbers (addition and multiplication algorithms).”

Timing Summary