⇤ ← Revision 1 as of 20090515 13:33:30
43
Comment:

← Revision 2 as of 20090515 13:34:09 ⇥
2170

Deletions are marked like this.  Additions are marked like this. 
Line 2:  Line 2: 
Presenter : Sharon Curtis Sharon presented a solution to the maximumdensity segment problem with decreasing rightskew 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 rightskew (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 highestdensity prefix . = leftMunch lrsp  longest rightSkew 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 maximumdensity 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 maximumdensity 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) 
Minutes from Algprog meeting of 20090424.
Presenter : Sharon Curtis
Sharon presented a solution to the maximumdensity segment problem with decreasing rightskew 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 rightskew (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 highestdensity prefix
 = leftMunch lrsp  longest rightSkew 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 maximumdensity 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 maximumdensity 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)