Teaching greedy algorithms with interactive components

Following my previous post on teaching sorting algorithms with interactive videos, I have developed a new interactive component to help my students work with greedy algorithms.

The Activity Selection problem is a classic example of a greedy algorithm. Given a set of activities, each with a start and end time, the goal is to select the maximum number of activities that do not overlap. In the problems terminology, we want to find the maximum number of activities that are compatible (i.e. do not overlap) with each other.

The key insight to solving this problem is to sort the activities by their end time and then greedily select the first activity that ends first. This is because the activity that ends first will free up the most time for other activities to be scheduled. Alternatively, if we sort the activities by their start time, and greedily select the activity that starts last, we may also find a solution.

To help my students explore the problem and get to the intuition behind the greedy algorithm, I have developed the interactive component below. The component allows students to add or modify activities, sort them by start time, end time, and duration, as well as select the activities they want to include in the solution. I have tested this component with some students last year, but it will become part of my regular teaching material this year. Feel free to interact with the component below. Once again, it is not easily available as a standalone tool, but I am happy to share the code with anyone interested.

The next step on this component is to simplify the process for editing of activities. I really wanted to have a drag-and-drop interface for the activities, but I had to settle for the text area for now, because the semester is about to start. I also wanted to add a feature to automatically generate random activities, but I will leave that for the future.

Activity selection

Huffman Codes

Another classic example of a greedy algorithm is the construction of Huffman codes. I have developed a few components using GraphViz to help my students understand the basic concepts behind the codes.

This is actually more of a draft, but I hope it is already helpful. It already shows the Huffman tree, so it’s still far from what I wanted it to be. My plan is to create more intermediate steps, so students can get the intuition behind the algorithm, and then how the tree is built step-by-step.