EECS 380 Homework 2

Winter Semester '01

Assigned Jan 23th 2001.
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.

Goals

Homework Description

This homework consists of four parts. The first is to implement two container classes with simple operations. The second is to learn how to process command-line options. The third is to compare the performance of equivalent operations implemented for these containers. The fourth is to implement operators with sorted ranges, and compare your implementations to generic implementations in STL.

Part 1a: A simple container class based on dynamically allocated array

Write a class that implements a container based on a dynamically allocated array, whose maximum size is known at construction time (no reallocations are allowed, so this array cannot be expandable). The type of stored value should be double. The following interface should be supported
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.

Part 1b: A simple linked list

Write a class that implements a single-link list of doubles and supports the following interface

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.

Part 2: Command-line processing

Go over the tutorial on command-line processing.

Part 3: Empirical measurement of complexity

Write a program that instantiates large objects of both container types and populates them using the function val(k)=k/2.5+13. For the array-based container, assume size = maxSize for this experiment. Measure and plot the memory used by each container, as a function of size. For large values of size, estimate how many bytes of memory is used per one value stored in the container.

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,)

Part 4: Operations with Sorted Ranges

Go over the tutorial on merge operations.

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 -g, (2) compile using command-line option -O3. -O3 tells g++ to optimize code for speed. The changes should be done in Makefile, and once you find the lines with -g and -O3, the rest should be straightforward. You can submit runtimes for both experiments, or only one --- in either case, make it very clear which options you used.

Turn-in check-list

Your name must be mentioned at the beginning of every document that you turn in (each program listing, each plot, etc). All sheets must be stapled.
  1. Complete source code printouts (.h and .cxx files) for your two container classes
  2. Gnuplot printouts with measurement results and big-Thetas for Part 3 (estimated bytes-per-value can be written on the memory plots)
  3. Source code printouts for Part 4.
  4. Gnuplot printouts with measurement results and big-Thetas for Part 4