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.
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.