Hide menu

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: O(text + pattern).

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: O(text + patterns + k), where k is the total number of matches of all patterns.

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.
The suffix can be represented by an index indicating the start of the suffix. If we sort the suffixes of the string "popup" we get: "opup", "p", "popup", "pup", "up". If we construct a suffix object from "popup" we will get: getSuffix(0) = 1, getSuffix(1) = 4, getSuffix(2) = 0, getSuffix(3) = 2, getSuffix(4) = 3.

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

Recommended time complexity: O(s log s) for the constructor and O(1) for getSuffix (note: it takes time to compare strings!).

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