Final Results
Data Tutor
Advisor: Jadrian Miles
Background
As a new programmer is learning their first or second programming language, one hurdle they must overcome is understanding the relationship between source code and the underlying memory representation of the state of a program as it runs. Software tools can support the user in learning this relationship by showing it to them explicitly. Many debuggers provide a rudimentary form of this functionality: they can list the names, values, and addresses of all variables in the namespace. Some tools have gone a step further, and provided dynamic schematic representations of the memory model: for example, see pythontutor.com.
Students in Data Structures and Algorithms, though, have a new conceptual task: move beyond the implementation details, and think abstractly about the behavior of canonical abstract data types as they are manipulated by a variety of different client algorithms.
Your project is to build a web app that allows a CS 201 or CS 252 student to type their own source code into an integrated editor, and then step through the code, while the app shows them an animated, visual representation of all the ADTs in their program, and how those ADTs' states are changing and interacting. Here are a couple mock-ups:
CS 201 use case: simple interactions of ADTs
Here a Data Structures student has entered code on the left (maybe entered from instructions on a homework assignment) and then pressed the “step through” button in the upper left. As they step through their code, an execution marker shows them where they are, and the ADT visualization on the right first gets populated with their stack and queue, and then the contents of these structures move around to mirror the data movement expressed in the program.
CS 252 use case: prototyping algorithms
Here an Algorithms student has entered code on the left to try out breadth-first search. In their code they've used a feature of the app's ADT implementation to generate a random test graph with multiple connected components. The app also populates the namespace with helpful numerical constants like “Inf”. As the student's code runs, they can see all the operations on the interaction data structures, as well as visual indications of access patterns in the graph.
The Project
Create the above-described tool as a web app, hostable on Carleton servers.
Baseline Features
- Visualization of standard abstract data types: Lists, Stacks, Queues, Priority Queues, Graphs, rooted Trees.
- A simple programming environment with heavily restricted semantics. You could require the user to code in a pseudocode language of your own devising, or a restricted dialect of Python or Java. The code they write should have access to the above-described ADTs.
- Execution-stepping functionality as in a graphical debugger, with the state at each time point reflected in the visualization of the ADTs.
- Animation of data movement and value changes.
- Automatic generation of random data in any ADT, constrained by user settings. (I.e., is the graph directed? Weighted? Connected? Big? Little? Don't care?) The distribution from which inputs are drawn should have a non-negligible probability of generating interesting/challenging inputs: unbalanced trees, complete graphs, disconnected graphs, empty lists, etc.
Advanced Features & Goals
- More ADTs: Dictionaries, Sets, Disjoint-Sets structures, Updatable-Priority Queues, etc.
- Test your app with real users in CS201 and/or 252. This requires developing user tests, recruiting participants, analyzing the results of the tests, etc.
- Intelligent automatic layout of the graph (that is, positioning of the nodes).
- Intelligent automatic arrangement of the ADT figures on the visualization canvas. (This is a tough problem! Stacks are vertical, queues and lists are horizontal, graphs are blobby — how do you arrange them to maximize comprehensibility? Can you also assure that data values moving between ADTs don't have to travel too far in the visualization?)
- Automatic inference, from the structure of the user's code, of which random data will be challenging for their algorithm. (E.g., you see that they're writing something that looks like a sorting algorithm that will waste tons of compares on nearly-sorted input, so the distribution for random data automatically shifts toward nearly-sorted lists.)