- Develop one or more generic software components, designing them
to fit into the STL or BGL framework of containers, generic
algorithms, iterators, function objects, adaptors, allocators, and
visitors. "Develop" includes doing concept
development,1 design,
implementation, experimentation, testing, and documentation.
- The emphasis of your project may be in any one of the following
three areas:
- Developing new components, with functionality distinct from
any components already in STL or BGL.
- Developing alternative implementations for existing STL or BGL
components, based on different algorithms or data structures with
different performance profiles (improving on existing implementations
for a definable, nontrivial class of inputs).
- Developing software tools that support generic programming
activities such as compiling (e.g., help with error messages), debugging
(e.g., help with interpreting run-time execution states), or
general understanding of generic algorithms and data structures
(e.g., documentation aids, algorithm animations, etc).
- Observe the documentation requirements and guidelines given in
a later section.
- For a generic algorithm, be sure you are starting with an
efficient concrete algorithm; there is no point in making a generic
bubble sort. The same is true for other kinds of components.
- Testing should be extensive, including checking
correctness of small cases, including boundary cases such as empty
sequences, and measuring performance of large randomly generated
inputs of a variety of sizes (possibly up to 100,000 or
a million elements, depending on the algorithm).
- Correctness for large inputs should
also be checked, using an acceptance routine (e.g., to check a sort
routine, use an acceptance routine that checks to see if the result is
in order, or better, checks to see if it is exactly the same output as
that from another sort routine known to be correct).
- Timings of fast algorithms on moderate size inputs (a few
thousand elements) may need to be repeated for some number of trials
and averaged, for accuracy.
- D. R. Musser, Measuring Computing Times of Generic
Algorithms. contains
advice and software tools for accurate performance measurement of
generic algorithms. Alternative (and generally better) methods
will be a topic of discussing in an upcoming lecture.
- For further ideas and discussion, see the test plan and
results subsection of the Documentation Requirements and
Guidelines section.
- Experiment with different potential optimizations of your
generic component(s). For each component, attempt to find, based on
performance measurements, the best version, under the constraint that
it should be generic. Include in the Design section of your
documentation discussion of why the selected and documented version is
better than alternatives. For algorithms, also compare performance
with other algorithms; if your algorithm isn't the best for all kinds
of inputs, try to describe the class of inputs for which it is best,
in the Complexity section.
- You must form teams of three, four, or five people and
submit one implementation and report for the team. You may divide up
responsibilities for the project as you wish, but each member of the
team should keep fully informed about the design decisions,
experimental results, testing results, and documentation.
|