6th Homework

This homework is to be prepared in teams of two students. Find your partner on http://moodle.uni-graz.at/. Download hw_6.tar.gz and extract it. Then add your homework solutions to the directory. Rename the directory according to the rules in the syllabus before submitting it as compressed archive. Don't forget to add the correct subject to the email when submitting.

Properly document the files you hand in to receive full credit. Each module (file), class and function needs a docstring. The purpose of each function needs to be summarized as a single sentence and then, if required, your intent and the behavior of the function can be described in more detail.

Furthermore - provide doctests for all functions and classes. Each of the modules needs to include a main() function which calls the other functions and prints appropriate output to stdout. main() itself must be called by the ifmain pattern at the end of the file.

TSP (4 points)
Declare an abstract base class Algorithm that defines an API for a travelling salesman problem (TSP) algorithm.
The API should define three properties: time, ov, and solution, where time and ov are floating-point numbers and solution is a list of integers each denoting a vertex.
Furthermore, there should exist a method solve(self, instance). solve(.) must call the method algorithm(self, instance) which is not implemented and measure its execution time. Both methods take the parameter instance which is an object of the class Instance2D in the file instance2D.py. The API should be used in the following way:
```
from instance2D import Instance2D
instance = Instance2D("filename.tsp")
algorithm = Algorithm()
algorithm.solve(instance)
print(algorithm.time)
print(algorithm.ov)
print(algorithm.solution)
    """
    
```
Based on the class Algorithm, derive two classes, T and NN, which implement the method algorithm(self, instance) and solve the TSP by two different algorithms:
- The class T just orders the vertices one after another, i.e. if the test instance has 5 vertices, the solution will be [0, 1, 2, 3, 4, 0].
- The class NN implements the nearest neighbour heuristic startetd from the vertex 0.
Name the module: t_s_p.py

Moore's Algorithm (5 points)
Implement Moore's algorithm ("An n Job, one Machine Sequencing Algorithm for Minimizing the Number of Late Jobs", J. Michael Moore, Management Science, Vol. 15, No. 1, Sept. 1968). You do not need to consider deferral costs - just minimize the number of late jobs. The return value of the function implementing Moore's algorithm (solve_moore(filename)) has to be a Python list containing project ids (the sequence in which the projects should be processed). Only the projects that can be completed in time should be part of that list. The remaining jobs should be discarded.
First, consider which Python data structure is suitable to store data used by the algorithm. It is essential that your selected data structure allows to be sorted by the values of a given row. It might also be helpful if it would be possible to add an additional row that contains the cumulative sum of any of the rows above.
An example for the required data is laid out in the table below:

project	1	2	3	4	5	6	7
duration	5	3	7	2	9	6	5
due time	6	16	27	19	14	17	21

Implement a function or method that takes the name of a file and populates the data structure with the data of the file. The data in the input files is transposed, so for the example above it looks like

project	duration	due time
1	5	6
2	3	16
3	7	27
...

The number of rows in the input file is not given and needs to be determined at runtime. Be careful, some of the input files might not have a header while others do.
It is certainly helpful to implement a function or method that takes a reference to a row and sorts the columns of your data structure by the values in the given row. Also, implementing a function or method that takes a reference to a row and adds an additional row that contains the cumulative sum of the values of the given row might be useful.
Note that the grader does not consider how you implement the solution to this problem. It is entirely up to you to choose an appropriate data structure and divide your code into multiple units of code that work together. The grader only looks at solve_moore(filename) and checks if the results are correct.
Name the module: moore.py