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.

  1. 3D Shapes (4 points)
    Declare an abstract base class ThreeDimensionalShape that defines a tiny API for 3-dimensional shapes. The API should consider of two methods surface() and volume().
    Implement three classes that each derive from ThreeDimensionalShape: Sphere(radius), Cylinder(radius, height) and Cone(radius, height). Each of these three classes needs to implement the full API defined by ThreeDimensionalShapes.
    Name the module: shape.py
  2. 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