Overview of Requirements

• A paragraph abstract emailed to me by Friday, November 30, at noon
• A 10 minute presentation on your data structure in lab on Monday, December 10
• A (maximum) 5 page paper discussing your data structure due Tuesday, December 11. You can ignore the size of illustrations in your page count. Late papers will be accepted until December 18 at midnight without penalty. Hand in a PDF document using the submission link on the course Moodle page.

This lab is to be done individually. But you are welcome and encouraged to discuss ideas with anyone in the class, and team up to practice your presentations and provide feedback on your reports. I strongly recommend practicing your presentations with others.

Introduction

Throughout the course, we we have seen several algorithms and structures for organizing and manipulating data. With each, you have built the foundations of your computational knowledge base that will aid you as you continue to mature as scientists. The constraints of a 13-week course limited the number of data structures we analyzed, as well as the variations and nuances of some that we did cover. The central goal of this course, however, was not to memorize every data structure ever invented. Rather, it was to develop the skills of analysis and design that are a prerequisite to becoming a skilled computer scientist.

For your last assignment, you will demonstrate these newly acquired skills by exploring data structures and algorithms that we did not cover in class. You will write a medium-length paper which will discuss your chosen topic. Your report should introduce the topic, provide a motivating example, compare and contrast to a related course data structure, and analyze a few important operations. You will demonstrate not only your conceptual understanding of the topic(s), but also your ability to analyze algorithmic efficiency.

Accompanying your report will be a 10 minute presentation in lab on Monday, December 10, 2012. You will be evaluated on your communication skills in both the report and your presentation, so be sure to understand the motivation of using your data structure. I encourage you to make your presentation interactive; you will be evaluated on substance and your ability to explain the data structure to your classmates. Below, you will find a list of questions I and your classmates will answer to evaluate your presentation.

Choosing a Data Structure/Algorithm

The choice of data structure or algorithm to cover is largely open ended. But you must send a short paragraph explaining your plan by Friday, November 30. This should include the topic you plan to cover and what you aim to discuss in your paper. You can use the book to find example data structures that we did not cover, or explore resources online. While Wikipedia is not a primary source, it is a reliable repository of data structures that can be easily explored and there are usually good examples. Other resources include:

• Wikipedia
• A WikiBook
• Data structure books in the CS Main Lab
• Rich, Tia, Andy, Adam, Jason, Lisa, or myself
• Google it!

Some example data structures include:

• Skip Lists
• Tries/Prefix trees
• Bloom filters
• Ternary Search Trees
• Red-black tree
• Splay tree
• (2,4) Trees
• Treap (a combined heap/binary search tree)
• B+ Tree
• Fibonacci heap
• Probablistic graphs
• R-tree
• Cords
• BSP trees
• Radix trees

You could also do algorithms such as:

• Sorting algorithms
• Graph algorithms
• Huffman coding
• Hash functions

Writeup Requirements

Your writeup should be well-structured and follow scientific writing principles. You can structure as you see fit, but at a minimum, your paper should include:

• An introduction - this can include a history and a preview of the central features of the data structure/algorithm
• Motivation - what is the problem that needs to be solved? It is recommended that you come up with real-world application and describe it here.
• Background/related work - what does this relate to from class? What are the conceptual differences? Are there other algorithms/data structures that generally compete with your choice?
• Interface - what are the major operations of the data structure? This may not apply for an algorithm, but you discuss assumptions for the structure of the data.
• Illustration - walk through an example (e.g., for BFS, going from Parrish to the Ville). You should have some sort of diagram that illustrates how the data structure/algorithm works.
• Analysis - provide pseudocode for a few key operations and analyze their run time. This does not need to be exhaustive, and how many operations you cover depends on the complexity of the problem. For example, inserting/removing from linked lists was fairly simple so it would be good to cover most of the methods. Removing/inserting into an AVL tree is quite complex, so be sure to limit your discussion to one or two key operations. You should then summarize the other operations.

Your paper should be typed; no hand-written writeups will be accepted. The exception is with illustrations, which can be neatly drawn and attached to your writeup. I would prefer you scan and attach the images to your PDF document, if possible. It may be useful to learn to use latex, a popular typesetting system that is used widely for writing scientific and mathematical papers. If you are interested, feel free to email me any questions about this. You can also find a primer and some sample guides online, including here or here. If you run update35, there are some example tex files in your cs35/class/12/ directory.

In terms of the length of your writeup, it is really up to you to judge how much material adequately describes your data structure/algorithm. Your writeup, excluding figures, should not exceed 5 pages using 1.5 spacing.

Presentation

You will present your findings in a short presentation (maximum 10 minutes) during lab on Monday, December 10. You will be divided into groups of 4-6 students with one discussion leader (either myself, a ninja, or Frances). Each student in your group as well as the discussion leader will evaluate your presentation on the following criteria:

1. Rate the introduction/motivation for the material
2. How effective was the presenters sample illustration in conveying the high-level features of the data structure/algorithm?
3. Overall, how effective was the presentation in explaining the data structure or algorithm?
4. Briefly, describe the strongest part of the discussion
5. Briefly, list one thing the presenter could improve upon to help you understand the topic better

Home Page