Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Iteratively Intervening with the “Most Difficult” Topics of an Algorithms and Complexity Course
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0003-3199-8953
2017 (English)In: ACM Transactions on Computing Education, ISSN 1946-6226, E-ISSN 1946-6226, Vol. 17, no 1, article id 4Article in journal (Refereed) Published
Abstract [en]

When compared to earlier programming and data structure experiences that our students might have, the perspective changes on computers and programming when introducing theoretical computer science into the picture. Underlying computational models need to be addressed, and mathematical tools employed, to understand the quality criteria of theoretical computer science. Focus shifts from doing to proving. Over several years, we have tried to make this perspective transition smoother for the students of a third-year mandatory algorithms, data structures, and computational complexity course. The concepts receiving extra attention in this work are NP-completeness, one of the most central concepts in computer science, and dynamic programming, an algorithm construction method that is powerful but somewhat unintuitive for some students.

The major difficulties that we attribute to NP-completeness are that the tasks look similar but have a different purpose than in algorithm construction exercises. Students do not immediately see the usefulness of the concept, and hence motivation could be one issue. One line of attacking NP-completeness has been to emphasize its algorithmic aspects using typical tools for teaching algorithms.

Some potential difficulties associated with dynamic programming are that the method is based on a known difficult concept—recursion—and that there are many ingredients in a dynamic programming solution to a problem.

For both dynamic programming and NP-completeness, we have invented several new activities and structured the teaching differently, forcing students to think and adopt a standpoint, and practice the concepts in programming assignments. Student surveys show that these activities are appreciated by the students, and our evaluations indicate that they have positive effects on learning. We believe that these activities could be useful in any similar course.

The approach to improving the course is action research, and the evaluation has been done using course surveys, self-efficacy surveys, rubrics-like grading protocols, and grades. We have also interviewed teaching assistants about their experiences.

Place, publisher, year, edition, pages
ACM Digital Library, 2017. Vol. 17, no 1, article id 4
Keywords [en]
reductions, algorithm visualization, assessment, dynamic programming, NP-completeness, pattern-oriented instruction, proofs, self-efficacy
National Category
Didactics
Research subject
Education and Communication in the Technological Sciences
Identifiers
URN: urn:nbn:se:kth:diva-201638DOI: 10.1145/3018109ISI: 000395525500004Scopus ID: 2-s2.0-85011418973OAI: oai:DiVA.org:kth-201638DiVA, id: diva2:1073600
Note

QC 20170308

Available from: 2017-02-12 Created: 2017-02-12 Last updated: 2017-11-29Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopushttp://dl.acm.org/citation.cfm?id=3018109

Search in DiVA

By author/editor
Enström, EmmaKann, Viggo
By organisation
Theoretical Computer Science, TCS
In the same journal
ACM Transactions on Computing Education
Didactics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 84 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf