Lab 3

Submit the following, as a group (it is sufficient that only one of you make the submission):

• A list of which problems you have solved, with links to the corresponding Kattis submissions.
• A short statement of who did what.

(Getting Accepted on Kattis is a necessary but not sufficient condition for passing a lab task. Before starting, read the General Lab Instructions for more details)

Hint: in C++ in particular but also Java it is useful to use iterators to represent vectors/sets/etc.  For an example of this for the longest increasing subsequence task below, see here. An advantage of this approach is that the function does not require the input to be stored in some specific container type, you can use arrays, vector, list, or whatever other container type has the operations needed in the function.

Note that the API suggestions below are to be interpreted as pseudo code, you should translate them to your favorite language as you see fit.

Problems on Kattis: https://kth.kattis.com/courses/DD2458/popup25/assignments/mxt25b/problems Links to an external site.

Note! The lab description below might have additional requirements that need to be fulfilled.  In some cases it might be possible to pass the Kattis tests with a slower algorithm, or Kattis might not test all required functionality.  If you do not fulfill the requirements given below you might still get points deducted when presenting your labs.

Strings and String matching

Task 3.1: Substring search (1p)

Implement a function to find all occurrences of a string pattern in another string text.

API suggestion:
position[] find(string pattern, string text)

Required time complexity: O(|text| + |pattern|) worst case.

Problem on Kattis: String Matching

A good test case to think of if your code is too slow is text = aaa...a (200000 characters) and pattern = aaaa...a (100000 characters). All indices from 0 to 100000 are matching positions. Also try to make this test case twice as large (i.e., double the size of text and pattern). Your solution should then only take approximately twice as much time (whereas a quadratic solution would take four times as much time).

Task 3.2: Multiple substring search (1p)

Implement a function which finds all occurrences of a set of strings pattern[] in another string text.

API suggestion:
position[][] find(string pattern[], string text)

Required time complexity: O(|text| + |pattern[]| + k), where k is the total number of matches of all patterns.

Problem on Kattis: String Multimatching

Note: A solution to this problem is also a solution for Task 3.1 (since the parameter k is at most the length of the text if there is only one pattern).  However the converse does not hold, this problem requires more work than simply taking a solution for 3.1 and running it once per pattern..

Task 3.3: Suffix Sorting (2p)

Implement a data structure to sort the suffixes of a string in lexicographic order. The data structure should have the following operations:

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

For instance, the string "popup" has 5 suffixes: "p", "up", "pup", "opup", and "popup".  If we sort these we get: "opup", "p", "popup", "pup", "up".  However in general writing down all the suffixes of a string takes quadratic time and space, so we represent each suffix by the position in the string at which the suffix starts.  Thus if we create a suffix object from the string "popup", we should have: getSuffix(0) = 1, getSuffix(1) = 4, getSuffix(2) = 0, getSuffix(3) = 2, getSuffix(4) = 3.

Recommended time complexity: O(s log s) for the construction and constant time for getSuffix. Extra log factors in the construction running time are OK if the code passes on Kattis. (Note! remember that string comparisons take time!),

A good test case to think about if your code is too slow is s = <W><W>, where W is a long random string.

Number Theory

Task 3.4: Modular Arithmetic (1p)

Implement modular arithmetic, i.e., addition, subtraction, multiplication, and division modulo n. It is not allowed to use ready-made classes/functions/packages, such as java.math.BigInteger which already provides implementations of this.

Recall that the % operator doesn't behave the way you might want it to for negative numbers in C/C++/Java.

Requirements: all four operations must be computed in O(1) basic arithmetic operations (e.g. add/sub/mul/div on integers), except inverses for which you are also allowed to use the Euclidean algorithm.

Task 3.5: Chinese Remainder Theorem (2p)

Here you can choose between an easier (a) or harder (b) option.  The solutions here are much more useful if they allow for picking a custom integer type using templates/generics, but doing this is not a requirement.

The solution to task 3.4 may be useful in this task.  So if you're planning to both, it is recommendable to do 3.4 first.

Option (a): Relatively prime moduli (1p)

Implement a function solving the equation system

x = a (mod n)
x = b (mod m)

where m and n are relatively prime. The solver should return the unique solution x satisfying 0 ≤ x < n · m.

Problem on Kattis: Chinese Remainder

Option (b): Arbitrary moduli (2p)

Implement a function that solves the equation system above for arbitrary (not necessarily relatively prime) moduli.  Note that in this case the system might not have a solution, this should be detected.

The solution x returned must satisfy 0 ≤ x < n · m / gcd(m,n).

Problem on Kattis: Chinese Remainder (non-relatively prime moduli)

Task 3.6: Prime sieve (1p)

Implement Erathostenes' sieve for finding all prime numbers up to a limit  n. The sieve can for instance be implemented as a class where the constructor takes  n as a parameter and which then in constant time can answer queries about whether a given number between 0 and n is prime or not.

Note that your implementation must be both memory- and time efficient.

Linear recurrences

Task 3.7: Fast computation of small recurrences (1p)

Implement an algorithm to find the n'th number in a linear recurrence.

Required time complexity: O(k³ · log(n)) for the n'th term in a linear recurrence of degree k.

The solution to task 3.4 may be useful in this task.  So if you're planning to both, it is recommendable to do 3.4 first.