An Edgerton Center student team is developing museum exhibits as part of its STEM-related outreach efforts. To complement their work, graduate student Adam Gleitman built a prototype for a museum exhibit that teaches users about sorting algorithms. Through the prototype, he has turned the problem of sorting into a game.
The prototype consists of eight blocks, each with a different color and shape. Each block contains an RFID (Radio Frequency Identification), which allows a collection of RFID readers inside the exhibit’s enclosure to track the blocks’ locations in real time. Each block (or more precisely, each tag) is assigned a secret integer between 0 and 99 inclusive. The user does not know what the numbers are, but must figure out the relative order of the numbers. He or she does this by choosing any two blocks and pressing a button. A computer indicates what block has the larger value or if they have equal values. The object of the game is to put the blocks in the correct order in as few comparisons as possible.
A simple bubble sort or insertion sort algorithm can take up to 28 comparisons, but a merge sort only needs 17. Randomized algorithms like quicksort can have wildly different results depending on how lucky the user is in selecting a pivot. There are many enhancements that can be made to this exhibit, including illustrating different sorting strategies as a dynamic directed acyclic graph. Adam is excited to see how far his project can go and to explore other fun and innovative ways to teach people about computer science.