Lab 3

Due Nov 17, 2020 by 10am
Points 9
Submitting a text entry box
Available after Oct 13, 2020 at 12am

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.

Required time complexity means that your algorithm should have this time complexity. In some cases it might be possible to pass the Kattis tests with a slower algorithm, but if you do so, 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 ID on Kattis Links to an external site.: stringmatching Links to an external site..

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 ID on Kattis Links to an external site.: stringmultimatching Links to an external site..

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!),

Problem ID on Kattis Links to an external site.: suffixsorting Links to an external site..

A good test case to think about if your code is too slow is s = <W><W>, where W is a 50000 character 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 packages or classes, 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.

Problem ID on Kattis Links to an external site.: modulararithmetic Links to an external site..

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 ID on Kattis Links to an external site.: chineseremainder Links to an external site..

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 ID on Kattis Links to an external site.: generalchineseremainder Links to an external site..

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.

Problem ID on Kattis Links to an external site.: primesieve Links to an external site..