Midterm Examination: Programming part

No code sharing is allowed! Both offenders will have their score cancelled and will receive a much harder problem (or zero score for the test, at our discretion).

You need to do one of the following programs, by our choice. You will find the number of your assigned problem http://www.ccs.neu.edu/home/sbratus/com1101/problembyssn.html . Instead, you may decide to do the (hard) Problem D, which also brings extra credit. If you do so, you will be asked to explain your solution in a 10 minute interview with Sergey or Mani.

You need to read the descriptions of problems other than yours, because later problems refer to earlier ones.

You need to submit:

the full print-out of your code
a working executable
if done on a Mac: your CodeWarrior project file

You can work on your program in any environment (Mac, PC, Unix). On the Mac, you can use either the Minimal Project (which includes only the standard C++ libraries) or the Core Tools Shell Project. Both are available in the course directory on Ambassador.

Problem A

Implement the class Phonebook. The phonebook contains entries (name, phone number) and is searchable by name. More exactly, the class should allow the following operations.

Add an entry (name, phone number)
Look up a phone number by name
Change an entry that corresponds to name
Print all entries in the phonebook (in any order)

For extra credit, you can also implement the following features.

Delete an entry (by name)
Keep and print all entries in alphabetic order (Hint: strings have a comparison operator < )

There are two important issues to address:

at no point there should be two entries under the same name. If adding a record with an already existing name is attempted, the operation should fail.
if an name is not found on lookup, a special string should be returned. It may be an empty string or "not found". Make sure your code handles this special case gracefully.

You can base your class either on an array or on a linked list. You are allowed to set a limit on the capacity of your Phonebook, and refuse "add" operations after it has been exhausted. You will receive extra credit for solutions without such limit. Of course, the amount of information contained in an object cannot be larger than RAM can hold.

Your class must be able to work with the following primitive driver program. Notice that by using the CoreTools functions RequestInt() and RequestString(..) from IOTools.* you can re-write this example to make it even shorter.

#include <iostream.h>
#include <string>

#include "phonebook.h"  // the header file with your phonebook class

int main(){
  Phonebook phb;
  
  string cmd;  // command
  string inp1, inp2;  // input for a command
  while( true ){
    cout << "Enter command (add, find, change, all): ";
    cin >> cmd;
    if( cmd == "add" ){
       cout << "Name? ";
       getline( cin, inp1 ); // a name may contain spaces, hence getline
       cout << "Number? ";
       getline( cin, inp2 ); // phone number may contain spaces too 
       phb.Add( inp1, inp2 );
    }
    else if( cmd == "find" ){
       cout << "Name? ";
       getline( cin, inp1 );
       cout << "Result: " << phb.Find( inp1 ) << endl;
       // From this you can see that Find(..) returns a string.
    }
    else if( cmd == "change" ){
       cout << "Name? ";
       getline( cin, inp1 );
       cout << "New number? ";
       getline( cin, inp2 );
       phb.Change( inp1, inp2 );
    }
    else if( cmd == "all" ){
       cout << "All entries:\n"; 
       phb.PrintAll();
    }
    else if( cmd == "quit" )
       break;   // leave the loop 
    else 
       cout << "Unrecognized command. Please try again.\n";
          	       
  }
  cout << "Bye now\n";
  return 0;
}

Naturally, such a phonebook is not much fun to use. Still, if instead of command line inteface someone writes a windowed interface for it (with dialog boxes, animations etc. etc.), it may become quite usable. The class Phonebook, though, would not need to change at all.

Problem B

Implement a class Gradebook. The gradebook contains entries of the type (course, grade) and supports the following operations:

Add an entry (course, grade)
Look up a grade by course name
Print all entries in the gradebook (in any order)
Compute the GPA based on the information in the coursebook

Choose short and simple course names, such as "com1101". For extra credit, implement the same extra functionality as for Problem A.

For this program you have to address the issues of duplicate entries (they are not permitted), and of lookups for a course which is not in the list. See Problem A for details.

For the driver code, refer to example for Problem A, with the commands being "add", "find", "all", "gpa" and "quit", and the methods of the class Gradebook called Add( string, string ), Find( string ), PrintAll(), GetGPA() respectively.

Problem C

Implement a class MovieList. It contains the records (title, rating). A rating is a number between 1 and 10. The class supports the following operations:

Add an entry (title, rating)
Look up a rating by title
Print all entries in the list (in any order), with ratings
Print all titles with the ratings higher than a given number (takes an integer as input argument)

Duplicate entries (i.e. those with the same title) are not allowed, and an attempt to add a title already in the list should fail.

For extra credit, implement

deletion of records by title
printing the list sorted by ratings

The driver code is analogous to that of Problem A, with commands "add", "find", "all", "above" and "quit" and methods Add(string, int), Find(string), PrintAll() and PrintAbove( int ) respectively.

Problem D, extra credit

This problem may be chosen instead of the assigned problem. A quality solution is expected.

Implement a dictionary using a hash table. Fill the dictionary by reading in a file containing a list of words of the English language (provided). Then read a text and print out all words not in the dictionary (i.e. possible spelling errors). Your program may ignore case and punctuation. Further details are at http://www.ccs.neu.edu/home/sbratus/com1101/hash-dict.html