Change search
ReferencesLink to record
Permanent link

Direct link
Dynamic programming - structure, difficulties and teaching
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
2013 (English)In: 2013 IEEE Frontiers in Education Conference, New York: IEEE , 2013, 1857-1863 p.Conference paper (Refereed)
Abstract [en]

In this paper we describe action research on our third year Algorithms, Data structures and Complexity course, in which students have considered dynamic programming hard in comparison to the other topics. Attempting to amend this, we wanted to know which difficulties the students encountered, where they gained their knowledge, and which tasks they were most certain that they could perform after the course. Such work resides in the didactics of the subject taught, but the general methods of attacking perceived difficulties in a course can be tried on any course. We identified subtasks that could be taught separately, and adapted the lectures to Pattern Oriented Instruction in order to help students cope with the cognitive complexity of solving problems using dynamic programming. For this, we prepared new clicker questions, visualisations and a lab assignment. We also constructed self-efficacy items on the course goals for dynamic programming, and administered them before and after the teaching and learning activities. Among the self-efficacy items, determining the evaluation order and solving a problem with dynamic programming with no hints had the lowest score after the course. As for the activities, arguing correctness of a solution was something many students claimed that they did not learn anywhere. Students considered the lab exercise most useful, but they also learned a lot from the other activities.

Place, publisher, year, edition, pages
New York: IEEE , 2013. 1857-1863 p.
, Frontiers in Education Conference, ISSN 0190-5848
Keyword [en]
Action research, Cognitive complexity, Evaluation order, General method, Perceived difficulties, Self efficacy, Teaching and learning, Visualisations
National Category
Educational Sciences Computer and Information Science
URN: urn:nbn:se:kth:diva-143472DOI: 10.1109/FIE.2013.6685158ISI: 000330839100389ScopusID: 2-s2.0-84893295842ISBN: 978-1-4673-5261-1OAI: diva2:707493
43rd IEEE Annual Frontiers in Education Conference, FIE 2013; Oklahoma City, OK; United States; 23 October 2013 through 26 October 2013

QC 20140324

Available from: 2014-03-24 Created: 2014-03-21 Last updated: 2014-09-29Bibliographically approved
In thesis
1. On difficult topics in theoretical computer science education
Open this publication in new window or tab >>On difficult topics in theoretical computer science education
2014 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

This thesis primarily reports on an action research project that has been conducted on a course in theoretical computer science (TCS). The course is called Algorithms, data structures, and complexity (ADC) and is given at KTH Royal Institute of Technology in Stockholm, Sweden.

The ADC course is an introduction to TCS, but resembles and succeeds courses introducing programming, system development best practices, problem solving, proving, and logic. Requiring the completion of four programming projects, the course can easily be perceived as a programming course by the students. Most previous research in computer science education has been on programming and introductory courses.

The focus of the thesis work has been to understand what subject matter is particularly difficult to students. In three action research cycles, the course has been studied and improved to alleviate the discovered difficulties. We also discuss how the course design may color students’ perceptions of what TCS is. Most of the results are descriptive.

Additionally, automated assessment has been introduced in the ADC course as well as in introductory courses for non-CS majors. Automated assessment is appreciated by the students and is directing their attention to the importance of program correctness. A drawback is that the exercises in their current form are not likely to encourage students to take responsibility for program correctness.

The most difficult tasks of the course are related to proving correctness, solving complex dynamic programming problems, and to reductions. A certain confusion regarding the epistemology, tools and discourse of the ADC course and of TCS in general can be glimpsed in the way difficulties manifest themselves. Possible consequences of viewing the highly mathematical problems and tools of ADC in more practical, programming, perspective, are discussed. It is likely that teachers could explicitly address more of the nature and discourse of TCS in order to reduce confusion among the students, for instance regarding the use of such words and constructs as “problem”, “verify a solution”, and “proof sketch”.

One of the tools used to study difficulties was self-efficacy surveys. No correlation was found between the self-efficacy beliefs and the graded performance on the course. Further investigation of this is beyond the scope of this thesis, but may be done with tasks corresponding more closely and exclusively to each self-efficacy item.

Didactics is an additional way for a professional to understand his or her subject. Didactics is concerned with the teaching and learning of something, and hence sheds light on that “something” from an angle that sometimes is not reflected on by its professionals. Reflecting on didactical aspects of TCS can enrichen the understanding of the subject itself, which is one goal with this work.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2014. vi, 94 p.
TRITA-CSC-A, ISSN 1653-5723 ; 2014:15
National Category
urn:nbn:se:kth:diva-152357 (URN)978-91-7595-267-3 (ISBN)
Public defence
2014-10-17, F3, Lindstedtsvägen 26, KTH, Stockholm, 14:00 (English)

QC 20140929

Available from: 2014-09-29 Created: 2014-09-25 Last updated: 2014-09-29Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Enström, Emma
By organisation
Theoretical Computer Science, TCS
Educational SciencesComputer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 43 hits
ReferencesLink to record
Permanent link

Direct link