Avalg project 2, fall 2009
This project is due 25/11 at 10.15. It can be delivered to Stefan personally at his office or put in his mail slot at the department. Do not use the department mail box. It can also be given to Stefan in connection with one of the lectures. Solutions handed in late are not accepted and will not be graded.
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 report and for each problem it should be clearly marked which of the members have contributed. The report should be printed, not handwritten.
There will be a list outside of Stefan's office where you can book a time to pick up and discuss your project. All members of the group must be present during this oral exam. Credit may be given for partially solved problems.
2. Factoring (100p)
Your task is to implement an algorithm for factoring large integers. The implementation should be in Java or C/C++. You may use the java.util.Math or the GMP library. Both of these libraries implement basic arithmetic for large integer numbers. In particular, you may use the built-in algorithms for primality testing. However, you must implement the actual factoring algorithm(s) yourself.
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.
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.
The report (including the oral exam) will be awarded up to 50p.