## Research one of the below topics:
1. B-Trees
2. K-d Trees
3. Red-Black Trees
4. Suffix Arrays / PATRICIA Trees
5. Priority Queues
6. Heap Sort
7. Quick Sort
8. Merge Sort
9. Short URL
Your source can be a journal article (research or technology note) or an
article online in a tech-trade magazine. Blogs are not allowed unless they are
comparing and contrast (If you have trouble accessing any articles see the
Consolidated Information Center or contact me if they cannot help). Your work
may not directly use the textbook implementation we discussed (e.g. Google’s
Big Table). But you must identify what is different about the approach.
Discuss how the topic was applied to solve a particular problem. Your text
should identify who was involved, what they did, when they did it, where it is
being used, and why they used it.
## The Assignment Deliverable
1. Format
a. Write a 2 page double spaced report.
b. 12 point font (Times New Roman).
c. 1” Margins and only your name for a header. Adding additional text will result in 20 points off (e.g. 10% of the total grade)
2. Paper Structure
a. Introduction (1 paragraph)
b. Background to Problem they solved
c. Methods of Solving (what data structures did they use)
d. Discussion (1 paragraph)
3. Submit a copy through ANGEL (http://lms.wsu.edu)
4. Bring a hardcopy to class.Possibly References
## Some possible places to start your search
1. Google’s Big Table
a. http://static.googleusercontent.com/media/research.google.com/en/us/archive/bigtable-osdi06.pdf
2. k-d trees for ray-tracing
a. http://en.wikipedia.org/wiki/Ray_tracing_(graphics)
3. k-d trees for proteomics
a. http://www.pnas.org/content/early/2009/08/25/0904100106.full.pdf
4. MD5 Hash
a. http://en.wikipedia.org/wiki/MD5
5. Suffix Arrays / TRIES
a. http://en.wikipedia.org/wiki/Trie
Also have a look at Slashdot for ideas. Google Scholar has great references. Or have a look at CiteSeerX from Princeton.
