3461
Comment:

3471

Deletions are marked like this.  Additions are marked like this. 
Line 23:  Line 23: 
. = leftMunch lrsp  longest rightSkew prefix = rightMunch llds = rightMunch lrss  . = leftMunch lrsp  longest rightSkew prefix . = rightMunch llds . = rightMunch lrss 
2008 M Term Week 3
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)
WikiName Wiki
What is this wiki about?
Interesting starting points:
RecentChanges: see where people are currently working
WikiSandBox: feel free to change this page and experiment with editing
FindPage: search or browse the database in various ways
SyntaxReference: quick access to wiki syntax
SiteNavigation: get an overview over this site and what it contains
How to use this site
A Wiki is a collaborative site, anyone can contribute and share:
Edit any page by pressing Edit at the top or the bottom of the page
Create a link to another page with joined capitalized words (like WikiSandBox) or with [[words in brackets]]
 Search for page titles or text within pages using the search box at the top of any page
See HelpForBeginners to get you going, HelpContents for all help pages.
To learn more about what a WikiWikiWeb is, read about WhyWikiWorks and the WikiNature. Also, consult the HelpMiscellaneous/FrequentlyAskedQuestions page.
This wiki is powered by MoinMoin.