From theory to practice: NP-completeness for every CS student

NP-completeness is one of the most central concepts in computer science, and has been extensively applied in many diverse application areas. Despite this, students have problems grasping the concept and, more specifically, applying it to new problems. Independently, we have identified these problems at our universities in different countries and cultures. In an action research approach we have modified our courses and studied the effects. We here present some promising results. Our approach is mainly based on the idea of making more evident the fact that proving a new NP-completeness result is not at all different from designing a new algorithm. Based on this idea, we used tools typically used to teach algorithms (such as automatic program assessment and algorithm visualization systems), accompanied by other activities mainly devoted to augmenting the motivation to study computational complexity and forcing students to think and adopt a standpoint.