For the given problem (a problem from the set specified by the lecturer, with a number corresponding to the student’s number on the student list), the student must:

1. Prepare a theoretical description of the problem (in written form). (2 pts)

2. Prepare a description of an exact algorithm for solving the given problem (in written form). (2 pts)

3. Prepare a description of a specified or self-proposed approximation/heuristic algorithm for solving the given problem (in written form). (2 pts)

4. Implement in a chosen environment:

   a. An exact algorithm solving the problem. (6 pts)

   b. A specified or self-proposed approximation/heuristic algorithm solving the problem. (6 pts)

   The format of data input and output is arbitrary. One option is to use a text interface or text files.

5. The implementation should include:

   a. A data instance generator for the problem with a given size. (2 × 1 pt)

   b. Measured time complexity of both algorithms. (2 × 1 pt)

   c. Measured memory usage of both algorithms. (2 × 1 pt)

   d. Data allowing the evaluation of the quality (accuracy) of the solution. (2 × 1 pt)

6. Estimate (for each of the two algorithms):

   a. Theoretical pessimistic memory and computational complexity as a function of problem size (as defined for the given problem). (2 pts)

   b. Theoretical expected memory and computational complexity as a function of problem size (as defined for the given problem). (2 pts)

   c. Theoretical pessimistic sensitivity as a function of problem size (as defined for the given problem). (2 pts)

   d. Theoretical expected sensitivity as a function of problem size (as defined for the given problem). (2 pts)

   e. Theoretical accuracy as a function of problem size (as defined for the given problem). (2 pts)

7. Prepare a presentation containing information from points 1, 2, 3, 5 (optionally also from point 4). Present it during the specified laboratory class (presentation time – max 10 minutes). (4 pts)

8. Conduct a series of experiments (5 pts) and analyze their results along with conclusions (5 pts). The experiments should allow for comparing the estimated parameters from point 5 with the actual values obtained during the experiments.

9. Prepare a report. The report should contain information gathered in points 1, 2, 3, 5, and 7, conclusions, and bibliography. The report, along with the presentation and implementation, should be delivered no later than during the last laboratory class of the semester. Exceptions to this rule – upon agreement with the lecturer.