Instructors can find out how well students understand how to choose among various data structures for a specific scenario. In this scenario, students are asked to infrequently remove old data from the structure.
Read the following scenario and answer the question. Be certain to back up your decisions.
You need a data structure with the following functionality. Items are inserted, looked up, and removed on a fairly frequent basis. More importantly, every hour, in order to save space, you remove the least used data from the structure. For example, if data A was accessed only once in the past hour, you might want to remove it. Assume it is up to you to decide what makes data "old."
How would you implement a solution to this problem?
Student answers will vary greatly. One of the more obvious solutions is to use a splay tree. Other students might note that the removal by age process takes place very infrequently and will instead focus on making the rest of the functionality more efficient.
Read through the applications and sort or mark them as "Good," "Acceptable," "Marginal," or "Wrong." Read through the piles again to make sure that you have not accidently misclassified a response. You might also want to sort the responses by the type of algorithms are used.
Choose three or four of the best examples from the "Good" pile. Emphasize understandability, but try to have a diversity of example domains. Also consider a few acceptable and marginal responses that highlight points you wish to discuss.
If you use an application in class as a bad or poor example, change the application just enough to disguise the example from the original authors.