C++ (Object Oriented Programming)

Recursion & Set ADT.

The programming is divided in to two parts. First, we need a function that processes the elements of an array using recursion. Then, we implement a set class template using an array.

Requirements:

-Use of Binary search

Find the largest element in an array using the recursive technique.

Each call to the recursive binary search function processes a portion of the array identified by the first and last indexes of the subarray of the subarray to be processes by this call.

1. First, we need a function called maxArray that will return the largest value in an integer array. Create a driver to test the function. The maxArray function and driver program can be in the same file

Algorithm:

Use the given algorithm to find the largest value in the array.

if (anArray has only one entry)

return the value of that entry

else if (anArray has more than one entry)

return the maximum of maxArray(left half of anArray) and maxArray(right half of anArray)

BinarySearch function always return a value.

For this program, your function will never be called with first > last. If familiar with the assert statement, you can use it to handle this error.

Objectives

A set is like a bag, except that duplicate entries are not allowed in a set.

-use arrays inside class object

-implement ADT with an interface and class templates

-A set has the same operations as a bag except as noted below. The required changes for the set operations are:

• Add operation - Duplicate entries are not allowed in a set. If you add an entry that is already in the set, the set is not updated, but the operation is considered successful. If you add an entry that is not currently in the set, the entry needs to be added and the count of items in the set incremented by one. If the entry cannot be added for any reason, the operation fails.
• Get frequency of operation - Delete this operation. Since duplicate entries are not allowed, the only possible results are zero or one. This information is already provided by the contains operation.
• You will provide a default constructor that initializes the set to an empty set (like the bag constructor).
• Add a second constructor that has 2 parameters - an array of ItemType elements, and a count of the number of elements in the array. Use the array elements to initialize the set.

Requirements

1. Vectors are used in the toVector() method of the class, and in the driver program that tests the class. Do not use vectors anywhere else. The main objective of this assignment is to use arrays inside class objects.
2. Do not use any C++ templates from the STL except as noted in Requirement 1.
3. You are encouraged to reuse class methods by calling them from other class methods (where appropriate). If you already have a tested method in your class that will do what you need, use it instead of copying the code to your new method.

Set Interface

Create an interface for your ADT called SetInterface. Be sure to include the changes listed above that need to be included in the interface. Use the BagInterface class template as a model for your interface. You must include updated documentation for your set interface operations (methods) similar to the documentation in the BagInterface file.

Set Implementation using arrays

Create a class template called ArraySet to implement your ADT. You can combine the class template definition and class template implementation in a single header file (as I did in the example Bag code provided). Be sure to include the changes listed above that need to be included in the ArraySet class template.