Some forms of collaboration are allowed and required. The size of a group of collaboration should be two people. The group should hand in only one written report and for each problem it should be clearly marked which of the members have contributed.

There will be a list outside of Stefan's office where you can book a time. All members of the group must be present when the homework is returned. Credit may be given for partially solved problems.

1. Euclidean TSP (100p)
Your task is to implement an algorithm for computing short TSP tours in the plane. The implementation should be in Java or C/C++. You should implement the algorithm(s) from scratch.

You should submit your code to Kattis for automatic grading and evaluation. Depending on the performance of your algorithm you will be awarded up to 50p from Kattis. All group members who want to get points from Kattis need to make a separate submission.

You should also hand in a written report where you describe the algorithms and strategies you have used in your program. The description should be detailed and easy to follow. You may want to describe your algorithms in pseudo code.