CMPSC112F09: Data Structures

Benjamin Bloom and his group formulated three taxonomies for assessment in the 50's (see "The Taxonomy of Educational Objectives, The Classification of Educational Goals, Handbook I: Cognitive Domain"). I want to introduce you, briefly, to the cognitive taxonomy

When I ask you facts about things in class, I'm evaluating at the most basic level of cognition: factual recall of knowledge. When I ask you to interpret or extrapolate, that involves you comprehending those facts. When I ask you to solve a new problem using what you know, that involves applying your knowledge in new (but not necessarily creative) ways. Decomposing things into component parts and critically evaluating them exercises your analytical skills, putting everything together in new and creative ways is a synthetic process that we, as students of computing, have too little opportunity for, and making, evaluating, and defending judgements based on evidence and criteria is considered to be at the top of this cognitive hierarchy.

Is this hierarchy a good basis for formulating assessments of students? 

I don't particularly care, at the moment. But, I wanted to give you the framework for reflecting on your own learning—reflection in the context of this taxonomy is why I rewrote this laboratory at the last minute.

Most directly, I am asking you to implement a linked list and apply it creatively in a context you are not familiar with. 

If you are feeling creative, you can synthesize something completely new, as long as (fundamental to your project) is an implementation and use of a linked list.

The first project you might explore involves building on the piano scenario (download link). If you start with the piano scenario, you should be able to implement something that lets you play simple tunes.

Once you can play simple tunes, you should be able to record and play back those tunes. Develop a simple interface (it could be based on simple keypresses, or perhaps something more complex) that allows the user to start a recording. Then, you should keep track of when the key events take place: when do they play a note, which note, etc. When the user stops recording, you should be able to play it back... perhaps by having three possible recording slots, or perhaps by saving their recordings to a file. (This is certainly more ambitious.)

I don't know how long this laboratory will take. I expect it can fill a full 10-12 hours of work this coming week. 

I want to challenge you and your partner to work from the interfaces provided below, and write your own implementations. Use Drake's book for reference if you get stuck, or chat with me... but don't just punt and copy the implementation from the text. Work through the logic of what action each method defined in the interface should perform on the list (or the node). 

Through constructing your linked list implementation, my hope is you are building a better understanding of the list itself. So, central to your implementation is an excellent linked list implementation. Excellent means:

• Commented thoroughly with JavaDoc
• Exceptions thrown at appropriate places in the implementation
• Unit tests covering the entire implementation of the linked list

Page 134 is where you can find the List<E> interface; use this as your starting point. Likewise, you are welcome to use a ListNode<E> on page 159 as the starting point for your node implementation.

A creature of streams and fountains, you have no real provenance beyond these small bodies of water. If someone happens to fall asleep nearby, you can ensorcel them to your will, but other than that, you're mostly afraid of drought. 

You will achieve this level of greatness in the pantheon of the ancient gods if you only submit an excellent ListNode<E> and LinkedList<E> implementation as defined above.

You are Hera, Queen of the Gods. (Zeus, if you're male are uncomfortable with the idea of being Hera. But, really: whatev. Hera was awesome.)

You are among the great, remembered for all time. Your followers build you temples, sacrifice at your altars, and emblazon your name across the bumside of their sweatpants. Truly, you are among the immortal great, just like Mr. T.

A new scenario of your own invention almost immediately launches you to godhood. Or, some truly excellent integration work based on the musical or celestial scenario will also earn you this recognition. Having the ability to record multiple songs, add new worlds and set critical parameters (mass, color, etc.)... anything that inspires your user to play and explore.

You must present your work to a panel of experts (your peers), and they must agree that your work transcends mere Titan-ness, and is grounds for inclusion among the New Gods.