Avalg project 2 fall 2006

This project is due 8/12 at 17.00 (NEW DEADLINE). 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 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. Polynomial multiplication (100p)
Your task is to implement three algorithms for multiplying polynomials:

  1. the naive algorithm,
  2. Karatsuba's algorithm,
  3. the fast Fourier transform (FFT).
The implementation should be in Java or C/C++.

You should submit your code to Kattis (polymul1, polymul2, polymul3) for automatic grading and evaluation. Depending on the performance of your algorithm you will be awarded up to 50p from Kattis - 10p for the naive algorithm, 15p for Karatsuba, and 25p for FFT. 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 the 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.

Measure and compare the performance of the different algorithms. Try to explain the behavior and present your results graphically. You will probably find that no single algorithm is consistently faster than the others.

It might be possible to achieve even better running times by combining several of these algorithms. Discuss how this could be done and implement such an algorithm. Compare the performance of this combo algorithm with the ones above. Again, discuss the results and present your measurements graphically.

The report (including the oral exam) will be awarded up to 50p.

Stefan Nilsson