9th Homework
This homework has to be prepared in teams. Find your partners on
http://moodle.unigraz.at/.
Download hw_9.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.
All of the tasks below need to
 run with the provided input data without crashing
 produce correct results
 have a comprehensive amount of unit tests
 have proper docstrings
 be implemented without using nonEnglish function and variable names,
docstrings etc.
in order to receive (full) points.
You'll have to start by implementing a decent testsuite for each of the
tasks. Only when you're done with your tests, implement the task itself. The
grader will mainly use your own tests to determine your score. If the
testsuite is comprehensive, the grader's score will be awarded fully.
Otherwise, reasonable deductions will be made.
In this homework, it is up to you to pick one of the tasks below and solve it.

Data Structure (9 points)
Imagine that you decide to code your homework
for another course in Python. Also imagine that the other class'
teacher doesn't allow you to fully use the Python standard library or any third party libraries...
Pick a data structure like matrix, linked list, doubly linked
list or graph. Implement this data structure as Python class with a set of
useful methods and useful behavior.
E.g. a matrix should be constructed with a
given number of rows and columns initialized to a value of choice. It
should have methods/ properties returning the number of rows and columns.
Also, it should be possible to iterate over its rows/ the row elements.
You may also add methods/ operations to add one matrix to another, multiply
it with a scalar or return the sum of all elements in the matrix. Go wild!
:) (Note: if you pick another data structure, the example
methods for matrices won't make sense... e.g. linked lists rather need
methods like insert(.)
and remove(.)
etc.)
Properly test your data structure and all the operations it supports.
Name the test module: test_data_structure.py
Test class: TestDataStructure
Name the module: data_structure.py

Knapsack Problem (9 points)
Implement a simple solver for 01 knapsack problems. The solver needs to
return the set of items to be selected in order to maximize the total
profit.
Name the test module: test_knapsack.py
Test class: TestKnapsack
Name the module: knapsack.py

Simulation (9 points)
Solve all of the following problems.

The Drunkard's Walk
Read up on random walks and simulate a 2 dimensional walk ("Drunkard's Walk") over 100 intersections.

The Monty Hall problem
Read up on the Monty Hall problem and simulate it. Run 10000 loops to get a confident result.
Name the test module: test_simulation.py
Test class: TestSimulation
Name the module: simulation.py