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.

Subject headings

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Sciences (hsv//eng)

SAMHÄLLSVETENSKAP  -- Utbildningsvetenskap -- Lärande (hsv//swe)

SOCIAL SCIENCES  -- Educational Sciences -- Learning (hsv//eng)

Keyword

Algorithm visualization

Assessment

NP-completeness

Self-efficacy

Action research

Automatic programs

Diverse applications

Self efficacy

Algorithms

Engineering research

Students

Teaching

Formal logic

Publication and Content Type

ref (subject category)

kon (subject category)