Avalg homework 1 fall 2004

This homework is due November 19 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 solution and for each problem it should be clearly marked which of the members have contributed.

There will be a list (from November 8th) outside of Stefan's office where you can book a time. 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 (40p)
Your task is to implement multiplication algorithms for large integers. You should implement both the schoolbook algorithm and Karatsuba's algorithm. The multiplication algorithms should be implemented from scratch using either C or Java. However, you may use standard libraries, such as Java's BigInteger, for reading and converting numbers from and to decimal form. Compare the running times of the algorithms experimentally. (Optionally, compare the running time of your algorithms with the algorithm based on FFT in the textbook by Goodrich and Tamassia.)

  • 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. I highly recommend the following article. You don't have to use the software tool described in the article but the ideas are still very useful.

2. Fill in the gaps (5p+5p+5p+5p)
Give detailed proofs of the following statements.

page 14: If this condition is true for all a between 1 and p-1 then N must be prime since gcd(a, N) = 1 for 1 <= a <= N-1 which clearly implies that N is prime.

page 15: It is not hard to see that

              x = a1U1 + a2U2 mod p1p2

fulfills the first set of equations ...

page 15: It is not difficult to extend this to larger r (we leave the details as an exercise) and ...

page 16: But if N is prime, then the equation x2 = 1 mod N has only the solutions x = ±1 and ...

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 xd = ±1 mod p where d = (p - 1)/8, (p - 1)/4, and (p - 1)/2.

4.Lemma 4.2 (20p)
Prove Lemma 4.2 in the lecture notes.

5. TSP (40p+40p+20p)

a) Implement Christophides's algorithm from scratch (i.e. you may only use the standard C or Java libraries) and run the algorithm on the instances eil51, eil76, and eil101 in TSPLIB What is the running time and how good are the approximations?

b) Implement your own approximative algorithm for TSP with Eucliden distance. Try the algorithm on the d198, d493, d657, ... instances in TSPLIB. What is the largest instance you can solve within 10% of optimum within 20 minutes user time on a Nada work station?

c) Theorem 16.2 (Arora) gives a theoretical result on approximating Euclidean 2-dimensional TSP. What else can be said about TSP with Euclidean distance? What about higher dimensions? You may go about this problem in different ways. You will be rewarded for presenting published results (don't forget do give proper references) and creative thinking of your own is also very much appreciated.

Stefan Nilsson