Minutes from Algprog meeting of 20090424.

Presenter : Sharon Curtis

Sharon presented a solution to the maximum-density segment problem with decreasing right-skew partition (DRSP).

Density is defined as the total area of a sequence of items over the total width. In a DRSP, the density of each segment must be strictly decreasing and each segment must be right-skew (defined below)

forall u,v st. y = u++v => density u <= density v

The four ways that computes the unique DRSP is

drsp :: [Item] -> Item

drsp x = leftMunch lhdp - longest highest-density prefix

- = leftMunch lrsp -- longest right-Skew prefix
- = rightMunch llds
- = rightMunch lrss

leftMunch :: ([Item] -> [Item]) -> [Item] -> Item

leftMunch m [] = []

leftMunch m x = y : leftMunch (drop (#y) x)

- where y = m x

Consider the maximum-density segment with a minimum length l.

The solution is to start with a suffix (window) of the sequence and take away the first l elements. The rest of the suffix is DRSPed. It is then checked segment by segment to append to the first l elements.

After this step, the remaining window (first l element + the chosen segments) is shifted leftwards by consing one element to the left. As a result, the first l compulsory elements are also shifted leftward and the DRSP of the remaining list is updated with one more element to the left.

This update is easy given the following property

tail (drsp (x:xs)) is a suffix of drsp xs

To implement this update, the sequence is represented as a tree.

DTree a = Node a [DTree a]

makeDTree (i,is) = Node i (map makeDTree (drsp is))

Ralf's comment here:

Density does not play a part here. It is all about partition properties,

which is orthogonal and more general.

This algorithm can be generalized with maximum-density segment with both a minimum length and a maximum length.

In general, it is needed to split a tree. It is again down to reDRSP it with a suffix dropped.

Jeremy and Geraint's proof of

density x <= density y and rightSkew x and rightSkew y implies rightSkew (x++y)

density x1 <= density (x1++x2++y) <= density (x2++y)