CS14, Extra Credit Program

Assigned: May 24^th, 2002

Due: June 10^th, 2002

This is an extra credit program, your opportunity to make up points lost on earlier assignments or on the tests. Depending on the work you put into it, it could be worth up to a letter grade.

Half the credit will be given to the design of your data structure. Think of it as getting significant credit for commenting your code.

Background

A concordance of a text is a list of the words found in the text and where in the text they can be found, usually a page and line number. Very common words such as prepositions and conjunctions are generally not listed in a concordance. For this assignment, you will design and write a program that accepts a text, and stores its words in a structure that will enable searching for a word and finding all the lines where it appears, as well as printing out an alphabetical list of all the words in it, each word followed by a list of all the line numbers where it can be found. For yet more credit, your program should be able to filter out common words before creating the concordance.

There is no single “correct” solution to this problem. Be creative.

Part I – 50 points

Describe in meticulous detail the data structures you choose for creating and storing the concordance. Be specific. No credit will be given for vague descriptions and handwaving arguments. List out all the variables you will be using – arrays and their contents, structures and their fields, classes and their methods, pointers and what they point to. Use as much code or pseudocode as you need to be precise. You may use any and all of the data structures you studied, wrote or used during the quarter, or you can design your own.

Include in your description an analysis of how long it would take to create a concordance using your data structures in terms of t, the number of words in the text, and how long it would take to search the concordance in terms of n, the number of words in the concordance.

Turn in Part I in a text file called README.txt. Please no Word documents.

Part II – 50 points

Implement the concordance using the data structures you described in Part I. You may use STL or any class you wrote during the quarter.

The program should be able to handle the following operations:

• Create a concordance from a text read from a file
• Create a concordance from a text read from a file, filtering out a list of common words (the list can be hardwired or read from another file)
• Search the concordance for a word, printing all the line numbers where it appears
• Print the entire concordance: an alphabetical listing of all words, each followed by tall the line numbers where it appears.

Partial credit will be given, but whatever partial code you write has to work, so plan carefully the order in which you do things. Programs that do not compile will receive no credit.

What to turn in

· README.txt

· All the files needed to run your program.

· A makefile that compiles your program when you type

make

and creates an executable called

conc