Up Next
Go up to Project
Go forward to Important dates

Project requirements

  • 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:
    1. Developing new components, with functionality distinct from any components already in STL or BGL.
    2. 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).
    3. 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.


 

Up Next