Assignment

1. Write a C++ function rotate(int arr[], int d, int n) that rotates arr[] of size n to the left by d elements.

2. Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), write a C++ function maxProfit(int prices[], int size ) to find the maximum profit.

3. Given an array of random numbers, write a C++ function pushZerosToEnd(int arr[], int n) to push all the zero's of a given array to the end of the array.

4. Given two sorted arrays, write a C++ function mergeArrays(int arr1[], int arr2[], int n1, int n2, int arr3[]) to merge them in a sorted manner.

5. Given an array of size n, write a C++ function findMajority(int arr[], int size) to find the majority element. The majority element is the element that appears more than ⌊n/2⌋ times. You may assume that the array is non-empty and the majority element always exist in the array.

6. Mini-project: Extending the ADT Bag using vector

In CISC 1100 or 1400, you learned how to compute the union, intersection, and difference of sets:

A∪B = {x: x ∈ A ∨ ∈ B}
A∩B = {x: x ∈ A ∧ ∈ B}
A-B = {x: x ∈ A ∧ ∉ B}

The union, intersection, and difference of bags are defined analogously. The only real difference is that since bags may contain repeated elements, the union (or intersection or difference) of bags may contain repeated elements. For example, suppose that we define bags

A = [1, 1, 2, 2, 3, 4, 4, 4] and B = [1, 2, 3, 3, 4, 4, 5].

(Here, we use [. . .] to denote bags, similarly to the way that {... } denotes a set. Also, there's no reason to assume that a bag is sorted; we show the bag elements in sorted order to simply to make it easier to follow the example.) Then

A∪B = [1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 5]
A∩B = [1, 2, 3, 4, 4]
A - B= [1, 2, 4]

Before doing so, note that the author has given us two different implementations: array-based and link-based. The main problem with the former is that the implementer must decide how big to make the underlying array. This problem doesn't exist for the latter; however, linked structures are more complicated than arrays. However, if we were to use a vector-based implementation, then we wouldn't need to worry about how to choose the size of an array; moreover, vectors are easier to handle than linked structures. So the first thing to do is to create VectorBag, a vector-based implementation. Since vectors may be thought of as "safe arrays", the best thing to do would be to start with the array-based implementation and work from there.

Once you've done this, you should now add new operations to the VectorBag class.

Since the standard symbols ? and ? are not available on our keyboard and since union is a reserved word, let's use + and * to denote union and intersection; of course, - is the obvious choice for denoting set difference. This means that you'll want to define operator+ (and so forth), making sure to add appropriate comments that describe what these do.

Your main task will be to design, write, and test the VectorBag class.

- VectorBag.h: interface file for the VectorBagclass.
- VectorBag.cpp: the implementation file for VectorBag class.
- Note: you will add 3 new functions operator+(), operator -() and operator*(). The prototype of operator+() function is
VectorBag operator+(VectorBag &anotherBag);

I am providing you with the following files, which may be found in the directory ~zhou/datastr/hw/hw1 or on the blackboard for this project:

- The file proj1.cpp, for testing your VectorBag class. This file is similar to the main.cpp that the authors provide for testing the ArrayBag class. Of course, it works for VectorBag, rather than for the ArrayBag class. In addition:

• The displayBag() function will work for a VectorBag. It also displays the items in sorted order. Hence the < operation must be defined for ItemType.

• The new operation (?, ?, -) are tested.

- A working version of the program, called proj1 , for you to try out.
- Your recollection of overloaded operators (such as operator+ and such like) may be a bit rusty. I have provided you with a file point.cc, which defines a Point class that has an operator+ (for adding two Points).