From theory to practice: NP-completeness for every CS student
2013 (English)In: ITiCSE '13 Proceedings of the 18th ACM conference on Innovation and technology in computer science education, Association for Computing Machinery (ACM), 2013, 16-21 p.Conference paper (Refereed)
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.
Place, publisher, year, edition, pages
Association for Computing Machinery (ACM), 2013. 16-21 p.
, Annual Conference on Innovation and Technology in Computer Science Education, ITiCSE, ISSN 1942-647X
Algorithm visualization, Assessment, NP-completeness, Self-efficacy, Action research, Automatic programs, Diverse applications, Self efficacy, Algorithms, Engineering research, Students, Teaching, Formal logic
Computer Science Learning
IdentifiersURN: urn:nbn:se:kth:diva-133890DOI: 10.1145/2462476.2465582ScopusID: 2-s2.0-84881120385ISBN: 978-145032078-8OAI: oai:DiVA.org:kth-133890DiVA: diva2:663426
18th ACM Conference on Innovation and Technology in Computer Science Education, ITiCSE 2013, 1 July 2013 through 3 July 2013, Canterbury
QC 201311112013-11-112013-11-112014-09-29Bibliographically approved