Analyzing Student Practices in Theory of Computation in Light of Distributed Cognition Theory

ABSTRACT

This paper describes a qualitative study investigating how undergraduate CS majors solved assignments from a Theory of Computation (ToC) course in individually-formed study groups. We use Distributed Cognition Theory as the underlying theoretical framework and ask two research questions: 1) How do students use mathematical notations to work on their assignment, and 2) how and by which means do students assure themselves that their approach is correct? We observed 12 undergraduate CS majors tasked with developing a proof for NP-completeness working in three study groups. Data collected in this study points to students' lack of working proficiency, especially with regard to creating mathematical inscriptions, as a key aspect in their difficulties in solving ToC assignments. This result is significant because it highlights the need to reexamine widely used assumptions about reasons for students' difficulties with ToC, e.g., lack of interest due to abstract and theoretical nature of ToC.

References

1. Armoni, M., Rodgers, S., Vardi, M., and Verma, R. 2006. Automata theory - its relevance to computer science students and course content. SIGCSE Bulletin. 38, 1, 197--198.
2. Berque, D., Johnson, D., and Jovanovic, L. 2001. Teaching theory of computation using pen-based computers and an electronic whiteboard. ACM SIGCSE Bulletin, 33, 3, 169--172.
3. Chesñevar, C., González, M., and Maguitman, A. 2004. Didactic strategies for promoting significant learning in formal languages and automata theory. In Proceedings of the 9th annual SIGCSE conference on Innovation and technology in computer science education. ITiCSE '04. ACM, 7--11.
4. Chudá, D. 2007. Visualization in Education of Theoretical Computer Science. In Proceedings of the 2007 international conference on Computer systems and technologies. CompSysTech '07. 84.
5. Cormen, T., Stein, C., Rivest, R., and Leiserson, C. 2009. Introduction to Algorithms. McGraw-Hill Higher Education, 3rd edition.
6. Crescenzi, P., Enström, E., and Kann, V. 2013. From theory to practice: NP-completeness for every CS student. In Proceedings of the 18th ACM conference on Innovation and technology in computer science education. ITiCSE '13. ACM, 16--21.
7. Cutts, Q., Esper, S., Fecho, M., Foster, S., Simon, B. 2012. The Abstraction Transition Taxonomy: Developing Desired Learning Outcomes through the Lens of Situated Cognition. In Proceedings of the ninth annual International Conference on International Computing Education Research. ICER '12. ACM, 63--70.
8. Deitrick, E., Shapiro, B., Ahrens, M., Fiebrink, R., Lehrman, P., and Farooq, S. 2015. Using Distributed Cognition Theory to Analyze Collaborative Computer Science Learning. In Proceedings of the eleventh annual International Conference on Computing Education Research. ICER '15. ACM, 51--60.
9. Devedzic, V., Debenham, J., and Popvic D. 2000. Teaching Formal Languages by an Intelligent Tutoring System. Educational Technology and Society 3, 2, ISSN 1436--4522.
10. García-Osorio, C., Mediavilla-Sáiz, I., Jimeno-Visitación, J., and García-Pedrajas, N. 2008. Teaching push-down automata and turing machines. ACM SIGCSE Bulletin, 40, 3.
11. Goldreich, O. 2006. On teaching the basics of complexity theory, Theoretical Computer Science: Essays in Memory of Shimon Even. Springer-Verlag, Berlin.
12. Habiballa, H. and Kmet, T. 2004. Theoretical branches in teaching computer science. International Journal of Mathematical Education in Science and Technology. 35, 6, 829--841
13. Hämäläinen, W. 2004. Problem-based learning of theoretical computer science. In Proceedings of the 34th ASEE/IEEE Frontiers in Education Conference. S1H/1 -S1H/6 Vol. 3.
14. Hielscher, M. and Wagenknecht. C. 2006. AtoCC: learning environment for teaching theory of automata and formal languages. In Proceedings of the 11th annual SIGCSE conference on Innovation and technology in computer science education. ITICSE '06. ACM, 306--306.
15. Hollan, J., Hutchins, E., & Kirsh, D. 2001. Distributed Cognition: Toward a New Foundation for Human-Computer Interaction Research. Human-Computer Interaction in the New Millennium. Carroll, M., Eds., ACM Press, New York, 75--94.
16. Hopcroft, J., Motwani, R., and Ullman, J. 2006. Introduction to Automata Theory, Languages, and Computation. 3rd Edition, Pearson.
17. Hutchins, E. 1995. Cognition in the wild. Bradford: MIT Press.
18. Knobelsdorf, M. 2015. The Theory Behind Theory - Computer Science Education Research Through the Lenses of Situated Learning. In Proceedings of the 8th International Conference on Informatics in Schools: Situation, Evolution, and Perspectives (ISSEP), Lecture Notes in Computer Science, Volume 9378, Springer, 21--21.
19. Knobelsdorf, M., Kreitz, C., and Böhne, S. 2014. Teaching theoretical computer science using a cognitive apprenticeship approach. In Proceedings of the 45th ACM technical symposium on Computer science education. SIGCSE '45. ACM, New York, 67--72.
20. Korte, L., Anderson, S., Pain, H., and Good, J. 2007. Learning by game-building: a novel approach to theoretical computer science education. In Proceedings of the 12th annual SIGCSE conference on Innovation and technology in computer science education. ITiCSE '07. ACM, 53--57.
21. Lincoln, Y., and Guba, E. 1985. Naturalistic Inquiry. Sage Publications. Newbury Park, California.
22. Mayring. P. 2000. Qualitative Content Analysis. Forum: Qualitative Social Research {Online Journal}, 1, 2, Art. 20.
23. Parker, M. and Lewis, C. 2014. What makes big-O analysis difficult: understanding how students understand runtime analysis. Journal of Computing Sciences in Colleges.29, 4, 164--174.
24. Pea, R. 1993. Practices of distributed intelligence and designs for education. In Distributed cognitions: Psychological and educational considerations. G. Salomon, Ed. Cambridge: Cambridge University Press, 47--87.
25. Perkins, D. 1993. Person-plus: A distributed view of thinking and learning. In Distributed cognitions: Psychological and educational considerations. G. Salomon, Ed. Cambridge: Cambridge University Press, p. 88--110.
26. Pillay, N. 2009. Learning Difficulties Experienced by Students in a Course on Formal Languages and Automata Theory. SIGCSE Bulletin. 41, 4, 48--52.
27. Rodger, S. H., Bressler, B., Finley, T., and Reading, S. 2006. Turning automata theory into a hands-on course. In Proceedings of the 37th SIGCSE technical symposium on Computer science education. SIGCSE '06. ACM, 379--383.
28. Säljö, R. 1998. Learning as the use of tools: a sociocultural perspective on the human-technology link. In Learning with computers. Littleton, K. and Light, P., Ed. Routledge, New York, 144--161.
29. Sigman, S. 2007. Engaging students in formal language theory and theory of computation. SIGCSE Bulletin. 39, 1, 450--453.
30. Tenenberg, J. and Knobelsdorf, M. 2013. Out of our minds: a review of sociocultural cognition theory. Computer Science Education. 24, 1, 1--24.
31. Verma, R. 2005. A visual and interactive automata theory course emphasizing breadth of automata. In Proceedings of the 10th Annual SIGCSE Conference on innovation and Technology in Computer Science Education. ITiCSE '05. ACM, 325--329.
32. Vygotsky, L. S. 1978. Mind in Society: The Development of Higher Psychological Processes: Harvard University Press.
33. Wermelinger, M. and Dias, A. 2005. A prolog toolkit for for-mal languages and automata, ACM SIGCSE Bulletin. 37, 3.
34. Wertsch, J. V. 1993. Voices of the Mind: Sociocultural Approach to Mediated Action. Harvard University Press.
35. Zingaro, Z. 2008. Another approach for resisting student resistance to formal methods, ACM SIGCSE Bulletin, 40, 4.

Index Terms

• Social and professional topics

  • Professional topics

    • Computing education

      • Computing education programs

        • Computer science education