# TDDD95 Algorithmic Problem Solving

### Lab 3

# Lab Assignment 3

**The recommended deadline for lab 3 is 2017-04-24 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.

# Strings and String Matching

## Task 3.1: String matching (1p)

Kattis problem: stringmatching

Implement a function that given a string and a pattern finds all matches of the pattern in the string.

A good test case is text = aaa...a (200000 characters), pattern = aaaa...a (100000 characters). Every index between 0 and 100000 is a matching position. Also try to double the size of the problem instance (both the text and the pattern). Your solution should solve this in about twice the time.

Suggested API:

position[] find(string pattern, string text)

Recommended time complexity:

## Task 3.2: String multi matching (1p)

Kattis problem: stringmultimatching

Implement a function that given a string and a set of patterns finds all matches in the string for each of the patterns. This is a generalization of Task 1.6, which means that if you solve this problem you have also solved the previous problem.

Suggested API:

position[][] find(string pattern[], string text)

Recommended time complexity:

## Task 3.3: Suffix sort (2p)

Kattis problem: suffixsorting

Implement a data structure that sorts the suffixes of a string in lexicographical order, with the following operations:

- constructor(string s) - create a suffix object from a string.
- position getSuffix(i) - return the i:th smallest suffix.

A good test case is s = <W><W>, where <W> is a 50000 character long string with random characters.

Recommended time complexity:

# Number Theory

## Task 3.4: 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.5: 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.6: 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.7: 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.8: 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.

Page responsible: Fredrik Heintz

Last updated: 2017-03-20