Students misconceptions in analysis of algorithmic and computational complexity of problems
Mark Trakhtenbrot · 2013
Course "Computability and Complexity" allows students to get familiar with limits of computation and degrees of algorithmic (decidable, enumerable, undecidable) and computational (P, NP, NP-complete) complexity of problems. Students learn to use reducibility techniques for analysis of language complexity. Due to the formal and abstract nature of the studied concepts, students tend to develop a variety of misconceptions that turn such analysis to a wrong path. In our research, we analysed typical misconceptions arising in this context and their sources. We then developed a series of special purpose examples that help students to actively construct a proper understanding by confronting their misconceptions.