C M S C     2 1 4
C o m p u t e r   S c i e n c e   I I
F a l l   2 0 0 3


Project #3

Due Thursday, October 30th, by 11PM

Checklist

Preliminary Material

Project 3 is worth 10% of your grade.

This project enhances and adds to Project 2. It will implement
a binary search tree and a modified binary search tree.

Your Encoder dll MAY NOT BE CIRCULAR in this project.
You will forfeit all points if we detect circularity.

binary search tree

  • a binary tree where the nodes are ordered
  • leftchild(data) < parent(data) < rightchild(data)
    for each subtree (consisting of a parent and 2 children)
modified binary search tree
  • same definition as above with a modification to the node
  • the modified node contains a pointer to the parent in
    addition to pointers to left and right children.
garble
  • a word or words whose letters get transposed
  • a word or words that are not found in the codebook.txt and is not part of an expression

Purpose

This project requires you to implement a binary search tree. It also enhances the features of the Encoder and Decoder. The goals of this project are to:

  1. Understand and implement a binary search tree.
  2. Understand and implement a modified bst.
  3. Locate expressions that are more complicated.
  4. Handle garbles.
  5. Write and throw exceptions when appropriate.
  6. Enhance the encoded output, for security.

Academic Integrity Statement

Please note that *all* programming projects in this course (including this one) are to be done independently or with the assistance of the instructional staff of this course only.

Please review the policies outlined on the class syllabus concerning the use of class computer accounts and concerning the University's Code of Academic Integrity. The instructors of this course will review the programs submitted by students for potential violations of the Code of Academic Integrity and if it is believed that a violation has occurred it will be referred to the Office of Judicial Programs and the Student Honor Council.

Hardcoding is considered a violation of academic integrity

Style Guide

Students are expected to write "clear and legible" code. Please review the following Style Guide which specifies how students in CMSC 214 are expected to lay out their code: 

http://www.cs.umd.edu/class/spring2003/cmsc214/Projects/styleguide.txt

FAQ

Answers to "frequently asked questions" will be posted via the main projects page. Prior to asking a question or submitting a project you should check the FAQ to see if any important information has been covered there. In addition to answers to FAQ's any important information pertaining to a project will be posted on it's FAQ.

E-mailing Questions

DON'T email questions. We cannot keep up with the numerous emails about a project. GO SEE A TA or an instructor during office hours. We will generally NOT respond to email questions about the project.

Project Overview

For this project you will be required, among other things to

  • replace the dll data structure in Codebook with the bst class Bst.h
  • write the code for the class ModNode.h
  • write the code for the class ModBst.h
  • make changes to the Encoder and Decoder classes
  • use AI (artificial intelligence) to construct more complex expressions

In addition, you will include, and add to, myExceptions.h and
myExceptions.cpp

In the class posting accounts (~bt214001) you can find the header files for the classes.
The following rules MUST be adhered to:
  • No public functions or (public, protected, or private data members) may be added to the header files.
  • Your output must match our output, an example of which is provided in primary.output
  • You may not change the input - as provided in primary.input
  • You may not change the input - as provided in secondary.input
  • This project MUST be submitted in order to pass this course.
  • Projects submitted after 2 days late but prior to Dec 8 at
    11PM receive a grade of 10 (out of 100) points.

Tar up your project two files or make a copy and store on another computer, disk or account before you begin this project.

Copy the header files Pair.h, Encoder.h, Bst.h, Node.h, Decoder.h, myExceptions.h, DllIterator.h, Decodebook.h, ModNode.h and ModBst.h into your account. Some of these have changed.

Copy your TNode.h and TNode.cpp into your account.

Copy myExceptions.cpp

Make any changes to your .h and .cpp files from Project 2.

Write the code that implements the member functions for these classes. Note: you may NOT change the public methods in the header files but may add private methods as needed. You may NOT add private, public or protected data members. You may not add ANYTHING (including comments) above the comment that tells you to insert your private member functions after it.

myExceptions.cpp contains exception classes that are called from several of your .cpp files. You must have at least 12 exception classes:

  • 2 were written for you
  • 4 you wrote for project 1
  • 3 you wrote for project 2
  • write at least 3 new exceptions that you determine are necessary

Next you should write and/or update unit tests for each of your classes:

  • testPair.cpp
  • testNode.cpp
  • testEncoder.cpp
  • testDecoder.cpp
  • testTNode.cpp
  • testBst.cpp
  • testModNode.cpp
  • testModBst.cpp
  • testDecodebook.cpp
  • testDllIterator.cpp

Remember to keep backups on a different system - perhaps WAM. You can still code on WAM but only the g++ compiler is available there.

And finally you should write a:

main.cpp

It should contain a main function that will call Encoder's reader() method, process the information just read, build the doubly linked list that holds the message, build the bst that holds the codebook (in Bst), build the vector holding the decoded message, build the vector that holds the decodebook (in Decoder), print the plaintext message, and print the code vector.

Your main program should use the classes created earlier to accomplish it's task. You may not write any other classes.

Assumptions

You may assume that

  • There may garbles in the input plaintext or code.
  • All words that do not appear in "codebook.txt" are part of an expression
    or the plural of a word in the codebook or a garble. Examples of an expression are
    "united states" and "of course"
    • "united" might not be in codebook but "united states" will be
    • "course" might not be in codebook but "of course" will be
    • Do not assume there will be only 2 words in an expression.
  • Expressions may be more complicated.
  • Any codes that can be doubled will not have their doubled value in "codebook.txt".
  • The word "halt" will never appear in the original message.
  • The input will not be empty. Each non-empty line will terminate with a newline.
  • There will be neither leading not trailing blanks in the plaintext or coded messages.
  • Plaintext messages may contain upper/lower case letters, white space,
    and punctuation, but NO digits.
  • plaintext input will be similar to that in Project 2
  • the input file may be several lines long
  • code input will be similar to that in Project 2
  • the output file may be several lines long

Approach

You might want to take a 6-pronged approach to this project:

  • Task 1
      • Correct any problems you had in Projects 1 and 2 that might impact this project.
  • Task 2
    • Get rid of the files Codebook.h and Codebook.cpp
    • Using Bst.h, create Bst.cpp and implement each method in Bst.h.
      • Your pairs in codebook.txt will no longer be stored in a doubly linked list.
      • The pairs will be stored alphabetically on the plaintext words/expressions in a binary search tree
    • erase() in Bst.cpp must implement one of the following methods for deleting a node with 2 children from a BST:
      • right subtree successor
      • left subtree predecessor
      • easy right pullup
      • easy left pullup
    • Create the test file testBst.cpp and thoroughly test your bst class.
  • Task 3
    • Make the changes to any classes, such as Encoder.cpp that were affected by the changes to Codebook becoming Bst.
    • Update your test files for any class that has changed.
  • Task 4
    • Fix "halt" logic in Encoder and Decoder.
      • "halt" is decremented by 7 each time it is encountered in
        encode() in Encoder.
      • any code not found should be checked to see if it is a decremented
        "halt". 0935 will be the first occurrance of "halt", 0928 the 2nd, etc.
      • in Decoder, decode various versions of "halt" to a period.
      • in Decoder, decode any non-"halt" 4-digit code that is not part of an
        expression to the "garble" lookup 4-digit code. (Do not hardcode this because
        our codebook.txt will have different values.)
    • Make the changes to checkCodebook(). It must now handle garbles.
      • Handling a garble should not affect any other words/expressions around it.
      • a plaintext message like: I htae cats. should translate to 2945 5555 6072 0935
      • a coded message like 4924 1486 5555 0935 should translate to we both garble.
    • Update testEncoder.cpp and testDecoder.cpp
  • Task 5
    • Create ModNode.cpp to hold pairs in your ModBst class.
    • Write testModNode.cpp
    • Write ModBst.cpp which contains a ModNode * (a pointer)
      • It is strongly suggested that you make a copy of all your working files
        and put them in a separate directory in case things go badly and you
        destroy working code.
      • copy Bst.cpp and change the functions as needed.
      • most of the functions will not change much (if at all)
      • when you test this, you are going to have to make copies of classes that used to #include "Bst.h" that will now #include "ModBst.h"
      • call these copies, Mod*, ie Encoder.cpp becomes ModEncoder.cpp
      • in your makefile, have a label p3mod:
        • this will compile the appropriate files to run the same primary and secondary inputs but will use Mod* files and other files that were not changed.
    • Write testModBst.cpp.
  • Task 6
    • This is 5 points extra credit so do this only after all else is working correctly
      • Write code in checkcodebook() that handles more complicated expressions.
      • Let's assume words in the Bst are represented by "X"s and those not in the Bst are represented by "Y"s.
      • We could have an expression
        XX XXX YY XXXX YYY X
      • If your code can handle this or other such expressions correctly, you will receive 5 extra points. (top score is 105)
      • If this does not work or you do not implement this, your top score will be 100
      • An example would be a message which contains the expression "the principality of monaco". If "the" and "of" and "the principality of monaco" are in codebook.txt but not "principality" nor "monaco" are in codebook.txt, then it requires more logic and code to find such an expression. This is not the relatively easy version of finding an expression such as that in project 2.
      • Do not assume the expression can only be as stated above.

Clarifications

All clarifications will be in the FAQ.

Read the checklist - a link is at the top of this file..

Sample I/O

You may assume:

  • There are no blank lines in the input file.
  • Each line terminates with a carriage return.
  • The last line contains an EOF marker.
  • There may or may not be garbles.
  • There may or may not be more complicated expressions.

A primary input file and a primary output file are provided in the class posting accounts (in the appropriate directory). You should review these files. They will be named primary.input and primary.output respectively.

A secondary input file and a secondary output file are also provided for further testing of your code. However, your project will successfully submit if your program passes the primary.input.

On further secondary inputs, you will be given other plaintext or coded messages in the same format as primary.input   Your program should generate the corresponding output similar to primary.output. Additionally, we will test several portions of your code.

When your main program is compiled and run with input redirected so that it gets the contents of the primary input file (primary.input) as input, it should generate output that matches the primary output file. When we test your program we will diff your output (using diff -bwi) with that of the primary output and if it does not match, your program will be considered to not meet the minimum running standards and you will be unable to submit it.

How to Submit

Provide a makefile that creates an executable file named p3 when the command make p3 is run.

Tar up all necessary files, such as source code, including:

  • all .cpp files
  • all .h files
  • your makefile

submit p3.tar 3

Submit will start accepting project 3 submissions on 10/26/03.

See the class syllabus for policies concerning email
Last Modified: Friday, October 17, 2003 		left up down right home

Web Accessibility