# Lab Assignment 1

The recommended deadline for lab 1 is 2017-02-09 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. An example is the longest increasing subsequence (task 1.3 below). A big advantage is that the content of the collection does not have to be stored in a particular data structure, you can use an array, a vector, a list or any other container that have the required operations.

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 indexes of the chosen intervals)

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

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 interger 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 indexes of the chosen things)

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 indexes of longest increasing subsequences)

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

# Data structures

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

Kattis problem: unionfind

Implement a data structure to handle disjunct sets, with 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
When the data structure is created, all the elements are in their own sets.

## 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]

# Arithmetic

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

## Task 1.6 Polynomial Multiplication (1p)

Kattis problem: polymul2. (There is also a simpler problem polymul1 where a quadratic algorithm will be sufficient.)

Implement multiplication of two polynomials using e.g. Karatsubas algorithm or FFT.

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

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.

## 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:

 x1 -2·x2 = 3 2·x1 -4·x2 = 6 x1 -2·x2 +x3 = 4

we can solve x3 = 1, while x1 and x2 cannot be determined. If the system does not have a solution this should be detected.

Page responsible: Fredrik Heintz
Last updated: 2017-01-14