Hide menu

AAPS Advanced Algorithmic Problem Solving

Lab 3


Lab Assignment 3

The recommended deadline for lab 3 is 2014-04-14 kl 12:00

Read the general instructions before you start.

Advice: In both C++ and Java it is practical to use iterators to represent vectors, sets etc.

Task 3.1: Rational Numbers (1p)

Kattis problem: rationalarithmetic

Implement a class for rational numbers. The class should at least support:

  • Common arithmetic operations: addition, subtraction, multiplication, and division.
  • Comparison.
  • Input and output operators.
The class will be more useful if it is possible to choose the numerator and denominator types using templates/generics, but it is not required.

It is not allowed to use existing packages, such as java.math.BigInteger, that already provide the functionality.

Advice: Store the rational numbers in a normalized form.

Task 3.2: Modular Arithmetic (1p)

Kattis problem: modulararithmetic

Implement modular arithemtic, i.e. addition, subtraction, multiplication and division modulo n. It is not allowed to use existing packages, such 1as java.math.BigInteger, that already provide the functionality.

Remember that the %-operator does not behave as expected for negative numbers.

Task 3.3: Linear Equation Systems with a Unique Solution (1p)

Kattis problem: equationsolver

Implement a function solving linear equation systems, Ax = b, where A is a n×n matrix and b is a n×1 vector.

If the system does not have a unique solution, i.e. the matrix A is singular, this should be detected. There are two cases to separate: systems with more than one solution and systems without a solution.

The function will be more useful if it is posible to choose the coefficient type using templates/generics, for example rationals, floats or integers modulo p, but it is not required.

Task 3.4: Linear Equation Systems without a Unique Solution (1p)

Kattis problem: equationsolverplus

Implement a function solving as many variables as possible from a linear equation system, Ax = b, where A is a n×n matrix and b is a n×1 vector, even if the system is under determined. For example, given the system:

x1 -2·x2 = 3
x1 -4·x2 = 6
x1 -2·x2 +x3 = 4

we can solve x3 = 1, while x1 and x2 cannot be determined. If the system does not have a solution this should be detected.

Task 3.5: Chinese Reminder Theorem - Relative Prime (1p)

Kattis problem: chineseremainder

Implement a function solving
x = a (mod n)
x = b (mod m)
where n and m are relative prime. The solver should return the unique solution x such that 0 ≤ x < n · m.

Task 3.6: General Chinese Reminder Theorem (1p)

Kattis problem: generalchineseremainder

Implement a function solving
x = a (mod n)
x = b (mod m)
where n and m does not have to be relative prime. The solver should return a solution x such that 0 ≤ x < n · m / gcd(m, n). The function should handle the case when there is no solution.

Task 3.7: Prime Sieve (1p)

Kattis problem: primesieve

Implement Erathostenes sieve to find all primes upp to a limit n. The sieve could for example be implemented as a class where the constructor takes n as an argument and allows constant time queries to it whether a particular number between 0 and n is a prime or not.

The implementation should be both memory and time efficient.

Task 3.8: Integer Factorization (1p)

Kattis problem: oldkattis:factoring

Implement a function that computes the correct factorization of an integer with up to 100 bits.


Page responsible: Fredrik Heintz
Last updated: 2014-03-24