Compigorithm: An Interactive Tool for Guided Practice of Complexity Analysis

Abstract

It is essential that students learn to write code that is not only correct, but also efficient. To that end, algorithmic complexity analysis techniques, such as Big-O analysis, are typically an important part of courses on algorithm design. However, students often hold fundamental misconceptions about how Big-O analysis works. This paper presents Compigorithm, an interactive tool for helping students practice Big-O analysis. Compigorithm scaffolds student learning by breaking down the analysis process into five concrete steps and walking students through each of these steps. When students make mistakes, they are provided with automated hints and allowed to re-attempt until they get the correct answer. Compigorithm was piloted in an introductory algorithms course and evaluated using a controlled experiment. The experimental group trained by analyzing algorithms using Compigorithm, while the control group analyzed the same algorithms by hand. On the subsequent post-test, the experimental group outperformed the control group by a significant margin (p < 0.00001; Cohen’s d = 0.84).

Publication
Proceedings of the ACM Conference on Innovation and Technology in Computer Science Education (ITiCSE)