Algorithms

Question 1

Interval Scheduling (without weights)

Answer 1

Earliest End First (EEF)
Sort the intervals according to their right end-
points. That is, re-index them such that f1 < f2 < . . . < fn. Put the interval [s1, f1] (the one with the smallest fi) in X, and delete all intervals that intersect this first interval. Repeat this step until every interval is either
in X or deleted.

Question 2

What is a greedy algorithm?

Answer 2

In every step, make the currently best choice, according to some simple optimality criterion

Question 3

Weighted Interval Scheduling

Answer 3

Define OPT (j) to be the maximum weight that can be achieved by selecting a subset of disjoint intervals from the first j intervals.
Define auxiliary function, p(j): the largest index i such that
fi < sj (nr of interval that ends before the current start).

OPT(j) = max{OPT(j−1), OPT(p(j)) + vj }

Question 4

Prove that the greedy algoritm works

Answer 4

Prove by exchange argument:
1) Assume there is another better solution (change omega’ to omega, which is either a better or equal solution)
2) This solution must have some element where for example earlier end time comes later
3) Change from better solution to our Greedy by exchange (swap two elements)
4) Asertain that this new solution is not worse and in worst case as good if elements are the same

Question 5

Knapsack

Answer 5

OPT (j, w) = max{OPT(j − 1, w), OPT(j-1, w − wj ) + vj }

The knapsack problem formula OPT (j, w) represents the maximum value (OPT) that can be obtained by selecting items from a set, given their weights (wj) and values (vj), without exceeding a weight limit (w). It’s a dynamic programming equation where you choose the maximum value between not including the current item (OP T (j - 1, w)) and including it (OP T (j, w - wj) + vj).

O(nW)

Question 6

What is the subset sum?

Answer 6

OPT(j, w) = max{OPT (j − 1, w), OPT (j − 1, w − wj ) + wj }

n numbers with “value” w, and another target number W. Goal is to find the maximum sum of values that is ≤ W.
- Special case of knapsack where v=w.

Question 7

Dynamic programing for segmentation problem

Answer 7

OPT(j) = min i<j { OPT(j-1) + e_(ij)}
O(n^2)

Question 8

Sequence comparasion (string editing)

Answer 8

Given string A and B; transform A into B in the fewest possible steps (OPT). Gap symbol
OPT(i, j) = min{OPT(i−1, j−1)+δij , OPT(i−1, j)+1, OPT(i, j−1)+1}

Question 9

Searching

Answer 9

Given a set S of n items and another element x; Find x or report x not in S.

Question 10

Skyline

Answer 10

Involves finding the set of all points in a given dataset that are visible from a specific viewpoint or observer. The goal is to identify the highest or most relevant points in the dataset, which are not obscured by others when viewed from a particular angle.