Homework A

This homework is due 2011-10-11. It should be done individually and handed in no later than 15.15 October 14. Drop it off in Mikael Goldmann's mailbox at Lindstedtsvägen 3. The solutions must be printed, not handwritten. Solutions handed in late are not accepted and will not be graded.

Please remember that solutions need to be in English.

Each problem is worth 5 points.

Problem 1

Show that the following algorithm will compute the GCD of two non-negative integers a and b where one of them is at least 1.

gcd(a,b):
  if b > a
    return gcd(b, a)
  else if b == 0
    return a
  else if a and b are even
    return 2*gcd(a/2, b/2)
  else if a is even
    return gcd(a/2, b)
  else if b is even
    return gcd(a, b/2)
  else
    return gcd(b, a-b)

Analyze the number of recursive calls and the bit complexity of the algorithm.

Problem 2

Let N be your ten-digit personal number. Find an integer 0 ≤ X < N(N+1) so that

X ≡ 123456789 (mod N)
X ≡ 987654321 (mod N+1)

Explain how the result was reached, don't just answer with a number.

You can use big integer support for additon, subtraction, multiplication and divistion available in e.g., Python or Java.

Problem 3

Design an algorithm that sorts n non-negative integers in linear time on a unit cost RAM if all elements are of magnintude at most n¹⁰.

Explain why it works and analyze it to show that it does have the desired complexity.

Problem 4

Design an algorithm that sorts n comparable elements in time O(n log m ) provided we know that there are only m distinct values.

Explain why it works and analyze it to show that it does have the desired complexity.

Problem 5

Show that resolution yields a polynomial time algorithm that determines the (un)satisfiability of 2-CNF formulas by deriving new clauses until either an empty clause is obtained or no more clauses can be derived.

(It is actually possible to determine satisfiability of a 2-CNF formula with n variables and m clauses in time O(n+m) but that is not required for this exercise.)