Emma Enström, Viggo Kann
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.