Due Date
See the
calendar for due date.
Objectives:
- Build a pointer-based tree
- Write recursive algorithms
Description:
You guessed it, for this lab you get to store DNA, RNA and amino acid (AA) entries in a pointer-based binary search tree (BST)!
In addition to the relevant classes from the last lab, you will need a class to manage the BST.
This class should contain the necessary methods to add, retrieve, remove
Sequence* items.
Each of these methods need to be a recursive method.
Requirements:
Use the following labTrees-main.cpp file, which has the main() function in it. Do not modify it.
You must have a separate header and implementation file for the above classes.
Name the project for this assignment labTrees-yourlastname.
If attempting to delete or print a sequence that doesn't exist, print out an error statement to the specified output file and continue processing commands.
Your program must compile and run in both Visual Studio 2012 or newer and on ranger. On ranger, it must compile with the following command:
g++ -std=c++0x *.cpp -o labTrees
You can assume that information in the input files is syntactically correct and that they each have a newline at the end of the file.
You can use labTrees-inputA.tab and labTrees-inputB.tab to assist your development.
Please produce your own input file(s) for testing.
Output needs to be stored in the file specified in main() and match the format given in labTrees-answerKeyA.txt:
Importing labTrees-inputA.tab ...
Printing 9999 ...
Can not find item (9999)!
Obliterating 9999 ...
Can not delete item (9999), NOT found!
Entries: 0 total
Adding 17 ...
Adding 117 ...
Adding 217 ...
Printing 17 ...
DNA: Label: CISY_EMENI ID: 17 Sequence: cttggacagcatggagttctcgagccaaatttgtcggtacactaccttaaacagccctagcgaatctcggcaacatgtgacggttggtatcgtgcgcgcttgtctgggccgggccgatgcgctatag Length: 127 cDNAStartIndex: 10
Printing 117 ...
RNA: Label: CISY_EMENI ID: 117 Sequence: auggaguucucgagccaaauuugucgguacacuaccuuaaacagcccuagcgaaucucggcaacaugugacgguugguaucgugcgcgcuugucugggccgggccgaugcgcua Length: 114 Type: mRNA
Printing 217 ...
AA: Label: CISY_EMENI ID: 217 Sequence: MEFSSQICRYTTLNSPSESRQHVTVGIVRACLGRADAL Length: 38 ORF: 1
Obliterating 17 ...
Entries: 2 total
Obliterating 117 ...
Obliterating 217 ...
Printing 1234567890 ...
Can not find item (1234567890)!
Obliterating 1234567890 ...
Can not delete item (1234567890), NOT found!
Entries: 0 total
Note: The error messages need to also be sent to the output file.
Make a file named rubric-yourlastname.txt in your project directory with a completed rubric. Specify estimated points for each entry including the number of hours spent.
Do not include spaces in directory names or file names.
Submission
Before submitting your project, remove the
debug and
ipch directories (if present) and any
.sdf files.
Zip the whole project folder (
e.g., by right-clicking on the folder and choosing
send to::Compressed (zipped folder) in Windows Explorer). Name your zip file as
labTrees.zip.
Make sure that all of the source code files (especially
labTrees-main.cpp) are in your zipped file. You can verify this by coping your zip file to a temporary location and uncompressing it.
Submit your zip file at
https://3110.cs.mtsu.edu/. For further instructions, please see the
Miscellaneous page.
Rubric:
Points Item
----------- --------------------------------------------------------------
_____ / 10 Documentation (applies to new and modified files):
All source code files (.h & .cpp) include file name, author, description etc.
Functions and variables
+ All non-trival variables are commented
+ All functions preceded by brief comments
+ Comments included before major portions of code
+ Functions should be no longer than 1 page
_____ / 42 Requirements met:
+ Recursive add, find, and remove methods
_____ / Compiles and runs in Visual Studio and on ranger
_____ / 46 Correct output (matches the format of the example & demonstrates correct execution)
_____ / 2 Completed rubric (estimates for each line including hours spent)
_____ / 100 Total
_____ Approximate number of hours spent
Notes
- Part of the grading process is automated by using diff. You should verify that your output matches the above output directly with the following commands on ranger:
g++ -std=c++0x *.cpp -o labTrees-yourlastname
cp /nfshome/hcarroll/public_html/3110/private/labs/labTrees-inputA.tab .
(echo ""; echo "") | ./labTrees-yourlastname
diff /nfshome/hcarroll/public_html/3110/private/labs/labTrees-answerKeyA.txt labTrees-outputA.txt
If the two files match exactly (which is what you want) then there should be NO output from diff. If diff shows one or more differences, fix them and run it again. To get side-by-side output (with the answer key on the left and your output on the right), replace the last line with:
diff --side-by-side /nfshome/hcarroll/public_html/3110/private/labs/labTrees-answerKeyA.txt labTrees-outputA.txt
For details about interpreting the output of diff, see the Using diff section on the Misc. webpage.
- Always download files (especially the input files) instead of copying and pasting them. This will preserve the newline(s) at the end of the files.
Optional:
- Extend your BST class to provide a way to perform preorder traversal of each node in the tree, which should print out the contents of the item.