=Paper=
{{Paper
|id=Vol-1910/paper0105
|storemode=property
|title=Tangibles for Graph Algorithmic Thinking: Research Questions and Work-in-Progress
|pdfUrl=https://ceur-ws.org/Vol-1910/paper0105.pdf
|volume=Vol-1910
|authors=Andrea Bonani
|dblpUrl=https://dblp.org/rec/conf/chitaly/Bonani17
}}
==Tangibles for Graph Algorithmic Thinking: Research Questions and Work-in-Progress==
https://ceur-ws.org/Vol-1910/paper0105.pdf
Tangibles for Graph Algorithmic Thinking:
Research Questions and Work-in-Progress
Andrea Bonani (supervision: V. Del Fatto, G. Dodero, R. Gennari)
Free University of Bozen-Bolzano, Piazza Domenicani 3, 39100 Bolzano, Italy
abonani@unibz.it
Abstract. Algorithmic thinking is at the hearth of the best known com-
putational thinking. It requires the abilities to decompose and model a
problem with a certain representation, and devise or understand an algo-
rithm for making a computer solve it. Such abilities are rather abstract
and thus algorithmic thinking is often neglected in primary and mid-
dle schools. This research picks up the challenge of designing interactive
tangible objects, enhanced by Internet of Things technologies, that can
help children in mastering algorithmic thinking. The research reported in
this paper focusses on graph algorithmic thinking, the latest prototype
of tangibles for graph algorithmic thinking and its usage in the field.
Keywords: Algorithmic Thinking; Interaction Design; Interactive Tan-
gible Objects
1 Introduction
1.1 Setting
Computational Thinking (CT ) [18] refers to a pool of abilities necessary to ab-
stract away a problem and represent it in a format amenable for computers to
process. It takes four main abilities: decomposition and modelling; pattern recog-
nition; pattern generalisation and abstraction; algorithm design. At the core of
CT abilities, one can recognise the less known Algorithmic Thinking (AT ) abil-
ities. Thinking algorithmically means being able to decompose a problem into
essential components and model it with a certain representation, so as to give
step-by-step instructions to make a computer solve it (an algorithm) [11].
Graph AT is the focus of the PhD work presented in this paper. In short,
a(n undirected) graph is a rather general representation format. It consists in
an ordered pair G = (V, E), with V = {v1 , . . . , vn } the set of nodes, and E =
{{vi , vj } | vi , vj ∈ V } the set of edges between pairs of nodes. Graph AT requires
to decompose and model a problem with a graph, and to explore or envisage
algorithms for resolving it. Example problems, familiar to all, are given by social
networks, of Facebook friends or classmate friends. Problems concerning such
social networks can be decomposed and modelled with graphs. People can be
modelled as nodes, and edges between nodes can be used to represent friendship
relations. Possible problems are: is there a way to connect a person, A, to another,
B, through a chain (a path) of mutual friends? If not, how can one connect all
the given people? In other words, how can one devise an algorithm for that?
1.2 Research Problem and Rationale
As the above examples show, understanding graphs and modelling problems with
graphs are prerequisites for exploring and devising graph algorithms. However,
they are rather abstract things for primary and middle school children to carry
out. And yet CT and AT in particular are nowadays considered fundamental
skills for those children as well.
For primary and middle school children, interactive tangibles for teaching
graph AT can be of help: tangibles could foster the interplay between abstraction
and concreteness, thus helping even the youngest to learn through multi-sensory
experiences, and be actively engaged in the experiences. This paper is based on
the idea of designing and using interactive tangible objects for graph algorithmic
thinking (briefly, graph AT tangibles), with and for primary and middle schools,
so as to promote multi-modal learning of graph AT and engaging all children
actively in the process. Such tangibles can be developed so as to exploit current
Internet of Things (IoT) technologies.
The design of graph AT tangibles is however highly complex: they should help
children grasp abstract concepts, promote multi-modal learning and be engaging.
It takes a specific design methodology that brings tangibles in the field, which
makes design advance through children’s usage of tangibles, and children learn
through the process. In other words, it takes a design approach that moves into
specific real contexts and brings all participants clear benefits.
1.3 Paper Outline
The paper starts presenting current work in the area of AT learning and tangible
design with users. Starting from this, it frames the main research questions of
the PhD. Then it overviews and explains the adopted design methodology and
process. It presents the current prototype design and the latest usage in the
field, with primary and middle school children. Results are still under analysis
and thus the reported findings are work in progress. The paper concludes with
reflections for future work in the area of tangible design and AT for children.
2 Related Research Work
2.1 Computational and Algorithmic Thinking
Literature on computer science education highlights three main categories of
approaches to teaching CT, in general, and AT, in particular: (1) without com-
puters; (2) by coding, with computers; (3) with interactive tangible objects.
Perhaps the best known approaches to AT education are based on coding,
with programming environments for children, such as Scratch [17]. Proposals
such as CS-unplugged by Bell [2], instead, teach CT without computers: they
require physical activities, using everyday materials like paper and pencil. CS-
unplugged has inspired several researchers, including Gibson, who taught graph
modeling and algorithms through physical non-interactive objects [15].
Relevant related work for AT education can also be found in the area of in-
teraction design of tangibles, e.g., [3,16]. Proposals to teach algorithms through
the use of tangibles have increased in recent years. A significant reference is [14],
where a gamified tangible for primary schools is presented, BALA, for the scaf-
folding of a sorting algorithm. Therein, gamification is used for creating probe
versions of tangibles for children as in [12,9,13].
2.2 Tangible Design with Users
Design solutions for social contexts, such as school contexts, are subject to evo-
lution, and meta-design has been proposed as a suitable design approach for
them [10]. Meta-design and other end-user development approaches, such as [7],
do not provide fixed solutions but a framework within which end users and
designers alike can continuously contribute to the development. An interesting
study of meta-design for end-user development of smart environments is reported
in [8].
In spite of their potentials, so far meta-design or other end-user development
approaches have been scarcely used for tangibles over long periods of time, in a
continuous manner, as done for instance in [14]. The former is a participatory
design study over time with children and teachers of tangibles for socio-emotional
learning. The latter describes the CoDICE software that enables designers to
trace the rationale of co-design decisions. The participatory design of this paper
shares the same concern of enabling a continuous evolution of graph AT tangibles
over time, by working with the users of tangibles and bringing them benefits:
children and teachers.
The adopted participatory design of graph AT tangibles is essentially an
action-research process, evolving over time through rapid prototype solutions
and usage in the field with users. The related research questions and process are
discussed in the following.
3 Research Questions and Methodology
3.1 Research Questions
The primary goal of my Ph.D. research is how to design graph AT tangibles for
primary and middle school children, focusing on the Italian context. To achieve
my research goal, my research work is framed around two main research ques-
tions: (RQ1) How can one rapidly design graph AT tangibles for children, focus-
ing on Italian contexts, so as to provide the involved children with an engaging
learning experience during the design process? (RQ2) What are the character-
istics of graph AT tangibles adequate for different learning contexts?
The first research question, RQ1, is tackled by adopting the research method-
ology and design process explained in the following. The second research ques-
tion, RQ2, will be tackled at the end of the PhD by cumulating over the research
experience and drafting guidelines for the design of such tangibles.
3.2 Research Methodology and Design Process
Given the aforementioned research goals, the PhD research involves users contin-
uously, so as to transform learning “by empowering all people to become active
contributors” [10]. Design is based on action research, which aims at bringing
benefits to all participants, especially users of tangibles. In case of graph AT
tangibles, users are teachers and their 9–13 years old pupils, from primary and
middle schools.
The design process spirals through: (1) planning of tangibles, (2) acting in
the field for (3) reflecting about their users’ usage. It proceeds through prototype
solutions, conceived as intermediary objects in the sense of [6], which are used
in studies with designers and users for detecting usability issues, exploring novel
design possibilities as well as creating learning possibilities for users.
To this end, tangibles are open-ended for unexpected usage and with few
functionalities, critical to assess. Early solutions take the form of probes, which
should be cheap and easy to abandon solutions, or solutions that can rapidly
evolve into interactive prototypes over time, introducing small changes. The
rationale for this spiral process is that solutions like graph AT tangibles, which
are for social contexts, can be studied best by introducing small changes into
these processes and observing the effects of these changes in it over time [1].
The design process started with an exploratory context of use analysis, which
triggered the first alternative design ideas, assessed with interaction design ex-
perts. After building a first vertical prototype of a tangible for AT (with few criti-
cal functionalities implemented and open for appropriations and rapid changes),
designers and users participated in two studies in informal learning contexts,
see [4,5] respectively. Tangibles were rapidly assessed and redesigned according
to the results of studies. For instance, new learning scenarios for primary and
middle schools were developed together with teachers. New design features were
added after studies with children.
4 Recent Prototype and Scenarios
The latest prototype of graph AT tangibles is made of wood, cables and micro-
electronics components. The prototype adopts a distributed client-server archi-
tecture, with a WiFi connection.
The server is a computer that verifies graph properties according to an en-
visioned learning scenario. Prototypes of graph AT tangibles, in fact, are used
together with learning scenarios: scenarios challenge children to model or al-
gorithmically solve with tangibles specific problems, e.g., friendship relations
among people and how to connect isolated people. Moreover, besides verifying
the properties envisioned by a learning scenario, the server implements a graph-
ical user interface (GUI) for teachers, which allows them to select a specific
learning scenario. The GUI is not discussed in this paper as it is not the main
research focus of this contribution.
Clients, which are the tangibles for children, interact with the server and
children through micro-electronic components. Currently, each node is equipped
with an RGB node LED and three RGB edge LEDs, besides other microelec-
tronics components. RGB node LEDs are activated for giving specific types of
feedback, e.g., RGB node LEDs of a strongly connected component switch on
with the same color. Each node has three sockets for cables, and in parallel
three RGB edge LEDs. The edge LEDs are activated when a cable is inserted
in its socket, or for delivering other types of feedback concerning edges, e.g., in
a simple graph there is only one edge between a pair of nodes. Edges, which
are Ethernet cables, are just passive links, and presently provide no interaction.
A confirmation button is also part of the prototype; it can only be pressed by
children for signalling that they think that they have concluded their learning
scenario. See Fig. 1.
Example learning scenarios are compactly presented below.
The first scenario aims at making children construct a simple graph. Chil-
dren are presented a situation to model, e.g., friendship relations in their
class. Children start labelling nodes with classmates’ names, e.g., see Fig. 2.
When a child introduces a loop or parallel edges, LED lights switch on,
blinking red, to signal error.
The second scenario aims at making children construct a connected graph.
Children are presented a situation modelled with graph AT tangibles, e.g.,
friendship relations in their class, with isolated classmates. Children are
not told that there are isolated classmates and are instead asked to push
the confirmation button: strongly connected components, that is, isolated
groups of classmates, blink with different colours, e.g., see Fig. 1. Children
are then asked to tell what that means in relation to the given problem.
Then Children can connect strongly connected components by means of
cables. In order to verify that the graph is finally connected, children can
push again the confirmation button and see that the graph AT tangibles are
all coloured green.
The scenarios were used in two studies: one with 8 middle school children,
all in the age range 12–13 years old; another one with 3 primary school children,
all in the age range 10–11 years old. See Fig. 2.
Qualitative data were gathered via designers’ field notes and videos, con-
cerning children’s user experience with tangibles, their understanding of graph
AT and engagement in the experience. Understanding of graph AT was further
investigated through a written survey delivered at the end of the experience.
The results of the studies are still under analysis but preliminary findings
are available and generally positive. All children succeeded in using tangibles
for modelling the situation proposed by the first learning scenario. However,
primary-school children required scaffolding support by designers to understand
what simple graphs are: designers asked them to repeat the learning scenario
with examples until children understood what simple graphs are. Interestingly,
whereas middle-school children did not notice LED lights for edges, primary-
school children immediately noted them and recognised them as pertaining to
edges.
In relation to the second scenario, again, no critical usability issue was re-
ported. All children understood that differently coloured nodes were isolated
groups of friends, that is, different strongly connected components. Interestingly,
only one child from the middle school, on his own, devised an optimal strategy
for connecting the graph—working on a single node per strongly connected com-
ponent.
Fig. 1: Nodes of a graph with two strongly connected components
5 Conclusions
The paper elaborated on the notion of graph AT tangibles, which can aid in the
scaffolding of AT through an active multi-modal experience. The design of such
tangibles is based on action-research approach, spiralling through rapid proto-
type solutions and studies with users. Teachers, children (users) and designers
co-discover design and learning possibilities by using and modifying tangibles
and scenarios.
Currently, were are moving the design and usage of such tangibles one step
forward: towards more complex learning scenarions requiring spanning trees.
References
1. Baskerville, R.L.: Investigating Information Systems with Action Research. Com-
mun. AIS 2(3es) (Nov 1999), http://dl.acm.org/citation.cfm?id=374468.
374476
Fig. 2: Children using the graph AT tangibles for modelling friendship relations
in their class
2. Bell, T., Alexander, J., Freeman, I., Grimley, M.: Computer science without com-
puters: new outreach methods from old tricks. In: Proc. of the 21st Annual Con-
ference of the National Advisory Committee on Computing Qualifications (2008)
3. Bers, M.U., Flannery, L., Kazakoff, E.R., Sullivan, A.: Computational thinking
and tinkering: Exploration of an early childhood robotics curriculum. Computers
& Education 72, 145–157 (2014)
4. Bonani, A., Del Fatto, V., Dodero, G., Gennari, R., Raimato, G.: First Steps
Towards the Design of Tangibles for Graph Algorithmic Thinking, pp. 110–117.
Springer International Publishing, Cham (2017), http://dx.doi.org/10.1007/
978-3-319-60819-8_13
5. Bonani, A., Del Fatto, V., Dodero, G., Gennari, R., Raimato, G.: Participatory
Design of Tangibles for Graphs: A Small-Scale Field Study with Children, pp.
161–168. Springer International Publishing, Cham (2018), http://dx.doi.org/
10.1007/978-3-319-61322-2_16
6. Cabitza, F., Fogli, D., Piccinno, A.: “Each to His Own”: Distinguishing Activi-
ties, Roles and Artifacts in EUD Practices, pp. 193–205. Springer International
Publishing, Cham (2014)
7. Costabile, M.F., Fogli, D., Mussio, P., Piccinno, A.: Visual interactive systems for
end-user development: A model-based design methodology. IEEE Transactions on
Systems, Man, and Cybernetics - Part A: Systems and Humans 37(6), 1029–1046
(Nov 2007)
8. Desolda, G., Ardito, C., Matera, M.: Empowering end users to customize their
smart environments: Model, composition paradigms, and domain-specific tools.
ACM Trans. Comput.-Hum. Interact. 24(2), 12:1–12:52 (Apr 2017), http://doi.
acm.org/10.1145/3057859
9. Dodero, G., Gennari, R., Melonio, A., Torello, S.: “There is No Rose Without
A Thorn”: An Assessment of a Game Design Expereience for Children. In: 11th
Edition of CHItaly, the biannual Conference of the Italian SIGCHI Chapter. (2015)
10. Fischer, G., Fogli, D., Piccinno, A.: Revisiting and Broadening the Meta-Design
Framework for End-User Development. In: Paterno, F., Wulf, V. (eds.) New Per-
spectives in End User Development. Kluwer (2017)
11. Futschek, G.: Algorithmic thinking: the key for understanding computer science.
In: Informatics education–the bridge between using and understanding computers,
pp. 159–168. Springer (2006)
12. Gennari, R., Melonio, A., Raccanello, D., Brondino, M., Dodero, G., Pasini,
M., Torello, S.: Children’s emotions and quality of products in partici-
patory game design. International Journal of Human Computer Studies,
year=2017 101, 45–61, https://www.scopus.com/inward/record.uri?eid=
2-s2.0-85011661549&doi=10.1016%2fj.ijhcs.2017.01.006&partnerID=40&
md5=433faab3bf27cea7b9cbdabf116c295a, cited By 0
13. Gennari, R., Melonio, A., Torello, S.: Gamified Probes for Cooperative Learning:
a Case Study. Multimedia Tools and Applications 76(4), 4925–4949 (2017)
14. Gennari, R., Melonio, A., Rizvi, M.: The Participatory Design Process of Tangi-
bles for Children’s Socio-Emotional Learning, pp. 167–182. Springer International
Publishing, Cham (2017), http://dx.doi.org/10.1007/978-3-319-58735-6_12
15. Gibson, J.P.: Teaching graph algorithms to children of all ages. Proc. of the
17th ACM annual conference on Innovation and technology in computer science
education (ITiCSE ’12) p. 34 (2012), http://dl.acm.org/citation.cfm?doid=
2325296.2325308
16. Lee, I., Martin, F., Denner, J., Coulter, B., Allan, W., Erickson, J., Malyn-Smith,
J., Werner, L.: Computational thinking for youth in practice. ACM Inroads 2(1),
32–37 (2011)
17. Maloney, J., Resnick, M., Rusk, N., Silverman, B., Eastmond, E.: The scratch pro-
gramming language and environment. ACM Transactions on Computing Education
(TOCE) 10(4), 16 (2010)
18. Wing, J.: Computational thinking. Comm. of the ACM 49(3), 33–35 (2006)