# 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.

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, A*x* = 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, A*x* = 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:

x_{1} |
-2·x_{2} |
= | 3 | |

2·x_{1} |
-4·x_{2} |
= | 6 | |

x1 |
-2·x_{2} | +x_{3} |
= | 4 |

we can solve *x*_{3} = 1,
while *x*_{1} and *x*_{2} 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