A printable PDF is available.
Assignment 1 -- Using Binary Search Trees
Monday, September 14
Objectives: This assignment has two objectives: First, to get students started using and programming in the Unix environment, and second, to experiment with lookup tables based on lists and trees and consider performance under various scenarios.
High-Level Description: You will write a program that reads a large text file, and keeps track of how many times each word occurs in the file using a list and a binary search tree. You will measure the time required by both implementations on several different inputs, and describe what affects the performance in each case. The programming for this assignment is not terribly deep or complicated, but you will working on a new system and you should not underestimate the challenges that this can raise -- do not wait until the last minute to start this assignment!
you will use the binary search tree implementations from the book, as
well as files supplied specifically for this assignment.
Unfortunately, the code from the book is not compatible with the most
modern compilers (such as the one on the
cmpunix machine that
you'll be using!), so do not download the code from the textbook
publisher or authors. Instead, go to the assignments
link on the class web page, and follow that to download
corrected versions. Alternatively, you can copy the code directly on
cmpunix system from directory
Your program will need to keep track of pairs consisting of a word and
an integer count. In order to do this, you should define a class for
these pairs, with a constructor and methods to retrieve the current
count, increment the count, get the word, etc. You should also
provide operator overloads for the
operators. I'll call this "
pairClass" in this handout, but
you can feel free to name it however you'd like.
You will code up two alternative ways of keeping track of these pairs:
using a list (use the STL
list class) and a binary search tree
stree class from the book with the provided code).
To see how to do this, look through the main file,
wordreader.cpp: it reads a word at a time
from standard input and then calls a function
each word it reads. This function should look for the word in your
data structure, and if it finds the word it should increment the count
for that word -- if it doesn't find the word, then it's a new word
and should be added to the data structure (with count 1). Since you
will be using both a list and a tree to keep track of the words, you
will need to write two implementations of this function with
slightly different function signatures:
void findAndInc(stree<pairClass> &allWords, const string &word) void findAndInc(list<pairClass> &allWords, const string &word)By doing it this way, you can simply change the declaration of your data structure on the first line of the
mainfunction, and when you recompile the compiler will automatically link that call to the correct version of the
Finally, notice that wordreader.cpp calls a
function (again, one of two functions, depending on the type of your
data structure). You should use this function to print out the words
in your data structure along with the count of each one -- see the
sample output below for an example. The words should be sorted, so
for your list implementation you may want to use the
method provided by the STL
list class before printing.
Testing and Analysis: When you are writing and debugging your
code, you will probably want to use a small input file, such as the
one in the "sample input" below. For testing with text from files
(rather than entered from the keyboard) you should use input
redirection. Once you are convinced that your code works correctly,
you will use some large text files provided in directory
~srtate/data/assign1 for testing. There are three files,
test3.txt, and all
three consist of the full text of The Count of Monte Cristo,
plus information at the beginning that varies by test case.
You should run all three test files through your program using the
list data structure, and then all three using the tree data structure.
So that you are really timing just the data structure operations, you
can comment out the call to
processWords() in the main program.
Use the Unix
time command to time your program. For example,
you might run the program like this:
time ./wordreader <~srtate/data/assign1/test1.txtThis will print 3 different times -- the one you want to report is the "user" time, which reflects the amount of time your program actually spent executing on the CPU. Feel free to adjust the compiler flags in the
Makefileto experiment with optimization settings (e.g., using "
-O4" when compiling), but make sure you use consistent flags when comparing implementations.
Finally, look at the test data files, and think about why the different implementations performed as they did for the different input files. Write a brief report giving a table of your measured times and explaining the performance -- explain why the different implementations performed well or didn't perform well on different inputs. It is important that you are as precise in your descriptions as possible, and use terminology and notation that is standard in computer science. For example, you should be referring to concepts "worst case," "best case," and "average case," and should be describing performance in terms of asymptotic notation ("big-oh notation", although if you want to really be precise you should use better notations such as "theta" notation).
To Turn In: Use the
330submit program (see
in order to turn in your code, using assignment name
You should submit every file that you have created or modified (you
can also include the
.h files that were provided to you, but
this isn't necessary -- they should not be changed!).
On the due date, you should turn in a printout of your code along with your
report giving your performance analysis.
Peter Piper picked a peck of pickled peppers, A peck of pickled pepers Peter Piper picked; If Peter Piper picked a peck of pickled peppers, Where's the peck of pickled peppers Peter Piper picked?
a: 3 if: 1 of: 4 peck: 4 pepers: 1 peppers: 3 peter: 4 picked: 4 pickled: 4 piper: 4 the: 1 where's: 1