Abstract
Understanding the notional machine that conceptually executes a program is a crucial step towards mastery of computer programming. In order to help students build a mental model of the notional machine, visible and tangible computing agents might be of great value, as they provide the student with a conceptual model of who or what is doing the actual work. In addition to programming, the concept of a notional machine is equally important when teaching algorithmic design, complexity theory, or computational thinking. We therefore propose to use a common computing agent as notional machine to not only introduce programming, but also discuss algorithms and their complexity.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abelson, H., DiSessa, A.: Turtle Geometry. MIT Press, Cambridge (1981)
Bell, T., Andreae, P., Lambert, L.: Computer science in New Zealand high schools. In: Proceedings of ACE 2010 (2010)
Bell, T., Witten, I., Fellows, M.: CS unplugged - computer science without a computer. http://csunplugged.org. Accessed 17 Sept 2017
Bell, T., Rosamond, F., Casey, N.: Computer science unplugged and related projects in math and computer science popularization. In: Bodlaender, H.L., Downey, R., Fomin, F.V., Marx, D. (eds.) The Multivariate Algorithmic Revolution and Beyond. LNCS, vol. 7370, pp. 398–456. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-30891-8_18
Bell, T., Alexander, J., Freeman, I., Grimley, M.: Computer science unplugged: school students doing real computing without computers. N. Z. J. Appl. Comput. Inf. Technol. 13, 01 (2009)
Caspersen, M.E., Christensen, H.B.: Here, there and everywhere - on the recurring use of turtle graphics in CS1. In: Proceedings of ACSE 2000 (2000)
Du Boulay, B.: Some difficulties of learning to program. J. Educ. Comput. Res. 2(1), 57–73 (1986)
Gallenbacher, J.: Abenteuer Informatik, 4th edn. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-662-53965-1
Hartmann, W., Nievergelt, J., Reichert, R.: Kara, finite state machines, and the case for programming as part of general education. In: Proceedings of the IEEE 2001 Symposia on Human Centric Computing Languages and Environments (HCC 2001), p. 135. IEEE Computer Society, Washington, DC (2001)
Hromkovič, J., Kohn, T., Komm, D., Serafini, G.: Combining the power of python with the simplicity of logo for a sustainable computer science education. In: Brodnik, A., Tort, F. (eds.) ISSEP 2016. LNCS, vol. 9973, pp. 155–166. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-46747-4_13
Kelleher, C., Pausch, R.: Lowering the barriers to programming: a taxonomy of programming environments and languages for novice programmers. ACM Comput. Surv. 37(2), 83–137 (2005)
Kölling, M.: The greenfoot programming environment. Trans. Comput. Educ. 10(4), 14:1–14:21 (2010)
Komm, D., Kohn, T.: An introduction to running time analysis for an SOI workshop. Olymp. Inform. 11, 77–86 (2017)
Lawrence, A.W., Badre, A.M., Stasko, J.T.: Empirically evaluating the use of animations to teach algorithms. In: Proceedings of 1994 IEEE Symposium on Visual Languages, pp. 48–54, October 1994
Lewis, C.M.: How programming environment shapes perception, learning and goals: Logo vs. Scratch. In: Proceedings of the 41st ACM Technical Symposium on Computer Science Education, SIGCSE 2010, pp. 346–350. ACM, New York (2010)
Lister, R.: Concrete and other neo-Piagetian forms of reasoning in the novice programmer. In: Proceedings of the Thirteenth Australasian Computing Education Conference, ACE 2011, vol. 114, pp. 9–18. Australian Computer Society Inc., Darlinghurst (2011)
Ma, L., Ferguson, J., Roper, M., Wood, M.: Investigating and improving the models of programming concepts held by novice programmers. Comput. Sci. Educ. 21(1), 57–80 (2011)
O’Neill, M.E.: The genuine sieve of Eratosthenes. J. Funct. Program. 19(1), 95–106 (2009)
Papert, S.: Mindstorms: Children, Computers, and Powerful Ideas. Harvester Press, Brighton (1980)
Resnick, M., et al.: Scratch: programming for all. Commun. ACM 52(11), 60–67 (2009)
Rodger, S.H., et al.: Enhancing K-12 education with Alice programming adventures. In: Proceedings of the Fifteenth Annual Conference on Innovation and Technology in Computer Science Education, ITiCSE 2010, pp. 234–238. ACM, New York (2010)
Schumacher, R.M., Czerwinski, M.P.: Mental models and the acquisition of expert knowledge. In: Hoffman, R.R. (ed.) The Psychology of Expertise, pp. 61–79. Springer, New York, New York (1992). https://doi.org/10.1007/978-1-4613-9733-5_4
Sorva, J.: Notional machines and introductory programming education. Trans. Comput. Educ. 13(2), 8:1–8:31 (2013)
Sorva, J., Lönnberg, J., Malmi, L.: Students’ ways of experiencing visual program simulation. Comput. Sci. Educ. 23(3), 207–238 (2013)
Teague, D., Lister, R.: Manifestations of preoperational reasoning on similar programming tasks. In: Proceedings of the Sixteenth Australasian Computing Education Conference, ACE 2014, vol. 148, pp. 65–74. Australian Computer Society Inc., Darlinghurst (2014)
D. D. Thornburg Friends of the Turtle: On Logo and Turtles. Compute! (1983)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Appendices
A Python Programs
B Quicksort
For Quicksort, the turtle assumes the colour of the first dot it encounters, and then compares the colours of all subsequent dots to its own colour (the pivot colour). Dots with a colour hue that is smaller (or equal) are placed to the left, those with larger colour hue are placed to the right (see Program 4 and Fig. 3). As long as more than one dot remains in any stack, the procedure is repeated recursively.
In our implementation of Quicksort, the turtle takes the colour of the first dot at the bottom as the pivot. It then moves all dots either to the left or to the right, creating two new columns to be sorted afterwards. (Color figure online)
An alternative implementation of Quicksort, where the dots are arranged horizontally. Each pivot colour is dropped to the bottom after the sorting step: due to the gap between the left and the right hand side, its position in the result is already known. At the very bottom, the final solution is shown. (Color figure online)
Instead of arranging the dots as vertical stacks as in Fig. 3, it is also possible to arrange the coloured dots as horizontal lines as in Fig. 4. Note that the line on the right side grows from right to left, leading to the order of the dots being reversed on each step. Since the pivot dot is neither added to the left, nor the right hand side, a gap forms in between the two sides. While an implementation without additional variables is, in principle, feasible, the search for the right spot to place the new dot might take a large amount of both program code, and execution time.
So far, we have never progressed in class enough to actually discuss Python code of Quicksort as shown in Program 4. The use of recursion makes a discussion on entry level difficult (it is possible to do it without recursion, but this does not necessarily lead to better understandable program code). However, we have presented the horizontal version several times as a basis for further discussion, with great results: students often realised, for instance, that the algorithm works best if the pivot colour divides the dots into two lines, or piles, of approximately equal size, and fails to be efficient for dots, “which are sorted in reverse” (it seems that the idea of sorting an already sorted line does not necessarily occur to high school students).
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Kohn, T., Komm, D. (2018). Teaching Programming and Algorithmic Complexity with Tangible Machines. In: Pozdniakov, S., Dagienė, V. (eds) Informatics in Schools. Fundamentals of Computer Science and Software Engineering. ISSEP 2018. Lecture Notes in Computer Science(), vol 11169. Springer, Cham. https://doi.org/10.1007/978-3-030-02750-6_6
Download citation
DOI: https://doi.org/10.1007/978-3-030-02750-6_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-02749-0
Online ISBN: 978-3-030-02750-6
eBook Packages: Computer ScienceComputer Science (R0)