Difference between pages "4.9" and "7.23"

From The Algorithm Design Manual Solution Wiki
(Difference between pages)
Jump to navigation Jump to search
 
(Created page with " for any node in the tree, there are two possibilities # either the diameter is contained in one of the subtrees # or the node itself is at the top of the longest path in the...")
 
Line 1: Line 1:
−
Here the main thing to notice is that we need a O(<math>n^{k-1}logn</math>) solution. <br />
 
−
For various values of k,  <br />
 
−
k      Solution Time Complexity <br />
 
−
1      O(<math>n^0logn</math>) <br />
 
−
2      O(<math>n^1logn</math>) <br />
 
−
3      O(<math>n^2logn</math>) <br />
 
−
4      O(<math>n^3logn</math>) <br />
 
  
−
for k = 2 onwards <br />
+
for any node in the tree, there are two possibilities
−
1. sort the array ( nlogn ) <br />
+
# either the diameter is contained in one of the subtrees
−
2. use k-1 loops for iterating over array, where ith loop starts from i-1 + 1 element of array, and then use binary search <br />
+
# or the node itself is at the top of the longest path in the tree that defines the diameter
−
eg: <br />
 
−
for k = 3 <br />
 
−
for( i = 0; i < n; i++ ) <br />
 
−
for( j = i+1; j < n; j++ ) <br />
 
−
# now use binary search to find ( T - a[i] - a[j] ) from j+1 element to end of array <br />
 
  
−
<h3>Another recursive solution</h3>
+
in the second case, the diameter is equal to the sum of depth of the two deepest sub-trees of that node
−
First, we note that an O(<math>n \lg n</math>) solution for <math>k = 2</math> exists, which is already within the required bounds. Now, for <math>k \ge 3</math>, we can do something like this:
 
  
−
<pre>
+
the following algorithm calculates the diameter in <math>O(n)</math> time
−
sort S ascending;
 
−
CheckSumOfK(S, k, T); // defined below
 
  
−
// S must be aorted array of integers
+
<source lang="python">
−
function CheckSumOfK(S, k, T)
 
−
    if k <= 2:
 
−
        Use any method in the solution of ex 4.8 and return the result. This can be done in O(n) time because S is sorted.
 
  
−
    Initialize array A of n - 1 elements;
+
class Node:
−
    for i from 0 to n - 1:
 
−
        k = 0
 
−
        // Collect in A all numbers in S but S[i]. Note that A will still be sorted.
 
−
        for j from 0 to n - 1:
 
−
            if i != j:
 
−
                A[k] = S[j];
 
−
                k = k + 1
 
−
        // If S[i] is included in the k integers that sum up to T, then there must
 
−
        // exactly (k - 1) integers in the rest of S (i.e., A) that sum to (T - S[i]).
 
−
        // We can find that out by calling ourselves recursively.
 
−
        if CheckSumOfK(A, k - 1, T - S[i]):
 
−
            return True
 
−
    return False
 
−
</pre>
 
  
−
<h3>Complexity</h3>
+
    def __init__(self, value, children):
−
For each item in S, there is <math>O(n)</math> work done in assembling the array A, except at the <math>{k - 1}^{th}</math> recursive call, which completes in <math>O(n \lg n)</math> time. So, for each number in S, we have <math>O(kn) + O(n \lg n)</math> work, and since <math>k <= n</math>, each iteration of the outer loop takes <math>O(n^2) + O(n \lg n) = O(n^2)</math>
+
        self.value = value
−
work. Now since the outer loop goes on for at most <math>n</math> iterations, we have a total runtime of <math>O(n^3)</math>.
+
        self.children = children
  
−
A trick can be used to lower this runtime to <math>O(n^2 \lg n)</math> by having the routines in [[ TADM2E 4.8 | this solution ]] take an index to ignore when iterating in their inner loops. With this, we save the <math>O(n)</math> construction of A for every
+
    @classmethod
−
item, and then each iteration of the outer loop becomes <math>O(n \lg n)</math> (How? <math>O(k) = O(n)</math> constant time recursive calls plus <math>O(n \lg n)</math> time spent in the <math>{k - 1}^{th}</math> calls), giving a total runtime of <math>O(n^2 \lg n)</math> for <math>n</math> elements in S.
+
    def preorder(cls, lists):
 +
        return cls(
 +
                lists[0],
 +
                [cls.preorder(l) for l in lists[1:]]
 +
            )
  
−
Note that this cost includes the initial <math>O(n \lg n)</math> cost for sorting S. Also, this algorithm is always going to be <math>O(n^{k-1} \lg n)</math> for all <math>k >= 2</math>. The exercise just states an upper bound.
+
 +
def dd(root):
 +
    """
 +
    returns depth, diameter for tree with given root node
  
 +
    >>> dd(Node.preorder([0, [1], [2]]))
 +
    (1, 2)
 +
    >>> dd(Node.preorder([1, [2, [3]], [4, [5]]]))
 +
    (2, 4)
 +
    >>> dd(Node.preorder([1, [2, [3, [4]], [5, [6, [7], [8]]]], [9]]))
 +
    (4, 5)
 +
    """
 +
    d1 = d2 = -1
 +
    md = 0
 +
    for child in root.children:
 +
        depth, diameter = dd(child)
 +
        if diameter > md:
 +
            md = diameter
 +
        if depth >= d1:
 +
            d2 = d1
 +
            d1 = depth
 +
        elif depth > d2:
 +
            d2 = depth
 +
    return d1 + 1, max(md, d1 + d2 + 2)
  
−
Back to [[Chapter 4]]
+
 
 +
if __name__ == "__main__":
 +
    import doctest
 +
    doctest.testmod()
 +
 
 +
</source>
 +
 
 +
 
 +
Back to [[Chapter 7]]

Latest revision as of 01:07, 21 September 2020

for any node in the tree, there are two possibilities

  1. either the diameter is contained in one of the subtrees
  2. or the node itself is at the top of the longest path in the tree that defines the diameter

in the second case, the diameter is equal to the sum of depth of the two deepest sub-trees of that node

the following algorithm calculates the diameter in [math]\displaystyle{ O(n) }[/math] time 

class Node:

    def __init__(self, value, children):
        self.value = value
        self.children = children

    @classmethod
    def preorder(cls, lists):
        return cls(
                lists[0],
                [cls.preorder(l) for l in lists[1:]]
            )

 
def dd(root):
    """
    returns depth, diameter for tree with given root node

    >>> dd(Node.preorder([0, [1], [2]]))
    (1, 2)
    >>> dd(Node.preorder([1, [2, [3]], [4, [5]]]))
    (2, 4)
    >>> dd(Node.preorder([1, [2, [3, [4]], [5, [6, [7], [8]]]], [9]]))
    (4, 5)
    """
    d1 = d2 = -1
    md = 0
    for child in root.children:
        depth, diameter = dd(child)
        if diameter > md:
            md = diameter
        if depth >= d1:
            d2 = d1
            d1 = depth
        elif depth > d2:
            d2 = depth
    return d1 + 1, max(md, d1 + d2 + 2)


if __name__ == "__main__":
    import doctest
    doctest.testmod()


Back to Chapter 7

Retrieved from "https://algorist.com//algowiki/index.php?title=4.9&oldid=360"