This homework is due November 21 at 15.15. It can be
delivered to Stefan or Jonas personally at their offices or put in
their mail slot at the department. 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 solution and for each problem it should be clearly
marked which of the members have contributed.
The homework will be returned on Monday and Tuesday November 2627.
Please book a time by writing your names on the list
outside of Stefan's office.
All members of the group must be present when the homework is returned.
I do not consider the set of problems below easy. Thus a
performance of getting half the total score on this set
is at least equivalent to the grade 4 on this subset of
the course. Credit may be given for partially solved
problems.
1. Multiplication (60p)
Your task is to implement multiplication algorithms for
large numbers. You should implement both the schoolbook
algorithm and Karatsuba's algorithm.
(Optionally, you may also want to implement an algorithm
based on the fast Fourier transform.)
You should implement the algorithms from scratch using either C or Java.
Compare the running times of the algorithms experimentally.

The code should follow
Java Code Conventions
(or similar C conventions).
IndexTreeList.java
is intended to be a good
example.

Your code should be well documented and easy to use.
The documentation could be generated using
javadoc.

The API should be easy to understand and use. Only include necessary
methods and carefully design your data types.

The code should be robust. Erroneous parameters and function
calls should be handled gracefully.

The code should be efficient.

The code must, of course, be correct. Include code for
testing
all functions.
2. Fermat's little theorem (20p)
Give an elementary proof of Fermat's little theorem,
i.e. you may not use any group theoretic arguments.
3. Prime numbers (20p)
Let p be a prime such that p = 1 mod 8.
Find, and prove, a formula for the number of solutions to
x^{d} = ±1 mod p where
d = (p  1)/8, (p  1)/4, and (p  1)/2.
4. Detect a cycle in a linked list (20p)
How can you detect a cycle in a linked list? The list
is in readonly memory, and you cannot mark elements.
Also, you may only use a constant amount of extra memory.
5.Lemma 4.2 (20p)
Prove Lemma 4.2.