Project 2 - Version 1.0
Due Friday November 2nd
O. No Longer The Latest Version
This is no longer the latest version of the project. The latest version
is located here!
You have just been approached by a world famous UW history professor.
He would like you to settle a
centuries-old debate on who wrote Shakespeare's plays, Shakespeare
or Sir Francis Bacon?
You protest that this question is surely outside of your area expertise.
"Oh, no," chuckled the historian, stroking his snowy white beard. "I need
a Computer Scientist!"
II. Word Frequency Analysis
The professor suspects that some authors use particular words more often
than others. He hopes that if we study the frequency with which authors
use words, we may be able to come up with a word usage "signature" for
that author. This signature should be quite consistant across a particular
author's works, but vary greatly between authors.
The professor wants you to take two works of Shakespeare (Hamlet,
and All's Well That Ends Well), and two of Bacon
(The New Atlantis, and The
Essays), and count the number of times that each word occurs in each.
He would like you write a program that takes two commmand line arguments.
The first argument is the name of a text file to be parsed, and the second
is a text file that your program will output. The output file will be in
the following format:
...where the first string is a word in the text, and the second string
is the frequency with which it occurs in the text. Strangely enough, the
professor wants you to hand in this project using the turnin program to
the CSE 326 database. He would like a copy of your source code, an explanation
of how to compile your program, and a 1-2 paragraph answer to his question:
based on the data you have accumulated,did Bacon write Shakespeare's plays?
III. The Nitty Gritty - IMPORTANT!!!
You may work on this project in teams of up to two.
You must implement the word counting algorithm in the following
By loading the strings as keys into an unbalanced binary search tree. The
values are the frequency with which that word has occured so far. This
should be compilable into an executable called "bst".
As above, except using AVL trees, instead of using unbalance binary search
trees. This should be compilable into an executable called "avl".
As above, except using Splay trees. The executable here should be called
Make your balanced binary tree classes inherit from you unbalanced
binary tree class. The functions to add and get elements should be delcared
virtual, and related polymorphically across trees.
Your frequency count should be case sensitive. That is, "Shakespeare" and
"sHaKeSpEaRe" should be counted seperately.
You should only skip over the following characters: the space character
(' '), the tab character ('\t'), the newline character ('\n'),
the carriage-return charactger ('\r'), and the form-feed character
('\f'). All other characters should be considered part of words.
You will find that the text files we give you contain some extraneous information
(e.g. copyright stuff). Don't waste your time trying to delete this, as
it will have an negligable effect on the output.
You do not need to implement delete functions, since these aren't needed
for this project.
You must implement these data structures from scratch. This time around
we won't give you and definitions to implement. So it's all up to you!!!
Have fun, and uncover deep historical truths!
IV. Files for Project 2
V. Extra Credit!
The files we have provided for you:
The files you should turn in (Bundle these files with the tar
utlity and turn them in with turnin.
This project is called "project2" in the turnin system.)
bst.cpp - the program using the unbalanced binary search tree
avl.cpp - the program using AVL trees
splay.cpp - the program using splay trees
readme.txt - an explanation of how to compile your program (note:
your program should compile with g++ on UNIX)
my-answer.txt - a one to two paragraph explanation of whether
or not you think that Bacon wrote Shakespeare's plays based on the data
you collected. No fancy statistical analyses here. Keep it fun and simple.
Implement the program with Red-Black trees. The advantage of Red-Black
trees is that you can write non-recursive insertion/deletion algorithms
(the trade-off is that Red-Black trees have weaker balancing condition,
though they do guarantee O(log(n)) depth) . Don't cheat, write
non-recursive algorithms here.
Compare the running time of the trees on the words
file using either the time utility or (even better) the gprof
utility. The words file is an in-order list of words in the English language.
This is the worse case for the unbalanced binary trees. So you will find
the balanced trees way outperforming the unbalanced tree here.
VI. Interesting Tid Bits
Word frequency analysis plays an important role in Cryptanalysis, the science
of breaking secretly encoded messages. The first mention of using the frequency
distribution of a language to to break codes was in a 14-volume Arabic
encyclopedia written by al-Qalqashandi in 1412. The idea is attributed
Ibn al-Duraihim, the brilliant 13th century Arab Cryptanalyst. If you are
interested in cryptography, be sure to check out The
Code Book by Simon Singh. This is great introduction to cryptography
Wondering where we got these text files? From the Project
Gutenburg site, which has thousands of books as plain text files! Check
it out. Run your word couting program on the King James Bible! (Guess which
word comes up more frequently in the Bible "he" or "she?".. by a factor