Back to Search
Start Over
Identification and addressing reduction-related misconceptions
- Source :
- Computer Science Education. 26:89-103
- Publication Year :
- 2016
- Publisher :
- Informa UK Limited, 2016.
-
Abstract
- Reduction is one of the key techniques used for problem-solving in computer science. In particular, in the theory of computation and complexity (TCC), mapping and polynomial reductions are used for analysis of decidability and computational complexity of problems, including the core concept of NP-completeness. Reduction is a highly abstract technique that involves revealing close non-trivial connections between problems that often seem to have nothing in common. As a result, proper understanding and application of reduction is a serious challenge for students and a source of numerous misconceptions. The main contribution of this paper is detection of such misconceptions, analysis of their roots, and proposing a way to address them in an undergraduate TCC course. Our observations suggest that the main source of the misconceptions is the false intuitive rule “the bigger is a set/problem, the harder it is to solve”. Accordingly, we developed a series of exercises for proactive prevention of these mis...
- Subjects :
- Theoretical computer science
General Computer Science
Computational complexity theory
Concept map
Computer science
05 social sciences
050301 education
02 engineering and technology
Data science
Education
Decidability
Reduction (complexity)
Identification (information)
020204 information systems
Theory of computation
ComputingMilieux_COMPUTERSANDEDUCATION
0202 electrical engineering, electronic engineering, information engineering
Key (cryptography)
Set (psychology)
0503 education
Subjects
Details
- ISSN :
- 17445175 and 08993408
- Volume :
- 26
- Database :
- OpenAIRE
- Journal :
- Computer Science Education
- Accession number :
- edsair.doi...........69e2389b7c1e3e752a69d75c59cf1fd9