Individual Programming Assignment #4
CS 163 Data Structures
Programming – Goal: The goal of this program is to create a binary search tree
(BST) and to implement ALL repetitive BST algorithms recursively.
Background: The advantage of a binary search tree is the ability to retrieve our
data using a logarithmic performance assuming that the tree is relatively balanced,
be able to search for a range of information and obtain our data in sorted order. In
program #4 we will be implementing a “Table ADT” (which means we are
working with the “value” of the data) using a binary search tree as our data
structure (instead of a hash table).
Program Assignment #4 Specification and Data structure:
For program #4, we will be using a binary search tree as our data structure. We
will be working with the same information (saving endangered species) as in
Program #3 but replacing the hash table with a binary search tree. I would suggest
keeping your external data file, although this is not a requirement. For each
animal, you are still keeping track of the following:
1. Common Name of the Animal (e.g., Warthog)
2. Scientific Name (e.g., Phacochoerus africanus, P. aethiopicus)
3. Location (e.g., Southern Africa)
4. Description (e.g., Forage during the morning and early evening)
5. Life span (e.g., 11.5 years)
6. One other of your choice (must be last in the file and consist of character
data)
The beauty of the binary search tree is that we now can get our data in sorted
order! We couldn’t do that with a hash table.
Programming Data Structure:
• Implement the table abstract data type using a binary search tree.
Remember the term “table ADT” means that we are working with the
“value” of the data. Each node is organized by the name.
• The following should be public wrapper functions for the private recursive
counterparts. The client should have a menu that allows the choice for
adding, display, removing and retrieval to allow testing of the following
tasks:
CS163 Fall 2023 Assignment #4
The Table ADT operations are:
Task 1. Constructor
Task 2. Add a new Animal from the client
Task 3. Display all – in sorted order by the Animal’s Common Name
Task 4. Remove by the Animal’s Common Name
Task 5. Retrieve the information for a given Animal, by their name (this is
not display)
Task 6. Destructor
Task 7. Display all animals within a range of a lifespan (so you will need to
provide two arguments representing the starting and ending of this range.
Task 8. Determine the height of the tree (used to assist in evaluating the
performance of your software)
In your efficiency Writeup...
In your efficiency writeup, discuss the relationship of the shape of the resulting
tree based on the order in which the data is obtained. To understand this, you
will need your code to determine the height of the tree in relation to the number
of data items.
CS163 Fall 2023 Assignment #4
CS163 - Checklist for First Week of Cycle
Cycle Monday Tuesday Thursday Friday
First week Discussion
(Planning
Design)
Draft .h file Discussion
Response
Revised .h
Draft .cpp
Tasks #1-3
Second week Discussion
(Planning
Testing)
Progress
Submission
Tasks 4-6
Following
Monday:
Discussion
Response
Following
Monday:
Finished
Assignment &
Writeup
______1 Monday - Begin by Collaborating with your Virtual Group
• Using the Canvas Discussions
• You may share your design ideas:
- Explore sample prototypes that meet the rules of Data
Abstraction and share those among your group (although don’t
share so much that no one else has anything left to do!)
- Make sure to ask a question to help others respond to you!
______2 Tuesday - Submit a Draft .h file
• Due by 7pm
• Submit the URL of your gitlab repository to Assignments on
Canvas
• It should contain prototypes for all of the public functions
outlined in this assignment with arguments and returned types
• It should contain all of the structures and class(es) planned
• You may change your .h after this
______3 By Thursday – Constructive Response to your Virtual Group
______4 Friday - Submit a Revised .h file and a Draft .cpp file
• Due by 7pm
• Submit the URL of your gitlab repository to Assignments on
Canvas
• Implement and demonstrate Tasks #1-3
• Provide “stubs” for the rest of the functions
• Have header comments (1 paragraph minimum) for each file
CS163 Fall 2023 Assignment #4
CS163 - Checklist for Second Week of Cycle
Cycle Monday Tuesday Thursday Friday
First week Discussion
(Planning
Design)
Draft .h file Discussion
Response
Revised .h
Draft .cpp
Tasks #1-3
Second week Discussion
(Planning
Testing)
Progress
Submission
Tasks 4-6
Following
Monday:
Discussion
Response
Following
Monday:
Finished
Assignment &
Writeup
______1 Monday – Discuss Testing with your Virtual Group
• Using the Canvas Discussions
• You may share how you plan to test your code
- Talk about the concept of unit testing and how that can be
applied to building abstract data types
- Make sure to ask a question to help others respond to you!
- Remember to include a discussion of the social, ethical and
security implications of the software
______2 Tuesday - Submit a Progress Submission
• Due by 7pm
• Submit the URL of your gitlab repository to Assignments on
Canvas
• It must compile and run to gain credit
• Implement and Demonstrate Tasks #1-6
______3 Following Monday:
– Constructive response to your Virtual Group
• Are there changes you would make to the approach for the
next programming assignment?
______4 Following Monday:
- Submit a Completed Assignment with Efficiency Writeup
• Complete the remaining Tasks
• Due by 7pm
• Submit to Assignments on Canvas
• Tar or Zip all of the .h and .cpp files together
• Upload the Efficiency Writeup separately