Hide menu

AAPS Advanced Algorithmic Problem Solving

Lab 1


Lab Assignment 1

The recommended deadline for lab 1 is 2014-02-10 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.

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.

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

Task 1.4: Union Find (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]

Task 1.6: String matching (1p)

Kattis problem: stringmatching

Implement a function that given a string and a pattern finds all matches of the pattern in the string.

A good test case is text = aaa...a (200000 characters), pattern = aaaa...a (100000 characters). Every index between 0 and 100000 is a matching position. Also try to double the size of the problem instance (both the text and the pattern). Your solution should solve this in about twice the time.

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

Recommended time complexity: O(text + pattern).

Task 1.7: String multi matching (1p)

Kattis problem: stringmultimatching

Implement a function that given a string and a set of patterns finds all matches in the string for each of the patterns. This is a generalization of Task 1.6, which means that if you solve this problem you have also solved the previous problem.

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

Recommended time complexity: O(text + patterns + k), where k is the total number of matches of all patterns.

Task 1.8: Suffix sort (2p)

Kattis problem: suffixsorting

Implement a data structure that sorts the suffixes of a string in lexicographical order, with the following operations:

  • constructor(string s) - create a suffix object from a string.
  • position getSuffix(i) - return the i:th smallest suffix.
The suffix can be represented by an index indicating the start of the suffix. If we sort the suffixes of the string "popup" we get: "opup", "p", "popup", "pup", "up". If we construct a suffix object from "popup" we will get: getSuffix(0) = 1, getSuffix(1) = 4, getSuffix(2) = 0, getSuffix(3) = 2, getSuffix(4) = 3.

A good test case is s = <W><W>, where <W> is a 50000 character long string with random characters.

Recommended time complexity: O(s log s) for the constructor and O(1) for getSuffix (note: it takes time to compare strings!).


Page responsible: Fredrik Heintz
Last updated: 2015-04-27