Teaching greedy algorithms with interactive components
Following my previous post on teaching sorting algorithms with interactive videos, I’ve developed a new interactive component to help my students explore greedy algorithms.
One of the classic problems in this category is the Activity Selection Problem. Given a set of activities, each with a start and end time, the goal is to select the maximum number of non-overlapping activities. In other words, we want to find the largest subset of activities that are compatible with each other.
The Key Insight
The optimal solution follows a simple greedy strategy:
- Sort the activities by their end time.
- Iterate through the list, always selecting the first activity that finishes the earliest (while ensuring it doesn’t overlap with previously chosen activities).
Why does this work? Because picking the activity that ends the earliest maximizes the remaining time for scheduling additional activities. An alternative approach is to sort by start time and greedily select the latest-starting activity, which can also lead to a valid solution.
Interactive Component
To help students experiment with this problem and develop intuition for greedy algorithms, I’ve created the interactive component below. It allows students to:
- Add or modify activities
- Sort activities by start time, end time, or duration
- Manually select activities to test different strategies
I tested this tool with some students last year, and it will now become part of my regular teaching material. Feel free to try it out below! It’s not available as a standalone tool yet, but I’m happy to share the code with anyone interested.
Activity selection
Next Steps
While the current version is functional, there are a couple of features I’d like to add:
- Drag-and-drop interface for easier activity editing (instead of the current text-based approach)
- Random activity generator to quickly create new test cases
I had to leave these improvements for later since the semester is about to start, but they’re definitely on my roadmap!
Huffman Codes
Another classic example of a greedy algorithm is Huffman coding. I’ve started developing some GraphViz-based interactive components to help students understand how Huffman trees are constructed.
This is still in draft form, but it already visualizes the Huffman tree. My goal is to break the process into smaller, intuitive steps, so students can understand why the algorithm works and how the tree is built step by step.