Maximum subarray problem：
2-3 2

1 -1

3 -3

1 -2 1

2 -3

Given an array A of length n, consider
A[s, t] = Σs≦j≦t A[j].
Problem: Find the indices s and t
maximizing A[s,t]1Maximum weight region
Maximum weight region problem:
Given afunction f*(p) on G, find the region R in theregion family Ｆ maximizing f* (R)Easy to solve if F is the family of• x-monotone regions

X-monoton

Really easy ?? If you are a professional,
you should find a professional solution.

2

Magic of Algorithms isthe heart of programming and system design
Programming Pearls ： Famous column in themagazine CACM ( Communications of ACM ),author: John Bentley

Bentley’s forewards
I am pleased to announce the inauguration ofProgramming Pearls, a new department ofCommunications devoted to theseemingly small things that distinguishgreat programs from other programs．

Programming Pearls ，1984，9月“Algorithm Design Techniques”
Find the interval maximizing the sum of entries in an array
Maximum subarray problem：
2-3 2

1 -1

3 -3

1 -2 1

2 -3

1

The story (1977)

2-3 2

1 -1

3 -31 -2 12 -3

1• U. Grenander (Reseacher in computer graphics ）• Find the rectangular region maximizing the entry sum• Start with one-dimensional problem•Tip： Simplify the problem•Naïve method O(n3)• n2 intervals, each interval has n entries•Grenander solved in O(n2) time
•Ask theory seminar of Bentley for a better method•Tip ： Talk with people with other expertiseMichael Shamos thought overnight, andA (I) : entry sum of an interval I
Define P(J)=MaxI⊆J A(I)We can compute the following
L([s,t])=Max j∈[s,t]A([1,j]),R([s,t])=Max j∈[s,t]A([j,t])
Divide the inteval J into J1 and J2 at the middle, thenP(J) = max{ P(J1), P(J2), R(J1)+L(J2)}
2-3 2

1 -1

30

1 -2 12 -3

1O(n log n) time

Jay Kadane’s DP Algorithm
I (max, k) : Max interval to the left of k
2-3 2

1 -1

3 -3 1 -2 1

2 -3

1k
J (max, k) : Max interval whose right end is k2Lemma:-3 2

1 -1 3 -3 1 -2 1

2 -31k•I(max, k) = Max {I(max, k-1) , J(max, k)}•J(max, k) = Max { J(max, k-1) +A(k) , A(k)}Dynamic Programming procedure runs in linear timeThis is not the end of story, just the start
Bentley’s open problem：“Solve 2-d problem efficiently”• O(n3) (Answers by readers in the next issue of CACM）•Steve Mahaney, E.W. Dijkstra ,etc 14 solvers• Better one? Open Problem
Challenge this problem??
• Not solved in Bentley’s seminar ?
• No progress for 15 years, but still ?
• You need idea, timing, and luck

• Tip： If you are interested, think seriously for a week
One day, you may find a solution （1998, Tamaki and T.）

One day, suddenly you find your luck.
M: Could I discuss on my research topic?
T: Of course, I am happy to listen
M: I want to design data mining system of numeric
data base, and badly need efficient algorithms?
T: What? What is “data mining” ?
M: This is my problem…..
T: Yes, this is similar to Bentley’s problem. Well, I
can solve it, and give details by tomorrow.
Actor： Dr. Morishita, working on database applications
Tip, You should happily accept requests of your friends, andanswer as quickly as possible.

Numeric Association Rule• 100 > t[BP] > 50 Æ Diseased = no• 100<t[HEIGHT] - t[WEIGHT] < 130conditional attributes

Æ

Diseased = notarget attribute

AGE

BP

HEIGHT

WEIGHT…

Diseased

23
21
42
30…

140
91
129
98…

168
176
165
182
…

7961
80
57
…

…
…
…
…
…

Yes
No
Yes
No…

Association Rules for Numeric Data
Rules that have the form:( A ∈ [ x1 , x2 ]) ⇒ B

Input: Data base with two attributes A and B.
Attribute A is numeric and B is binary (yes or no)
Output: A range I = [x1, x2] of attribute value of A
Support： The ratio of data whose A-value is in I
Confidence: Probability that B= 1 under the condition
that A is in I

Optimized Numeric Association Rules( A ∈ [ x1 , x2 ]) ⇒ B
We call a rule
• Well-supported if support ≥ minsup threshold.
• Confident if confidence ≥ minconf threshold.
Two types of optimized rules:• Optimized confidence rule : a well-supported rulesthat maximizes the confidence.
• Optimized support rule : a confident rule thatmaximizes the support.

Optimized support rule
Maximize A(I) under the condition (A^B)(I)>αA(I)A2012A^B
C=A^B-0.5A 23232 32 3432 343232 32 32

32

30151517 13188-1 -1 -1

1 -32-714 15

11 21

19 16-2 ‐1-5 4

3Computed in linear time. How to do it???
Geometric view is helpful.

Optimal confidence rule
A 21A^B 1232 23 31 34 3233 31 22 31 32 33 21
14 20 11 119 11 31 12

Condition: A(I)> β(min-sup)Maximize A^B(I)/A(I)Use convex hull algorithm
Surprising, isn’t it?

27 22 238

Transformation into a geometric problem
A 21A^B 1232 23 31 34 3233 31 22 31 32 33 21
14 20 11 11 9 11 31 12 27 22 23 8

• Generation of sequences of points

Qm = ( A([1, m], A^ B ([1, m]))Prefix sumsQs − Qt = ( A (( s, t ]), A^ B (( s, t ]))Qt

Qs

confidence＞ minsup threshold

Convex hull again!

Qt

Ur(s)

Qr(s)

Qs

confidence
minsup threshold

The tangent of Qs and the corresponding upper convex hullfor some s gives the range of the optimized confidence rule.

Computing Tangents (1)Compute tangents from left to right.
When Qs is above the previous tangent L:

Qk

QS
QS
minsup

Qk

L

The tangent of Qs cannot have larger slope than L.
Leave L untouched.

Computing Tangents (2)When Qs is below the previous tangent L.
When L does not touch the convex hull:

When L still touches the convex hull:
Clockwise
SearchQk

LQt

QS
CounterClockwise
SearchL
Qk
QS

Algorithm•Compute the Convex Hull Tree
•Compute tangent lines, moving the anchor
point from left to right.
•Update the tangent points•Walk on Convex Hull Tree
• Linear time algorithm