Overview of Requirements

• A paragraph abstract by email, latest Monday, April 23 at noon
• A 10 minute presentation on your data structure in lab on Friday, April 27
• A (maximum) 5 page paper (not including illustrations) due Friday, April 27 with late papers accepted until Monday, April 30. Hand in a PDF document using handin35 in the ~/cs35/labs/12/ folder. If you can't scan your illustrations, you can hand in those in a hard copy, but I would still like the typed report to be handed in electronically as well.

This lab is to be done invidiually. But you are welcome to discuss ideas with anyone in the class, and team up to practice your presentations and provide feedback on your reports.

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 14-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-sized paper which will discuss your chosen topic. Your report should introduce the topic, provide a motivating example, compare and contrast to a related course topic, and analyze a few important operations. You will demonstrate not only your conceptual understanding of the topic(s), but also you are ability to analyze algorithmic efficiency.

Accompanying your report will be a 10 minute presentation in lab on Friday, April 27, 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 (e.g., using priority queues for handling triage in an emergency room). I will provide a rubric ahead of time which your fellow students, myself, and the ninjas will use to evaluate your presentation.

Choosing a Data Structure

This is largely open ended. But you must send a short paragraph explaining your plan by Sunday, April 22. 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, Charlie, Lisa, or myself
• I'll add more as I find them. Feel free to send me a link if you think it will be helpful for the class. In general, google it

Some example data structures include:

• Doubly Linked Lists
• Skip Lists
• Circulary Linked Lists
• Double-Ended Queues
• Red-black tree
• Splay tree
• (2,4) Trees
• Treap (a combined heap/binary search tree)
• B+ Tree
• Fibonacci heap
• Non-binary trees (e.g., ternary tree)
• Probablistic graphs

You could also do algorithms such as:

• Sorting algorithms
• Graph algorithms

Some of these are more advanced than others. Your report should take this into account - if you choose a simple extension of something we did in class like a double linked list, you are expected to do an in-depth analysis of the interface and tell us what the efficiency of most of the operations are. If you are more adventourous, the analysis can be a little more high level as you will spend most of your time illustrating the algorithm.

Writeup

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

• An introduction
• 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 in class? What are the conceptual differences?
• Interface - what are the major operations of the data structure. This maynot 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).
• Analysis - provide pseudocode for a few key operations and analyze their run time. If you are choosing a simpler structure, you should probably put a little more effort into this section. If you are analyzing a structure that is further afield from those covered in course, you can do more of a compare/constrast of runtimes and briefly explain the method's runtime. Or, you can go in depth on just one or two important operations.

Your paper should be typed; no hand-written solutions will be accepted. The exception is with illustrations, which can be neatly drawn and attached to your writeup. 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 update21, there are some example tex files for you to play around with.

In terms 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 Friday, April 27. 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


Last updated: Friday, April 20, 2012 at 03:45:36 PM