Archive for the ‘Algorithm’ Category

Given a string S, we are to find the longest sub-string s of S such that the reverse of s is exactly the same as s.
First insert a special character ‘#’ between each pair of adjacent characters of S, in front of S and at the back of S. After that, we only need to check palindrome sub-strings of odd length.
Let P[i] be the largest integer d such that S[i-d,…,i+d] is a palindrome.  We calculate all P[i]s from left to right. When calculating P[i], we have to compare S[i+1] with S[i-1], S[i+2] with S[i-2] and so on. A comparison is successful if two characters are the same, otherwise it is unsuccessful. In fact, we can possibly skip some unnecessary comparisons utilizing the previously calculated P[i]s.
Assume P[a]+a=max{ P[j]+j :  j<i }. If P[a]+a >= i, then we have
P[i] >= min{ P[2*a-i],  2*a-i-(a- P[a])}
Is it the algorithm linear time? The answer is yes.
First the overall number of unsuccessful comparisons is obviously at most N.
A more careful analysis show that S[i] would never be compared successfully with any S[j](j<i) after its first time successful comparison with some S[k] (k<i).
So the number of overall comparisons is a most 2N

It turns out that this algorithm is called Manacher’s algorithm.

Read Full Post »

Bottleneck Spanning Tree

A MST is obviously a BST. In fact, a simply linear algorithm exists for BST.
It appears in CLRS problem  23-3, but I didn’t come up with it and just Google it. I stupid!!!
It looks like a divide and conquer algorithm.
Find the median of all edge weights Em.
Using a DFS to check whether there exists a spanning tree with edge  weights not greater than Em.
If yes, remove all edges of weight greater than Em. Repeat.
If no, contract  all edges  of weight not greater than Em and get a smaller graph. Repeat.

Obviously, each edge is processed one time. 

Read Full Post »

A segment tree T stores a set S of n intervals on the line. A standard segment tree is a balanced binary search tree over the 2n endpoints of S that are stored at the leavesof T . We use the same notation for both a leaf and the point that it contains. We associate an interval denoted
by range(v) with each node v in T . If v is a leaf then range(v) is the interval [v, v]. If v is an internal node, where w is the leftmost leaf in the subtree rooted by v, and z is the rightmost leaf in the subtree rooted by v, then range(v) = [w, z]. We associate with each node v in T a set S(v) consisting of all segments s in S containing range(v) but not containing range(p(v)). Each node v in T holds a secondary data structure, representing the set S(v).
An interval tree is defined similarly. The difference is that in an interval tree an interval s = (xs, xe) is in S(v) if and only if v is the lowest common ancestor of xs and xe in T . It follows that a segment tree required O(n log n) space and an interval tree requires O(n) space.

Read Full Post »

Sometime, we need maintain a segment tree, which supports querying a minimal of a specified interval and adding a constant to a specified interval. It’s a common problem in programming contest. Usually, we maintain the interval segment tree by a folk technique called "deferred operation" or "contract subtree". Let’s see how Tarjan dealt with this problem in his paper on Dynamic Tree.
dvalue[v]=value[v]-value[parent[v]] if v is not root, otherwise value[v] if v is root.
dmin[v]=min[v]-min[parent[v]] if v is not root, otherwise min[v] if v is root.
It’s easy to maintain the segment tree of dvalue[] and dmin[].
Moreover, it’s elegant!  

Read Full Post »

How to solve a difference constraints system subjected to that a subset (not necessary all)
of unknowns must be integral? 

Read Full Post »

Red-Black Tree

上周实现了一下RB Tree,其实并不是想象中的那么麻烦(split和join暂缺,主要是模板类结构没规划好,
顺便orz一下它的发明者R.Bayer(发现者?奇怪的是,paper中大都说xx discover了xx算法)。

  1. 每个节点只需要一个bit的用于平衡的额外空间,而AVL需要记录高度。
  2. 每次作Fixup的时候,RBTree的Rotate次数是O(1)的,而AVL是O(lgN)的。
  3. 虽然RBTree作Fixup时Recolor的操作是O(lgN)的,但是其均摊复杂度确是O(1)的!这个意味着,N个插入删除操作的代价是O(N)的。(参见CLRS习题)

不过,ms AVL树更平衡,因为兄弟子树高度差不超过1,而RBTree一棵子树的实际高度可能是其兄弟子树的2倍。

Read Full Post »

A graph can be D+1 edge colored, where D is its maximum vertex degree.
Furthermore, a bipartite can be D edge colored.
The D+1 edge coloring algorithm below can also be considered as a proof.
First, for any bipartite there always exists a maximum match so that
the remaining bipartite’s D drops exact 1, if the match edges are removed.
It’s trivial to prove it by augment path.
So it just implies that bipartite is D edge-colorable.
For any graph G with maximum degree D,
we can divide the vertices of G into two groups V1 and V2
so that the degree of each vertex of induced bipartite G(V1,V2) is at least
half of original degree in G. Then the induced graphs G(V1), G(V2) have maximum
degree floor(D/2) and can be colored with 1+floor(D/2) respectively by induction assumption.
Meanwhile bipartite G(V1,V2) with maximum D-floor(D/2) can be colored with D-floor(D/2) colors.
Sum them up, G can be colored with D+1 colors.

Edge-coloring for bipartite graph.
It’s can be proven that there always exists a  maximum match in which every vertex in the graph
with maximum degree is matched. So just color the edges in the match with same color.

Read Full Post »

Older Posts »