# 9th Homework

This homework has to be prepared in teams. Find your partners on http://moodle.uni-graz.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 non-English function and variable names, docstrings etc.

in order to receive (full) points.

You'll have to start by implementing a decent test-suite 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 test-suite 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 0-1 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.
1. The Drunkard's Walk
Read up on random walks and simulate a 2 dimensional walk ("Drunkard's Walk") over 100 intersections.
2. 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