Faculty Recruiting Support CICS

Tools for Tutoring Theoretical Computer Science Topics

28 May
Tuesday, 05/28/2019 3:00pm to 5:00pm
CS 150/151
Ph.D. Thesis Defense
Speaker: Mark McCartin-Lim


This thesis introduces Complexity Tutor, a tutoring system to assist in learning abstract proof-based topics, which has been specifically targeted towards the population of computer science students studying theoretical computer science, and which gives those students real time feedback while working on theoretical computer science exercises. Existing literature has shown tremendous educational benefits produced by active learning techniques, student-centered pedagogy, gamification and intelligent tutoring systems. However, previously, there had been almost no research on adapting these ideas to the domain of theoretical computer science. As a population, computer science students receive immediate feedback from compilers and debuggers, but receive no similar level of guidance for theoretical coursework. One hypothesis of this thesis is that immediate feedback while working on theoretical problems would be particularly well-received by students, and this hypothesis has been supported by the feedback of students who used the system.

This thesis makes several contributions to the field.  It provides assistance for teaching proof construction. While other systems have been developed for training students in proof construction, most are limited to very narrow domains outside of theoretical computer science, and have typically taken decades for expert system designers to develop even for very limited domains. A second contribution is that it can be adapted to new domains taught in many abstract mathematical courses. Exercises can be constructed in natural language and instructors with limited programming knowledge can quickly develop new subject material for Complexity Tutor. A third contribution is the platform for writing algorithms in Python code that has been integrated into this framework, specifically to benefit theoretical computer science where constructive proofs are common. A fourth contribution is development of an interactive environment that uses a novel graphical puzzle-like platform and gamification ideas to teach proof concepts. As a result, the learning curve is also lower than many other systems, since it does not require students to learn a formal language or complex interface.

A multi-semester evaluation of 102 computer science students using Complexity Tutor was conducted. Many hours of video of students interacting with Complexity Tutor were collected, along with survey results and statistics about exam performance. An additional 98 students participated in the study as part of control groups. Complexity Tutor was used to help students learn the topics of NP-completeness in algorithms classes and prepositional logic proofs in discrete math classes. Both are abstract topics that computer science students frequently struggle with, and which are ripe for the intervention of an intelligent tutoring system. Since this is the first significant study of using a computerized tutoring system in theoretical computer science, results from the study not only provide evidence to support the suitability of using tutoring systems in theoretical computer science, but also provide insights for future research directions.

Advisors: Andrew McGregor and Beverly Woolf