Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Iteratively Intervening with the “Most Difficult” Topics of an Algorithms and Complexity Course
KTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.
KTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.ORCID-id: 0000-0003-3199-8953
2017 (engelsk)Inngår i: ACM Transactions on Computing Education, ISSN 1946-6226, E-ISSN 1946-6226, Vol. 17, nr 1, artikkel-id 4Artikkel i tidsskrift (Fagfellevurdert) 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.

sted, utgiver, år, opplag, sider
ACM Digital Library, 2017. Vol. 17, nr 1, artikkel-id 4
Emneord [en]
reductions, algorithm visualization, assessment, dynamic programming, NP-completeness, pattern-oriented instruction, proofs, self-efficacy
HSV kategori
Forskningsprogram
Teknikvetenskapens lärande och kommunikation
Identifikatorer
URN: urn:nbn:se:kth:diva-201638DOI: 10.1145/3018109ISI: 000395525500004Scopus ID: 2-s2.0-85011418973OAI: oai:DiVA.org:kth-201638DiVA, id: diva2:1073600
Merknad

QC 20170308

Tilgjengelig fra: 2017-02-12 Laget: 2017-02-12 Sist oppdatert: 2017-11-29bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekstScopushttp://dl.acm.org/citation.cfm?id=3018109

Søk i DiVA

Av forfatter/redaktør
Enström, EmmaKann, Viggo
Av organisasjonen
I samme tidsskrift
ACM Transactions on Computing Education

Søk utenfor DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric

doi
urn-nbn
Totalt: 143 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf