«GraphBench: Exploring the Limits of Complexity with Educational Software A dissertation submitted to the SWISS FEDERAL INSTITUTE OF TECHNOLOGY ZURICH ...»
DISS. ETH NO. 16392
GraphBench: Exploring the Limits of
Complexity with Educational Software
A dissertation submitted to the
SWISS FEDERAL INSTITUTE OF TECHNOLOGY
for the degree of
Doctor of Sciences ETH Z¨rich
Markus Andreas Br¨ndle
Dipl. Informatik-Ing. ETH
citizen of Mosnang SG
accepted on the recommendation of
Prof. Dr. Bertrand Meyer, examiner Prof. Dr. J¨rg Nievergelt, co-examiner u Prof. Dr. Angelika Steger, co-examiner Acknowledgements This dissertation and the software GraphBench resulted from the support and contributions of many people to whom I am very thankful and wish to express my gratitude.
I ﬁrst would like to thank J¨rg Nievergelt and Werner Hartmann for inu spiring me to work on this thesis. J¨rg Nievergelt has been an extraordinary u supervisor, advisor and personal mentor throughout my whole dissertation.
His interest, commitment, ideas and visions are the cornerstones of my work and for that I am very grateful. Werner Hartmann was the didactic voice and his comments and suggestions account for the usability of GraphBench. I would especially like to thank him for being a friend I could always talk to.
I am also indebted to Bertrand Meyer for allowing me to ﬁnish my thesis under his supervision. I greatly appreciate his contributions and his interest in a topic originally not within his research area.
I was very glad that Angelika Steger agreed to be co-advisor. Peter Widmayer and Juraj Hromkovic deserve my gratitude for the time I spent in their groups and for their support.
Matthias Dreier was involved in the beginning of the project and was very much responsible for the good start and the solid software foundation of GraphBench. Raimond Reichert, Ruedi Arnold and Judith Zimmermann greatly supported my work with their time, comments and suggestions.
Many others have directly or indirectly contributed to my work and deserve to be mentioned: Nina Huggenberger, Floris Tschurr, Hon Wai Leong and the whole reasearch group of Betrand Meyer, in particular Michela Pedroni and Till Bay.
Finally, I thank Ursina, my parents and my brother for putting up with me and taking my mind of computers every once in a while.
iii iv Abstract In today’s information society it has become ordinary for students to use computers to study. Educational software is increasingly being developed for all kinds of subjects and school levels. Although a broad range of computer science areas is covered, topics that admit intuitively meaningful graphic representations are almost exclusively considered. Mathematically
topics that are more diﬃcult to present, as well as to understand, still challenge our ability to create eﬀective computer support. The theory of NP-completeness in particular has been almost neglected by educational software, despite its importance in the theory of computation and in computer science education. Yet it is precisely in such a highly specialized, abstract topic that computer-based learning environments might do their best job.
In this thesis we have developed GraphBench, a highly interactive learning environment for the theory of NP-completeness. GraphBench, as well as the techniques and principles on which it is built, is the main contribution of this dissertation. Our software provides students with an intuitive approach to an otherwise abstract and complex topic. GraphBench features eight diﬀerent NP-complete problems and nine diﬀerent polynomial time reductions. Our software oﬀers separate environments for all featured NP-complete problems and polynomial time reductions.
GraphBench combines traditional didactic with new computer-based approaches to foster an intuitive understanding of the basic underlying concepts.
In this thesis we identify diﬃculties that arise when developing educational software for abstract topics and present several didactic concepts and implementation approaches to overcome them.
We have successfully used GraphBench in various courses on the theory of computation at the Swiss Federal Institute of Technology ETH, at the National University of Singapore and at the Free University of Bolzano. The highly positive feedback from professors and students justiﬁes our approach and shows the need for learning environments for highly specialized, abstract topics.
Overview In this chapter we give a short overview of this thesis. We summarize our motivation and the work that has been done. We further give a short introduction to our learning environment GraphBench and shortly look at its use.
1.1 Motivation The theory of computation teaches students the limits of computers, e.g. what a computer can and cannot compute. It is fundamental to computer science and thus an important part of any computer science education. Despite of its importance students often have diﬃculties with the theory of computation and lack motivation to study it. Among the topics that students typically struggle with is the theory of NP-completeness and polynomial time reductions. This theory deﬁnes a class of problems that are diﬃcult, i.e. very time consuming, for a computer to solve.
Computer-based learning environments can help students overcome their diﬃculties and help them gain a better understanding. While some topics of the theory of computation are well covered by educational software, the theory of NP-completeness has been almost neglected. It is a highly abstract and rigorously formal topic. This not only makes the theory diﬃcult for students to understand, but also the development of a learning environment for this topic challenging. Topics that are either only highly abstract or only rigorously formal are easier to understand. Students have for instance little problems to use the learning environment “Tarkis world” (Barwise and Etchemendy, 1997) that covers the very formal but not very complex topic of ﬁrst-order logic.
Computer games on the other hand are often highly complex, but because they are also quite intuitive they are well feasible to master. It is the combination of abstraction and formality that challenges the human mind and makes the design of a learning environment diﬃcult (ﬁgure 1.1).
Fig. 1.1: Software for either a only highly complex or a only rigorously formal topic is easier to master than software for a topic that is both.
The importance of the theory of NP-completeness, students’ problems with the topic and the lack of learning environments motivated us to approach the theory of complexity and design a learning environment for NP-completeness.
1.2 Contributions In this thesis we focus on complexity theory. We have developed GraphBench, a highly interactive learning environment for the theory of NP-completeness, i.e. for NP-complete problems and polynomial time reductions. GraphBench provides students with an intuitive approach and combines traditional didactic concepts with new computer-based methods. It fosters an intuitive understanding of the basic underlying concepts and allows students to experiment and thus to discover the theory of NP-completeness.
GraphBench features eight diﬀerent NP-complete problems, e.g. Satisfiability or Graph Colorability, and nine diﬀerent polynomial time reductions, e.g. reducing 3CNF Satisfiability to Clique or Vertex Cover to Hamilton Circuit. GraphBench oﬀers a separate environment for every problem and for every reduction. The environments all share a common user interface and similar functionality. The problems and reductions were selected according to several criteria, e.g. their frequent use in computer science education.
GraphBench actively involves students and provides them with a “handson” approach. Students can for instance manipulate and create new problem instances, or actively investigate polynomial time reductions. The learning environment allows students to solve arbitrary examples by hand or to use built-in solution algorithms. GraphBench fosters an intuitive understanding by providing various, intuitive graphical representations of the NP-complete problems, polynomial time reductions, and solution algorithms.
In this thesis we have identiﬁed diﬃculties that arise when developing educational software for abstract topics and present several didactic concepts and implementation approaches to overcome them, e.g. “Selective Level of Detail”.
We illustrate the concepts with examples and state their learning beneﬁts.
This thesis consists of work in the ﬁeld of computer science education and didactics as well as work in the ﬁeld of software engineering. With GraphBench we have developed a Java software framework for computer-based learning environments. It consists of several independent libraries that can be reused to create learning environments for topics other than complexity theory. The framework is designed to facilitate maintaining and extending existing content, e.g. adding new NP-complete problems or solution algorithms.
We have successfully used our learning environment GraphBench in various courses on the theory of computation at the Swiss Federal Institute of Technology ETH, at the National University of Singapore and at the Free University of Bolzano. It was used as a demonstrational tool in class as well as for student assignments and semester projects.
1.3 Conclusions With GraphBench we have developed a learning environment for a topic that has otherwise been almost neglected by educational software. The fundamental importance of complexity theory in computer science and student’s struggle with the topic show the need for such a learning environment.
GraphBench conforms to today’s criteria for educational software, e.g. a high level of interactivity or active user involvement. We have developed a software framework and new didactic approaches that can be adapted for other topics.
The widespread use of GraphBench at universities worldwide, and the highly positive feedback from professors and students, convince us that our approach is successful and worth pursuing.
Computer-based learningenvironments: State of the art
Computer-based learning environments are omnipresent in today’s education society and can be found for a wide variety of topics. In this chapter we ﬁrst analyze the diﬀerent uses of computers in education and show our idea of utmost computer beneﬁt on learning success. We point out requirements and criteria for successful computer-based learning environments.
We then focus on computer science education and show the wide range of topics currently addressed by learning environments. We brieﬂy introduce several learning environments and point out where we see room for improvement.
2.1 Computer uses in education: Medium of presentation and subject matter tutor In today’s information society it is not uncommon for students to use computers to study. Educational software is increasingly being developed for all kinds of subjects and school levels. Traditional learning environments like classrooms include infrastructure, information, exercises, tests, teachers or tutors. How do we apply these traditional concepts to computer aided learning? What is needed to create a computer-based learning environment?
Today the computer is mostly used as versatile presentation medium that combines the capabilities of a number of traditional media such as books, movies or audio. The cognitive theory of multimedia learning supports the use of such multimedia presentations. [MM02] state for instance, that animations can improve learning when used in ways that are consistent to the theory of cognitive multimedia learning. This theory is based on three assumptions: 1) dual-channel assumption – the idea that humans possess separate information processing channels for visual and auditory material, 2) limited capacity assumption – the idea that humans are limited in the amount of information they can process at one time in each channel, 3) active processing – the idea that meaningful learning occurs when learners engage in cognitive processes, e.g. selecting relevant material (see e.g. [May01]).
Using computers and multimedia does not exhaust the strength of computers in learning by far. Computer-based technologies present a number of possibilities to further improve learning. Educational software can for instance provide access to a large collection of documents and facts. An additional advantage, compared to traditional media, is obtained if the data is kept upto-date. In business and ﬁnance, for example, the software might access daily currency exchange rates and stock quotations that are freely available on the Internet.
Today’s educational software often does not allow students to change the texts, narrations, sounds or animations, e.g. to change the initial conﬁguration of an animated experiment. However, allowing students to manipulate underlying objects, such as examples or solutions, can improve learning. For instance, instead of seeing a pre-computed animation, the student can now conﬁgure the initial parameters and then watch a simulation based on his settings.
An even greater beneﬁt arises when the software is able to produce new content depending on actions by the student, e.g. generate an unlimited number of exercises with various diﬃculty levels, solve arbitrary examples or provide meaningful feedback to actions or questions by the student. This implies that it must embody a model of its domain of discourse that enables it to derive facts not explicitly foreseen and stored. We refer to such systems as subject matter tutors. In this thesis we have developed a learning environment containing several subject matter tutors, we introduce the system and the subject matter tutors in detail in chapters 6, 7.