Lab 1

Due Sep 22, 2020 by 10am
Points 9
Submitting a text entry box

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.

Greedy/Dynamic Algorithms

Task 1.1: Interval Cover (1p)

In the interval cover problem we are given a target interval I and a set of intervals S, and we wish to cover I using as few intervals from S as possible, i.e., find a minimum size subset S' of S such that I is contained in the union of S'.

API suggestion:

int[] cover(interval, interval[])
(where the returned int-array give the indices of the chosen intervals)

Required time complexity: O(n log n), where n is the size of S.

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

Task 1.2: Knapsack (1p)

In the knapsack problem we have n items (e.g. jewels). Each items has a value and a weight. We have a knapsack in which we can pack items, but the total weight of packed items can not exced some given capacity. We want to pack items such that the total value of packed items is maximum.

Implement an algorithm to solve the knapsack problem when the weights are integers. The algorithm should also construct an optimal packing.

API suggestion
int[] knapsack(capacity, value/weight[])
(where the returned int-array has the indices for the chosen items)

Required time complexity: O(n·capacity).

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

Task 1.3: Longest Increasing Subsequence (1p)

Implement an algorithm to find a longest increasing sequence of a given sequence.

API suggestion:
int[] lis(object[])
(where the returned int-array are the indices used in the longest increasing subsequence)

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

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

Data Structures

Task 1.4: Disjoint Sets / Equivalence relations (1p)

Implement a data structure for disjoint sets of integers with the following operations:

union(int a, int b) - indicate that the sets containing a and b are merged.
boolean same(int a, int b) - checks if a and b are in the same set.

Initially all elements are in a set of their own.

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

Task 1.5: Prefix Sums (1p)

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

add(index i, number delta) - add delta to a[i].
number sum(index end) - compute the prefix sum a[0] + ... + a[end-1].

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

Arithmetic

The solutions in this part will become a lot more useful for you if they allow for custom coefficient types (e.g. integers, reals, rationals, etc) using templates/generics, but implementing this is not required.

Task 1.6 Rational Numbers (1p)

Implement a representation of rational numbers. The representation must at least have support for:

Basic arithmetic operations: addition, subtraction, multiplication, division.
Comparisons.
Input and output (output in "lowest terms").

The representation becomes more useful if it allows you to pick the data type for numerator and denominator using templates/generics, but it is not required to implement this.

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

Task 1.7 Polynomial Multiplication (1p)

Implement multiplication of two polynomials using e.g. Karatsuba's algorithm or FFT.

Problem ID on Kattis Links to an external site.: polymul2 Links to an external site.. (There is also a polymul1 Links to an external site. with smaller limits where a quadratic algorithm will pass. You might find this useful for debugging, but solving it is not required.)

Task 1.8: Linear Equations (2p)

Implement an algorithm to solve a linear equation A · x = b, where A is an n×n-matrix and b is an n×1-vector.

You can choose between an easier (a) and harder (b) version of this problem:

Option (a): With a unique solution (1p)

If the system lacks a unique solution (i.e., if A is singular), this should be detected. There are two cases to distinguish: systems with more than one solution, and systems without a solution.

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