CSE 143 Summer 2001 Homework 1 Due: Electronic submission by 9:30 pm, Wednesday, June 27.  Paper receipt and written report due in quiz section the following day.

Overview

A small start-up named Microsoft is working on a new word processing program, Word.  They need help implementing the document spell-checking feature and have hired you for the job.  (Sorry, no stock options involved).  As with all assignments, please read the instructions all the way through before beginning.  Read them once again before you turn in your assignment, to be sure you've left nothing out.

Concepts

The purpose of this assignment is to review some ideas from previous courses and explore basic parts of C++.

• Review of fundamental programming concepts (things you should be familiar with from CSE142)
  • functions
  • conditional and loop statements
  • data structures, including nested arrays and structs
  • concepts involving files (open, read, write, close)
• Source file organization (.cpp and .h files)
• C++ strings
• C++ stream I/O and files 
• C++ reference parameters

Program Specification

The program should operate in two phases:

1. When it starts, it should open a file named "words.txt" in the current directory, read the contents of that file, and store the information in a suitable data structure.  Details of the file format are given below.
2. After reading the file, the program should repeatedly ask the user to enter sentences (like "The cow jumped over the moon", or "green eggs and ham").  After each sentence has been entered,  the program should look for misspelled words in the sentence which match those found in the data structure initialized in step 1, and then replace the misspelled words with the correct version (also located in your data structure).  Finally, the program will print out the correctly spelled sentence as well as the total number of errors found.

File Format

The file contains two pieces of information for each word: The misspelled version of the word, and its correct spelling .  To keep things simple, words are restricted to be a single string.  So, for example:

meloncholy    melancholy 

would be a correct entry, but,

Seattle Maraner   Seattle Mariner

would not.

The end of the file is indicated by an entry with the symbol ". ." (two single period, separated by a space.).

You may assume that there are at most 30 total words in the input file (not including the end marker with periods as the word).  You should also assume that the input file contains clean data, i.e., you do not need to check for input errors like duplicate words, poorly formatted words, etc.

Example:  Here is a sample words.txt file giving various misspelled words.

mispelled misspelled 
Mispelling Misspelling 
Maraners Mariners
acentuate accentuate
teh the
certanly certainly
Teh The
cemetary cemetery
wierd  weird
exceding  exceeding
ar are
. .

Interaction

Once the program has read the words.txt file, it should prompt the user to enter a sentence, terminated by pressing <enter>.  You may assume that sentences are at most 200 characters long.  When the user presses <enter> your program should:

• Break the sentence into individual words
• For each word, do a look-up in the 'misspelled words' portion of the data structure you created from the words.txt  file
• If a match is found, replace the misspelled word with its correct spelling
• If no match is found, make no changes to the word
• Print out the final, corrected sentence, as well as the total number of errors found.
• Prompt the user for another sentence.

The word must exactly match the name in the database, including capitalization.  

When the user is done, she should enter a single period (".") to indicate that the program should terminate execution.

Example:  Here is a sample of what the interaction should look like, using the data given above. User input is underlined and in italics, like this.

Enter sentence: Teh Maraners ar exceding expectations
The Mariners are exceeding expectations.
4 Errors Found

Enter sentence: Mispelling words is certanly a problem
Misspelling words is certainly a problem
2 Errors found

Enter sentence: .

Implementation Requirements

A primary purpose of this assignment, besides learning basic C++, is for you to gain experience designing a program, including data structures, breaking the code apart into functions in some sensible way, and so forth.  But there are a few specific implementation requirements - things you must do as specified here.

You should split your code into two different source files, and partition your code into the files so that related code is together.  In particular, you will need a data structure to hold the mispelled/correctly spelled word pairs. You will also need various functions to manipulate this data structure, for example, adding new information to it, looking up a word in the structure, getting the correctly spelled version, etc.

You must separate your source code so that the functions that process the internal details of the word data structure are in a separate source (.cpp) file from the main program.  You will also need an associated header (.h) file containing declarations of the data structure(s) and function prototypes for the routines in this source file.  The source (.cpp) file containing the main program should #include the header file to access the data structure definitions and function prototypes.  The main program must call appropriate functions to manipulate the misspelled word data structure - it should not access the internal details itself.

Other Implementation Requirements

• Use C++ stream I/O (cin, cout, ifstream, etc.).  Do not use printf/scanf/fscanf or other C library functions for I/O.
• Use C++ reference parameters as needed.  Do not use explicit pointers.
• Your code should be clear and readable.  See the style guide for detailed suggestions.

Implementation Hints

• Remember to use #include "file.h" to include header files that you write and that are in your project folder.  The angle brackets in #include <library> are used to indicate libraries that are part of Visual C++ or other implementations
• Look at the documentation for the strtok and gets function.  This function will allow you to break up a sentence string into individual word strings. (a.k.a. tokens).  In VC++, you can view the documentation by simply selecting Help->Contents, then entering the function you wish to search for.
• Your program should handle punctuation correctly, try using the separator string of strtok for this
• You can assign character string variables ( type char *) to string type variables

Testing

Part of your job as a programmer is to verify that your code works by running appropriate tests.  That means more than just trying it with the example data given above.  You need to invent test data that will check your program under various conditions.  For example, your tests should check that the program works properly if

• The words.txt file contains no data (just the ". ." that signals the end of input data)
• The file contains entries for exactly 30 words (the maximum possible)
• The input sentence is blank, or contains exactly 200 characters.

As part of the report you turn in with this assignment (see below), you will need to describe how you tested the program and why you believe that your tests demonstrate that it works properly.

Sample Program

There is no sample program for this assignment; you should create a program that works as specified.  In cases where the specification is not clear, you may need to make some reasonable assumptions.  Also, feel free to discuss issues about the specifications on the course newsgroup, in sections, with your colleagues, etc.

Help!!! Where do I start?

In any non-trivial project, programming or otherwise, the job can often seem overwhelming at first - too many things to do all at once and no clear idea where to start.  An important skill to develop is to figure out what you can do first, without having to finish other things.  Here are some suggestions.

1. The place to start is not, I repeat not at the computer keyboard.  You have to do some thinking and planning before you start writing code.  Premature use of the computer is guaranteed, I repeat guaranteed to waste huge amounts of your time.
2. Start by planning, on paper, the data structures and functions you will need.  Write down fairly detailed data structure declarations.  Draw pictures.  Figure out what the functions need to do and what their parameters should be - but don't spend much time on implementation details now.
3. Figure out how you will test your code.  As you design data structures and specify functions, think about how they could fail(!) if you make a mistake.  Design a test that will catch that bug if it happens.  Write it down now, not later.
4. Only when you've gotten this far should you start writing detailed code on the computer.  You should develop the code bit-by-bit, getting some parts working, then add more until you have everything done.  You might try first getting the data structure definitions right, then implement the code to read the data from the file and store it in the data structure.  Inspect the data structure with the debugger or by printing it out at this point to verify that things are working so far.  Then add code to interact with the user, reading and correcting sentences.  Keep testing as you go.

Time spent planning and thinking at the beginning of the project will be more than repaid by time saved that would otherwise be needed to debug and fix problems.

Report

When you turn in your program, you must also turn in a short report that discusses the following issues:

1. Planning - How did you plan your code design for this problem.  What kinds of data structures and functions seemed necessary?
2. Implementation - Describe the implementation.  What data structures did you use?   How did you structure the code?  Were there any significant differences between the original design and the final program?  If there were major changes, why were they needed?
3. Testing - Describe the test cases you chose.  Describe the kinds of bugs you found using tests.  If some of your test cases still don't work, or there are parts of the program that are incomplete, describe that.  Attach some of your test cases and results to support your claims.
4. What did you learn from completing this project?  This could include things you learned about program specification and design, C++ language issues, developing test cases, debugging, etc.

This report need not be long, but it should be complete enough to give us a good picture of what you accomplished.

Electronic Submission

When you've finished your program, turn it in using this turnin form. Print out the receipt that appears, staple it and your report together, and hand it in during quiz section.