Instructions

• The project is done in groups of two or three.
• Choose one of the topics below.
• Implement the code using STL as much as reasonable.
  • Ask instructor/exercise tutor if you want to use non-standard libraries.
• Your own code should also be reasonably STL-like.
  • Use iterators, STL naming conventions, etc.
  • Write generic code (only) when appropriate.
• The instructions for Software Design (C++) End-Term Project apply in relevant parts. In particular:
  • Follow good C++ programming practices. See rules from Software Design (C++) (Note that there are several pages of rules.)
  • Quality of the source code is more important than efficiency.
  • Document things that are not self evident.
  • Use g++.
  • Return as a package (with a README file)

Deadlines

• 31.1. Assignment of topics on the lecture.
• 8.2. Present a plan
  • planned features, modules, etc.
  • who does what in the group
• 24.2. Return final work by email to Jarkko Toivonen.

Grading

• maximum 25 points
• basis for grading
  • proper use of STL components and conventions
  • general quality of code and documentation
  • degree of difficulty

Topics

1. Huffman coding. Implement a file compressor/decompressor based on Huffman coding.
2. Blackjack simulation. Blackjack is a popular game of chance in casinos with consistent winning strategies based on card counting. Implement a simulation that plays a large number of games to find out how much one wins or loses in the long run with or without card counting.

3. Dijkstra's algorithm. Implement Dijkstra's algorithm for computing shortest paths in a graph. Subtasks include:
   • simple graph class based on adjacency lists
   • priority queue that supports decrease_key operation
4. Self-organizing lists. Implement the self-organizing lists described in this article. Test them with word counts as in the article.

5. Statistical analysis. Implement the computation of various simple statistical measures:

   • summary statistic
   • measures of correlation
   • support different scales or levels of measurement

   Implement the computation as algorithms taking data in as an iterator range. Implement also a program that reads data from a file and applies the algorithms.

6. STLize. Rewrite some non-STL code you have written earlier using STL extensively.

7. Own topic.