Hide menu

TDDD95 Algorithmic Problem Solving

Lab 3


Lab Assignment 3

The recommended deadline for lab 3 is 2025-04-28 kl 13:00

Read the general instructions before you start.

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

Note: It is possible to get accepted in Kattis with an optimized quadratic algorithm. To receive points for this task, you must implement one of the known linear algorithms, e.g. Knuth-Morris-Pratt.

Task 3.2: 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!).

Note: It is possible to get accepted by Kattis using an optimized O(s2 log s) solution. However, to receive lab points your implementation must be sub-quadratic.

Task 3.3: Longest Common Prefix (1p)

Kattis problem: Dvaput (a stright-forward longest repeated substring problem)

The Longest Common Prefix array is a very useful extension to any Suffix Array implementation. Index i in the LCP array contains the length of the longest common prefix of suffix i and i-1, in sorted suffix order. The LCP array can be used to solve many common string processing problems, including string matching, finding the longest repeated substring, and finding the longest common substring between two or more string.

To complete the task, you are only required to use your LCP array to find a longest repeated substring. However, we encourage that you also learn how to use the LCP array to solve other kinds of problems, and such problems may be included in the weekly exercises and/or problem solving sessions.

Recommended time complecity: O(n) (after having constructed the Suffix Array in O(nlogn)).

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.
  • The six comparison operators <, >, <=, >=, ==, and !=. You must use operator overloading if your language supports it.
  • Input and output by overloading the corresponding operators. If your language does not support this, it is sufficient to provide a sensible constructor and a toString method or similar.

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/reduced form, i.e. such that the numerator and denominator don't share any factors. Beware of over-/underflow during any intermediary calculations.

Advice: Kattis does not check your comparison operators. A simple way to check these yourself is to sort an array of rational numbers using your operators, convert them to doubles and verifying that the order is correct.

Task 3.5: Modular Arithmetic (1p)

Kattis problem: modulararithmetic

Implement modular arithmetic, i.e. addition, subtraction, multiplication and division (modular inverse) modulo n. It is not allowed to use existing packages, such as 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.

Hint: You might run into overflow issues on this problem even if you've solved modular arithmetic. This is because in this problem, you will multiply numbers on the order of O(NM), and the result will not fit in a 64-bit integer. One way to handle this is to use that a * b = a * (2k + d) = 2 * (a * k) + a * d where k is an integer and d is 0 or 1. By multiplying the terms separately, it is possible to perform multiplication modulo m where all intermediary values are in O(2m).

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: 2025-01-28