TDDD95 Algorithmic Problem Solving

Lab 1

Lab Assignment 1

The recommended deadline for lab 1 is 2024-02-15 kl 13:00

Read the general instructions before you start.

The suggested API below is pseudo code, you have to translate it to your favorite language in an appropriate way.

The "recommended time complexity" is what is required to pass the time requirements in Kattis.

Greedy/Dynamic Algorithms

Task 1.1: Interval coverage (1p)

Kattis problem: intervalcover

Implement a function that given a set of intervals and a target interval returns the smallest number of intervals required to cover the target interval. An interval is a pair of real numbers.

For example, assume the target interval is [-0.5, 1] and the given intervals are {[-0.9, -0.1], [-0.2, 2], [-0.7, 1]}. In this case, it would be possible to use the first two intervals to cover the target interval. However, a better (in this case optimal) solution would be to use only the last interval.

Be aware of corner cases.

Suggested API:
int[] cover(interval, interval[])
The returned vector contains the indices of the chosen intervals.

Recommended time complexity: O(n log n), where n is the number of intervals.

Note: It is possible to get accepted by Kattis with an optimized algorithm with worst-case quadratic time complexity. However, to receive lab points you must make sure that your algorithm is in O(n log n) even in the worst case. In particular, make sure that you don't process the same interval multiple times except when sorting.

Task 1.2: Knapsack (1p)

Kattis problem: knapsack

Implement a function that computes what to pack in a capacity limited knapsack to maximize the total value of all the items packed. Each item has an integer value and an integer weight. The total weight of all items packed must be less than or equal to the capacity (which is a real number).

Suggested API:
int[] knapsack(capacity, value/weight[])
The returned vector contains the indices of the chosen items.

Recommended time complexity: O(n·capacity).

Task 1.3: Longest increasing subsequences (1p)

Kattis problem: longincsubseq

Implement a function that computes the longest increasing subsequence in a given sequence.

Suggested API:
int[] lis(object[])
The returned vector contains the indices of of a longest increasing subsequences.

Recommended time complexity: O(n log n), where n is the number of objects in the sequence.

Note: It is possible to get accepted by Kattis using an optimized O(n²) solution. However, to receive lab points your implementation must be in O(n log n)

Data structures

Task 1.4: Disjoint sets / equivalence relations (1p)

Kattis problem: unionfind

Implement a data structure to handle disjunct sets. When the data structure is created, all elements are in their own sets. Your implementation should at least support the following operations:

union(int a, int b) - merge the sets containing the elements a and b
boolean same(int a, int b) - test whether a and b are in the same set

Recommended time complexity: amortized O(log n) for both operations, where n is the total number of elements.

Warning: You are expected to produce a lot of output data for this problem. Make sure that you don't flush the output buffer after each line, since this might make your otherwise correct solution too slow.

Task 1.5: Prefix sums (1p)

Kattis problem: fenwick

Implement a data structure to handle prefix sums of an array a[0], a[1], ..., a[N-1], with the following operations:

add(index i, number delta) - increase a[i] with delta
number sum(index end) - compute the sum of the first numbers up to, but not including, a[end]

Recommended time complexity: O(log n) for both operations, where n is the number of elements in the array.

Warning: Even with a correct imlementation, Python is probably too slow to solve this assignment.

Arithmetic

The solutions in this part are more useful if the types for coefficients can be determined using templates/generics, but it is not a requirement.

Task 1.6 Polynomial Multiplication (1p)

Kattis problem: polymul2.

Implement multiplication of two polynomials using the Fast Fourier Transform.

Recommended time complexity: O(n log n), where n is the order of the resulting polynomial.

Note: There is also a simpler problem polymul1 where a quadratic algorithm is sufficient. While you are free to use this problem for testing etc., you will not receive any points for solving this simpler problem.

Task 1.7: Linear Equation Systems with a Unique Solution (1p)

Kattis problem: equationsolver

Implement a function solving linear equation systems, Ax = b, where A is a n×n matrix and b is a n×1 vector.

If the system does not have a unique solution, i.e. the matrix A is singular, this should be detected. There are two cases to separate: systems with more than one solution and systems without a solution. Be aware of corner cases and numerical stability.

The function will be more useful if it is posible to choose the coefficient type using templates/generics, for example rationals, floats or integers modulo p, but it is not required.

Recommended time complexity: O(n³).

Task 1.8: Linear Equation Systems without a Unique Solution (1p)

Kattis problem: equationsolverplus

Implement a function solving as many variables as possible from a linear equation system, Ax = b, where A is a n×n matrix and b is a n×1 vector, even if the system is under determined. For example, given the system:

x₁	-2·x₂		=	3
2·x₁	-4·x₂		=	6
x1	-2·x₂	+x₃	=	4

we can solve x₃ = 1, while x₁ and x₂ cannot be determined. If the system does not have a solution this should be detected.