Due Feb 6th, 6pm, EECS 380 box in room 2420 EECS

You are to turn this in with all parts *stapled* together.
Please use two-sided printing to reduce the amount of paper in homeworks,
if you can (graders are having trouble carrying all homeworks!).
Make sure to mention the following on the first page:
your name, uniquename and the number/time of your discussion section.

- Implement a container class based on dynamically allocated array, with simple operations.
- Implement a single-link list.
- Empirically measure complexity of simple operations implemented for the two containers and estimate the big-Theta.
- Study operations with sorted ranges (set_union/set_difference/etc)
- Start using STL
- Learn how to process command-line options using the supplied UTIL library

class EECS380_DynContainer { // add your own data declarations public: EECS380_DynContainer(unsigned maxSize); // constructs an empty container with given maxSize EECS380_DynContainer(unsigned maxSize, unsigned size, double val); // constructs a container populated with size // values val; size must be <= maxSize ~EECS380_DynContainer(); unsigned getSize() const; void prettyPrint() const; void push_back(double val); // adds the value at the end, increases size double pop_back(); // returns the last value, decreases size double& operator[](unsigned idx); // gives read-write access to elmement with index idx unsigned getIdxByElt(double val) const; // returns index of the first elmement equal to val // UINT_MAX if not found void insert(double val, unsigned idx); // inserts value at index idx and increases size };The indexing operator must perform a range check and exit with an error message if the argument exceeds current size. Make sure that your class works correctly --- by writing several simple programs in which you construct simple container objects, populated or not, perform simple operations and prettyPrint the objects before and after every operation.

class EECS380_LinkedList1 { // add your own data declarations public: EECS380_LinkedList1(); // constructs an dempty list EECS380_LinkedList1(unsigned size, double val); // constructs a linked list populated // with size values val ~EECS380_LinkedList1(); unsigned getSize() const; void prettyPrint() const; void push_back(double val); // adds the value at the end, increases size double pop_back(); // returns the last value, decreases size double& operator[](unsigned idx); // gives read-write access to elmement with index idx unsigned getIdxByElt(double val) const; // returns index of the first elmement equal to val // UINT_MAX if not found void insert(double val, unsigned idx); // inserts value at index idx and increases size };The getSize() and push_back() methods must be implemented with O(1) complexity (hint: you need to maintain current size and the tail of the list). Make sure that your class works correctly --- by writing several simple programs in which you construct simple container objects, populated or not, perform simple operations and prettyPrint the objects before and after every operation.

The values of N must be passed as unsigned command-line parameter -n.

Similarly, write a program that measures, for each container, the runtime of one push_back and one pop_back operation independently, amortized over a large number of such operations. For the array-based container, use size = maxSize at construction, and then start by performing a large number of pop_back() ops followed by an identical number of push_back() ops. There should be fewer pitfalls in the case of linked list. Plot the readings as four functions of size. If the results are significantly different from one another, you should graph them on different output plots.

Similarly, measure and plot the runtime of one operator[] and one insert operation for both containers (four functions on one plot), assuming that these operations use size/2 as their index argument.

For each of the above, write down on the plots (with a pen) the big-Theta complexities.

Your program must be capable of performing all of the above measurements without recompilation. This is to be achieved by requesting specific type of output by using command-line options (e.g., -m for memory measurement, -pushB for push_back measurements, -popB for pop_back, etc,)

Assume that the values stored in two containers implemented in part 1 have been sorted and do not repeat in the same container (i.e., populate the containers with such values only).

Extend each container by a method set_difference (+ any other extensions necessary for that) that takes const references to two other containers of the same kind and populates its container with all values stored in the first container, but not stored in the second. All previously-stored element in this container need to be removed.

For example, the set_difference of

1, 2, 3, 4, 5,....N and 1,1.5, 3,3.5, 5,....N (assume N is odd) is 2, 4, 6,...By running small examples and pretty-printing your containers, make sure that your code works just as STL's set_difference() function on conventional arrays (it should be trivial to modify the STL part of the tutorial to do this).

Measure the performance of your implementations of set_difference
(array-based and list-based) as a function of N on the example above.
**Your implementations for both containers need to run in linear time,
i.e., O(N)**. If they do not, you need to improve them.

You need to turn a plot with three functions on it (your two implementations of set_difference and STL's implementation) and big-Theta complexities next to them.

Your program must be capable of performing all of the above measurements without recompilation. This is to be achieved by requesting specific type of output by using command-line options.

Make sure to compile/run your program in two ways: (1) compile the command-line option

- Complete source code printouts (.h and .cxx files) for your two container classes
- Gnuplot printouts with measurement results and big-Thetas for Part 3 (estimated bytes-per-value can be written on the memory plots)
- Source code printouts for Part 4.
- Gnuplot printouts with measurement results and big-Thetas for Part 4