A major goal of these labs is to provide a context for each data structure. This way, students can see data structures as components of a larger system, rather than just abstractions in isolation.
While these labs are definitely a work in progress at the moment, I'd like to share some of what we have achieved thus far.
We begin by getting students up to speed with creating Eclipse projects and familiar with interfaces. To that end, they implement strategies for the Prisoner's Dilemma.
The next lab involves implementation of stacks. They must implement the data structures themselves. We provide a JavaFX GUI that enables them to visualize the behavior of what they create.
This is followed by a lab where they create a maze data structure. Again, we provide the GUI, but they create the underlying data structure. This sets them up for the next lab, where they implement maze solvers using stacks and queues. This is also the stage where we introduce the implementation of generic data types.
To illustrate and visualize doubly-linked lists, their next task is to implement a text editor. We again provide the GUI. The students implement the doubly-linked list. In creating a cursor to navigate the document, we also provide a gentle introduction to the concept of an iterator.
As no data structures course is complete without sorting algorithms, in the next lab the students implement animated sorting. Again, we provide the GUI and they provide the algorithms.
Having worked with four JavaFX projects up to this point, in the next lab the students are finally responsible for a GUI implementation. We guide them very closely through the process of creating it. After the lab, the students have a project assigned in which they are to create another GUI in a more free-form way.
Another classic data structure is the binary search tree, and in the next lab students create their own, with a simple visualization.
One of the most ubiquitous features of the modern age is the text-predicting device. We introduce students to the use of a trie for text prediction. The GUI shows the predicted text based on the input suffix. In practice, the trie is a more efficient tree structure than the binary search tree when the keys are strings, and we thought it would be valuable to introduce students to this concept.
The classic lookup data structure is of course the hash table. We actually struggled a bit to come up with a context in which a hash table was actually an appealing data structure (as opposed to a tree or trie). That is, every context we devised, most especially with string keys, seemed to involve an application where maintaining a sorted order was beneficial.
What we came up with as our application was the creation of a tic-tac-toe program that learns from experience. The students implement a hash table to store board positions and expected outcomes.
In our final lab, we revisit maze searching in order to introduce heaps. Students create a heap that is then used in an implementation of A*.
Some more labs we'd like to work on would include:
- Balanced binary trees
- Functional programming concepts introduced in Java 8, including
- stream computation.
- With regard to stream computation, it would be cool to come up with something that parallelizes nicely on a multicore.
I'd love to hear from anyone who finds any of this useful, or who has other ideas to share!