Required C++ Expert -- 2

Study ADT Bag, and its implementations Array Bag and
Link Bag, describe the most important things you have learnt
from both implementations, in terms of:
a. Encapsulation, Inheritance, Polymorphism
b. Describe differences between Array Bag and Link Bag,
when doing:
• Add an item
• Remove an item
• Search an item
2) Study the recursive algorithm “The Towers of Hanoi” in
chapter 2.
a. Describe the function
b. Demonstrate that this function is recursive by listing the
criteria of a recursive solution and stating how the function
meets each criterion.
3 Using UML diagram, design an ADT Chain by using a
linked chain of Nodes with generic item type (template).
Determine the classes and their private member variables
and public member operations.
Include some operations such as:
a. add one Node to the front of the Chain
b. remove one node from the end of the Chain

c. search a special node from the chain d. any one or two
other operations you feel important.
Part II: Programming [10 marks]
1) Create a C++ solution that implement the design in 1.3)
above:
a. a .h header file that defines all the classes in question.
b. a .cpp file that implements all the classes in question.
c. a .cpp driver program with a main() function that uses
and tests these two classes.
Try to test two item types: string, and integer. (Hint: using
template for item type)
2) In your report, please mention
1) what were completed with satisfaction;
2) what were difficulty to finish;
3) what special features you implemented, if any

-- Write a recursive binarySearch function for an array
of strings (already sorted), that returns the indexes of all thestrings whose first letter is “A” / “a”.For example, for anArray = {“Arrow”, “art”, “box”, “curve“,
“line”}, the search result should show: indexes = {0, 1}
You should set the target letter to be a variable, so that we
can use your function to search strings starting with any given
letter withing a-z / A-Z.
3. Write a main() function that tests all the above functions,
with two test cases for each function. You may create a menu
of choices for user to choose which function to test.