রবিবার, ২৯ নভেম্বর, ২০১৫

access-blocked-sites
blocked_sitesWe all love to get things for free of cost, but the owners/producers hate that. This is the only fear of the digital era which take away the good night sleep of the owners/producers. As there are many websites which offer paid things for free of cost as well as distribute some copyrighted products. Eventually the authority of that country order their ISPs to block those websites for that country. But this is not always related to copyrighted activity or piracy. Sometimes block some websites due to the reason that the websites are not following that countries tradition, culture or believe. To some people that is a good thing but to some people this is a completely autocratic activity to take away the internet democratic freedom from all the people around the world. As an example Indian High Court has blocked over 200 websites due to streaming FIFA World Cup 2014 on their website. Not only that Japan has blocked many pornographic websites because it is against their culture. In this post I’m not going to argue whether this is good or bad thing, beside that I’m going to show you that if you are a victim of this Government internet autocracy, how you can access blocked sites from your computer.  Don’t worry what I’m going to share is not illegal at all or against any cyber crime law. So, get ready to open up blocked sites from your computer.
Today in this post I’m going to mention 5 most useful ways to access blocked websites by any countries ISP without violating any cyber laws. Many people might already knew what are the steps, but I do know that there are many people who do not know how to do it. This post is for them. So, here are the following tricks:

1. URL Rewriting Trick

This trick sometimes work for some websites. But it might not work for many websites. This trick only work for those websites who host their sites in a VPS or Dedicated Server environment and have an unverified SSL installed for that domain name. So in short what you have to do is :
Contribute to iSaumya.com and see less ads
  1. Go to the address bar of your browser
  2. Instead of typing www.WebsiteURL.com or http://www.WebsiteURL.com, try typing https://www.WebsiteURL.com.
If the domain has an unverified SSL installed it will show you up a security notice like the website you are going to visit is unverified/untrusted etc. Just click “Proceed Anyway” (in Chrome) or add exception certificate in firefox to proceed to the website.
SSL Error Page in Chrome
SSL Error Page in Chrome

2. Change the DNS Trick

DNS is the server which have all the information of all the websites around the world. Generally when any country block any website for their countries ISPs, thei block it in their own DNS server, so that whoever uses that DNS cannot access restricted sites. This same concept has been used by many MNC companies for their office internet access. But if you use Google DNS or OpenDNS, many times you can access blocked websites. This trick generally work very well for the BSNL internet users. Here is how you can do it on your devices.
For Windows Vista, 7, 8, 8.1 users, here are the instructions:
  1. For Windows Vista and 7, click Start > Control Panel > Network and Internet > Network and Sharing Center. If you’re using Windows 8, hit Windows key + C > click Search on the right-hand side > type Control Panel in the search bar > select Control Panel > Network and Internet > Network and Sharing Center.
  2. Click Change adapter settings, which is on the left sidebar.
  3. Right-click the Internet connection (MTNL, Airtel, BSNL, etc.) on which you’re having trouble accessing websites, and clickProperties.
  4. Select Internet Protocol Version 4 (TCP/IP), and then click Properties.
  5. Click the radio button next to Use the following DNS Server addresss. If you want to use Google DNS, enter 8.8.8.8 as the Preferred DNS Server and 8.8.4.4 as the Alternate DNS Server. If you want to use OpenDNS, use 202.67.220.220 and 202.67.222.222 respectively. After entering these, click OK.
network-settings
For Windows Vista, 7, 8, 8.1 users
For Windows XP users
  1. Click Start > Control Panel > Network Connections.
  2. Now select your specific Internet connection with access problems, right-click, then select Properties.
  3. Left-click Internet Protocol (TCP/IP), and select Properties.
  4. Follow the Step 5 instruction given above.
If you are using an iOS device that’s connected to a Wi-Fi network, try this.
  1. Open Settings > tap Wi-Fi > tap the Wi-Fi network the device is connected to.
  2. Tap DNS and change the two values to Google DNS or Open DNS (explained in step 5 above). These two values should be separated with a comma and one space (8.8.8.8, 8.8.4.4).
For Android users, these are the steps.
  1. Open Settings > tap Wi-Fi.
  2. Long press the Wi-Fi network you’re connected to > tap Modify Network.
  3. Now tap the box next to Show advanced options. Scroll down.
  4. Tap DHCP > select Static IP > scroll down and modify DNS 1 and DNS 2 (as explained in step 5 above).
On BlackBerry 10 devices, try this.
  1. Settings > Network and Connections > tap Wi-Fi. Now connect to a Wi-Fi network.
  2. Long-press the connection you’re connected to > tap Edit.
  3. Scroll down and turn off Auto Obtain IP. After you do this, you’ll see more options, such as the IP address, DNS and gateway. Switch to OpenDNS or Google DNS here (as explained in step 5 above).
Sorry! Unfortunately, Windows Phone 8 doesn’t support changing DNS manually.

3.  Using Proxy Trick

Some people does know that how to proxify a website, but many people does not. There are many popular proxy service available on the web. The most popular free proxy service websites are Hidemyass, kproxy, NewIPNow etc. What you have to do is, just copy your site URL paste it in any proxify website then choose your proxy location and visit the site. As simple as that.
Hide My Ass free web proxy service
Hide My Ass free web proxy service

4. Additional Proxy Layer

Sometimes no matter which method you try, your ISP is so smart that they wont allow you to visit a blocked website without using VPN. When you are in this scenario, I will suggest you to try out this last trick before purchasing VPN. Tough if you see that no trick is working, then be assured than VPN will always work in any circumstance. Anyway, before revealing this trick, I would like to warn you that as you are going to use Proxy IPs, do not provide sensitive information over proxyfied line and if you do, do it on your own risk.
Now lets get started. There are many sites who provide Proxy IP and Port List for free of cost, like HideMyAss Proxy List, Free Proxy Lists, inCloak Proxy List etc. Visit any of these sites and grab one Proxy IP : Port combination which hast good speed and fast connection type – as shown in the screenshot below.
Hide My Ass: Free Proxy IP : Port List
Hide My Ass: Free Proxy IP : Port List
After you get one Proxy IP : Port combination, use the following procedure to add it in popular browsers like Google Chrome & Firefox.
For Google Chrome users
  1.  Go to settings and click on Show Advance Settings
  2. Under the Network, click on the Change Proxy Settings Button
  3. When the popup comes, click on the button called LAN Settings
  4. On the next popup window check on “Use proxy server for your LAN“
  5. Also mark the “Bypass proxy server for local address“.
  6. Hit OK and save. That’s all. You are good to go.
Google Chrome: How to add Proxy IP : Port
Google Chrome: How to add Proxy IP : Port
For Firefox users
  1. Go to Options
  2. Click on “Advanced” with a gear box sign from the top navigation section of the popup window
  3. Select “Network” tab from the sub navigation
  4. Under the Connections, select the Settings button
  5. On the next popup window, select the radio button saying “Manual Proxy Configuration“
  6. Put your Proxy IP : Port in the HTTP Proxy section
  7. Check the “Use this proxy server for all protocol“.
  8. Hit OK and save.
Firefox: Add Proxy IP : Port
Firefox: Add Proxy IP : Port

By using Browser Extension (Updated)

If you are using Google Chrome and if you have access to Chrome Web Store, you can download an awesome extension app named ZenMate for opening blocked websites by your ISP. ZenMate is a very good auto proxify extention and is completely free. What you have to do is just install the extension and then open a free account with ZenMate and start browsing web with the ZenMate proxy servers. This is really easy to do, completely free and reliable.
Please note! ZenMate is not just for Google Chrome Browser only, it supports all other major browsers like FireFox, Opera. ZenMate even has supported official apps for iOS & Android devices too. Fore more please visit ZenMate Official Website.

5. Using VPN trick

For complete anonymity on the Web and to be able to access all websites blocked in your country, a virtual private network (VPN) is the best solution. The best VPNs are not free. If you really need privacy or want to avoid proxy websites, you can try Private Internet Access at $7 (Rs. 420) per month, or TorGuard at $10 (Rs. 600) per month. The above mentioned free web proxy sites also provide VPNs, you can also take a look into their pricing.

Conclusion

In the 21st century where out life is surrounded with internet, practically there is no way to block any website from users no matter what ISPs do about that harsh reality. If I’ve missed your favorite trick to open up blocked website in the above post, please let me know in the comment section below. 
You can also follow me on twitter +Arabi Moin  or subscribe to my newsletter to always stay updated with my new posts.
Posted by at কোন মন্তব্য নেই:

বৃহস্পতিবার, ১৬ এপ্রিল, ২০১৫

Dynamic Programming


  1. I. Perspective

  2. II. Principle of Optimality

  3. III. Steps of Dynamic Programming

  4. First Application: The Matrix Chain Problem

  5. Second Application: The All-Pairs Shortest Path Problem

  6. Third Application: Optimal Binary Search Trees



I. Perspective


  • Dynamic programming is an optimization technique.
  • Greedy vs. Dynamic Programming :
    • Both techniques are optimization techniques, and both build solutions from a collection of choices of individual elements.
    • The greedy method computes its solution by making its choices in a serial forward fashion, never looking back or revising previous choices.
    • Dynamic programming computes its solution bottom up by synthesizing them from smaller subsolutions, and by trying many possibilities and choices before it arrives at the optimal set of choices.
    • There is no a priori litmus test by which one can tell if the Greedy method will lead to an optimal solution.
    • By contrast, there is a litmus test for Dynamic Programming, called The Principle of Optimality
  • Divide and Conquer vs. Dynamic Programming:
    • Both techniques split their input into parts, find subsolutions to the parts, and synthesize larger solutions from smalled ones.
    • Divide and Conquer splits its input at prespecified deterministic points (e.g., always in the middle)
    • Dynamic Programming splits its input at every possible split points rather than at a pre-specified points. After trying all split points, it determines which split point is optimal.

II. Principle of Optimality


  • Definition: A problem is said to satisfy the Principle of Optimality if the subsolutions of an optimal solution of the problem are themesleves optimal solutions for their subproblems.
  • Examples:
    • The shortest path problem satisfies the Principle of Optimality.
    • This is because if a,x1,x2,...,xn,b is a shortest path from node a to node b in a graph, then the portion of xi to xj on that path is a shortest path from xi to xj.
    • The longest path problem, on the other hand, does not satisfy the Principle of Optimality. Take for example the undirected graph G of nodes a, b, c, d, and e, and edges (a,b) (b,c) (c,d) (d,e) and (e,a). That is, G is a ring. The longest (noncyclic) path from a to d to a,b,c,d. The sub-path from b to c on that path is simply the edge b,c. But that is not the longest path from b to c. Rather, b,a,e,d,c is the longest path. Thus, the subpath on a longest path is not necessarily a longest path.

III. Steps of Dynamic Programming


  • Dynamic programming design involves 4 major steps:
    1. Develop a mathematical notation that can express any solution and subsolution for the problem at hand.
    2. Prove that the Principle of Optimality holds.
    3. Develop a recurrence relation that relates a solution to its subsolutions, using the math notation of step 1. Indicate what the initial values are for that recurrenec relation, and which term signifies the final solution.
    4. Write an algorithm to compute the recurrence relation.
  • Steps 1 and 2 need not be in that order. Do what makes sense in each problem.
  • Step 3 is the heart of the design process. In high level algorithmic design situations, one can stop at step 3. In this course, however, we will carry out step 4 as well.
  • Without the Principle of Optimality, it won't be possible to derive a sensible recurrence relation in step 3.
  • When the Principle of Optimality holds, the 4 steps of DP are guaranteed to yield an optimal solution. No proof of optimality is needed.

IV. First Application: The Matrix Chain Problem


  • Input: n matrices A1, A2,...,An of dimensions
    P1 x P2, P2 x P3, ... , Pn x Pn+1, respectively.
  • Goal: to compute the matrix product A1A2...An
  • Problem: In what order should A1A2...An be multiplied so that it would take the minimum number of computations to derive the product.
  • Matrix multiplication cost:
    • Let A and B be two matrices of dimensions p x q and q x r.
    • Let C= AB. C is of diemnsions p x r
    • Element Cij= Ai1B1j + Ai2B2j + ... + AiqBqj
    • Thus Cij takes n scalar multiplications and (n-1) scalar additions.
    • Since scalar multiplication is more expensive than scalar addition, we count only the scalar multiplications.
    • Thus Cij takes n multiplications.
    • Therefore, AB takes p x r x q = pqr multiplications.
  • Example of the best way of multiplying 3 matrices:
    • takes A1 of dimensions 3 x 5, A2 of dimensions 5 x 7, and A3 of dimensions 7 x 2.
    • (A1A2)A3 takes 3*5*7 + 3*7*2=147
    • A1(A2A3) takes 5*7*2 + 3*5*2=100
    • Thus, A1(A2A3) is much cheaper to compute than (A1A2)A3, although Both lead to the same final answer.
    • Exercise: Formulate a greedy method for the Matrix Chain Problem, and prove by a counter example that it does not necessarily lead to an optimal solution.
    • A Dynamic programming design:
      • Notation: let Mij denote the cost of multiplying Ai...Aj, where the cost is measured in the number of scalar multiplications.
        Clearly, M(i,i)=0 for all i, and M(1,n) is what we are looking for.
      • Proof of the principle of optimality
        • Every way of multiplying a sequence of matrices can be represented by a binary (infix) tree, where the leaves are the matrices, and the internal nodes are intemediary products.
        • Let T be the tree correspodning to the optimal way of multiplying Ai...Aj.
        • T has a left subtree L and a right subtree R. L corresponds to multiplying B=Ai...Ak, and R to multiplying C=Ak+1 ... Aj, for some integer k (i <= k <= j-1).
        • The cost corresponding to T is
          cost(T)= cost(R) + Cost(L) + cost(BC).
        • for the Principle of Optimality to hold, we need to show that L is the best tree of Ai...Ak, and R is the best tree for Ak+1 ... Aj. It suffices to show it for L.
        • The proof is by contradiction. If L were not optimal, then there would be a better tree L' for Ai...Ak.
        • Cost(L') < Cost(L).
        • Then, takes the tree T' whose left subtree is L' and whose right subtree is R.
        • Cost(T') = Cost(L') + Cost(R) + Cost(BC) 
         < Cost(L) + Cost(R) + Cost(BC) = Cost(T)
        • Thus, Cost(T') < cost(T), which contradicts the fact that T was the best tree for its matrices.
        • Therefore, L must be optimal. Q.E.D.
      • Derivation of the recurrence relation:

        • use the same notation T, L and R for the optimal way of multiplying Ai...Aj. L is the left subtree corresponding to Ai...Ak (for some k), and R corresponds to Ak+1...An.
        •  
Mij=cost(T)
      =Cost(L)+Cost(R)+Cost(BC)
      =Mik + Mk+1,j + PiPk+1Pj+1.
        • Since we do not know the right value of k, and since Mij is supposed to be the minimum possible, the relation should be
          Mij=min{Mik + Mk+1,j + PiPk+1Pj+1 | i <= k <= j-1}
      • Illustration:

        • n=4. A1 is 3 x 5, A2 is 5 x 7, A3 is 7 x 3, and A4 is 3 x 4
        • P1=3, P2=5, P3=7, P4=3, P5=4
        • We will build a table to compute the Mijs bottom up. For each Mij, we record the k that gives Mij its min vakue
        • M11=0M22=0M33=0M44=0
          M12=105M23=105M34=84
          M13=150
          k=1          		M24=165
          k=3
          M14=186
          k=3

        • Optimal multiplication way: (A1(A2A3))A4.

V. Second Application: The All-Pairs Shortest Path Problem


  • Input: A weighted graph, represented by its weight matrix W.
  • Problem: find the distance between every pair of nodes.
  • Dynamic programming Design:

    • Notation: A(k)(i,j) = length of the shortest path from node i to node j where the label of every intermediary node is <= k.
      A(0)(i,j) = W[i,j].
    • Principle of Optimality: We already saw that any sub-path of a shortest path is a shortest path between its end nodes.
    • recurrence relation:
    • Divide the paths from i to j where every intermediary node is of label <=k into two groups:

      1. Those paths that do go through node k
      2. Those paths that do not go through node k.
    • the shortest path in the first group is the shortest path from i to j where the label of every intermediary node is <= k-1.
    • therefore, the length of the shortest path of group 1 is A(k-1)(i,j)
    • Each path in group two consists of two portions: The first is from node i to node k, and the second is from node k to node j.
    • the shortest path in group 2 does not goe through K more than once, for otherwise, the cycle around K can be eliminated, leading to a shorter path in group 2.
    • Therefore, the two portions of the shortest path in group 2 have their intermediary labels <= k-1.
    • Each portion must be the shortest of its kind. That is, the portion from i to k where intermediary node is <= k-1 must be the shortest such a path from i to k. If not, we would get a shorter path in group 2. Same thing with the second portion (from j to k).
    • Therefore, the length of the first portion of the shortest path in group 2 is A(k-1)(i,k)
    • Therefore, the length of the 2nd portion of the shortest path in group 2 is A(k-1)(k,j)
    • Hence, the length of the shortest path in group 2 is A(k-1)(i,k) + A(k-1)(k,j)
    • Since the shortest path in the two groups is the shorter of the shortest paths of the two groups, we get
    • A(k)(i,j)=min(A(k-1)(i,j), A(k-1)(i,k) + A(k-1)(k,j)).
    • The algorithm follows:


Procedure APSP(input: W[1:n,1:n];A[1:n,1:n])
begin 
   for i=1 to n do
      for j=1 to n do
         A(0)(i,j) := W[i,j];
      endfor
   endfor
   for k=1 to n do
      for i=1 to n do
         for j=1 to n do
            A(k)(i,j)=min(A(k-1)(i,j),A(k-1)(i,k) + A(k-1)(k,j))
         endfor
      endfor
   endfor
end


  • Note that once A(k) has been computed, there is no need for A(k-1)
  • Therefore, we don't need to keep the superscript
  • By dropping it, the algorithm remains correct, and we save on space
  • the new implementation follows:


Procedure APSP(input: W[1:n,1:n];A[1:n,1:n])
begin 
   for i=1 to n do
        for j=1 to n do
           A(i,j) := W[i,j];
        endfor
   endfor
   for k=1 to n do
        for i=1 to n do
           for j=1 to n do
              A(i,j)=min(A(i,j),A(i,k) + A(k,j));
           endfor
        endfor
   endfor
end

  • Time Complexity Analysis:

    • The first double for-loop takes O(n2) time.
    • The tripl-for-loop that follows has a constant-time body, and thus takes O(n3) time.
    • Thus, the whole algorithm takes O(n3) time.


VI. Third Application: Optimal Binary Search Trees


  • Input: a1 < a2 < ... < an
    p1 p2 ... pn
    q0 q1 q2 ... qn
    pi = Prob[ai is accessed], i=1,2,...,n
    qi = Prob[accessing an element X, ai < X < ai+1]
    q0 = Prob[accessing an element X, X < a1]
    qn = Prob[accessing an element X, an < X]
  • Problem: Find for the the array a1..n a binary search tree of minimum cost.
  • Cost Measure: average search time 
    When computing the average, take into account both successful and unsuccessful searches.
  • Quantitatively, cost of a BST T is C(T) where
    C(T)= SUMni=1 picost(ai) +SUMni=0 qicost(X, ai < X < ai+1)
    (to simplify the notation, assume a0 = -infinity and an+1 = infinity)cost(ai) = level(ai) + 1
    cost(X, ai < X i+1) = level(Ei)
    where
    Ei = External node where X would be if it were in the tree
  • Notation:
    Tij = OBST(ai+1, ... , aj)
    Cij = cost(Tij)
    Cij = SUMjs=i+1 ps{level Tij(as) + 1} + SUMjs=i qslevel Tij(Es)
    T0n is the final tree being sought
    T00 is empty
    Ti,i+1 is a single-node tree that has element ai+1
  • Principle of Optimality:

    • Let T0n be an OBST for the elements a1 < a2 < ... < an, and let L and R be its left subtree and right subtree. Suppose that the root of T0n is ak, for some k.
    • Clearly, the numbers in the tree L are a1, a2, ... , ak-1
      and the numbers in the tree R are ak+1, ak+2, ... , an.
    • We need to show that L is an OBST for its elements (and also R is an OBST for its elements).
    • It will be shown below that C(T0n)=C(L)+C(R)+ p1+p2+...+pn + q0+q1+q2+...+qn
    • That is,
      C(T0n)=C(L)+C(R)+W
      where
      W=p1+p2+...+pn + q0+q1+q2+...+qn

    • W is independent of the structure of L and R.
    • If L is not an optimal BST for its elements, then we can find a better tree L' for the same elements, where C(L') < C(L). Let T' be the tree with root ak, left subtree L' and right subtree R.
    • We have
      C(T') = C(L') + C(R) + W < C(L) + C(R) + W < C(T0n)
    • That is, T' is better than T0n, contradicting the fact that T0n is an optimal BST. Therefore, L must be an optimal BST for its elements. The same proof applies to R.
    • Thus, a subtree of an OBST must be an OBST. This proves the principle of optimality.
  • Recurrence Relation for Cij:

    1. Tij is rooted at ak, for some k, (i+1 <= k <= j), its left subtree is Ti,k-1 and it right subtree is Tkj.
    2. Cij = SUMjs=i+1 ps{level Tij(as) + 1} + SUMjs=i qslevel Tij(Es)
    3. Ci,k-1 = SUMk-1s=i+1 ps{level Ti,k-1(as) + 1} +
      SUMk-1s=iqslevel Ti,k-1(Es)
    4. Ckj = SUMjs=k+1 ps{level Tkj(as) + 1} +
      SUMjs=k qslevel Tkj(Es)
    5. SUMjs=i+1 ps{level Tij(as) + 1} =
      SUMk-1s=i+1 ps{level Tij(as) + 1} +
      pk{level Tij(ak + 1} +
      SUMjs=k+1 ps{level Tij(as) + 1} =
      SUMk-1s=i+1 ps{level Tij(as) + 1} +
      pk +
      SUMjs=k+1 ps{level Tij(as) + 1}
    6. Noting that levelTij(as)= levelTi,k-1(as) + 1 for i <= k-1, and
      levelTij(as)= levelTkj(as) + 1, for i >= k+1, we conclude from (5):
    7. SUMjs=i+1 ps{level Tij(as) + 1} = SUMk-1s=i+1 ps{level Ti,k-1(as) + 1+1} + pk + SUMjs=k+1 ps{level Ti,k-1(as) + 1+1} =
      SUMk-1s=i+1 ps{level Ti,k-1(as) + 1} + SUMjs=k+1 ps{level Ti,k-1(as) + 1} + SUMk-1s=i ps + pk + SUMjs=k+1 ps
      SUMjs=i+1 ps{level Tij(as) + 1} = SUMk-1s=i+1 ps{level Ti,k-1(as) + 1} + SUMjs=k+1 ps{level Ti,k-1(as) + 1} + SUMjs=i+1 ps
      Similar arithmetic will show that
      SUMjs=i qslevel Tij(Es) = SUMk-1s=iqslevel Ti,k-1(Es) + SUMjs=k qslevel Tkj(Es) + SUMjs=i qs
    8. Therefore,
      Cij = SUMk-1s=i+1 ps{level Ti,k-1(as) + 1} +
      SUMjs=k+1 ps{level Ti,k-1(as) + 1} +
      SUMjs=i+1 ps +
      SUMk-1s=iqslevel Ti,k-1(Es) +
      SUMjs=k qslevel Tkj(Es +
      SUMjs=i qs =
      Ci,k-1 + Ckj + SUMjs=i+1 ps + SUMjs=i qs
    9. Cij = Ci,k-1 + Ckj + WijWij = SUMjs=i+1 ps + SUMjs=i qs
    10. Since we don't know which k should be at the root, and since we want to minimize Cij, we should take the k that gives the minimum. Therefore,
    11. Cij = mini+1 <= k <= j{Ci,k-1 + Ckj + Wij}
      Wij = SUMjs=i+1 ps + SUMjs=i qs
      Cii = 0, Wii = qi
      Denote by rij the index k that gives the minimum to Cij.

  • Algorithm:
    

    
This procedure computes the weights Wijs 

Procedure Weight(Input:p[1:n], q[0:n]; Output: W[0:n,0:n])
begin
   for i=1 to n do
      W[i,i] = q(i);
   endfor

   for l=1 to n do
      for i=0 to n-l do
         k = i+l;
         W[i,k]=W[i,k-1] + p[k] + q[k];
      endfor
   endfor
end 


    


    

    
This procedure computes the Cijs and the
rijs 

Procedure OBST(Input:p[1:n], q[0:n], W[0:n,0:n]; 
  Output: C[0:n,0:n], r[0:n,0:n])
begin
   for i=0 to n do
      C[i,i] := 0;
   endfor

   for l=1 to n do
      for i=0 to n-l do
         j=i+l;
         C[i,j] := infinity;
         m := i+1; --m keeps the index of the min
         for k=i+1 to j do
            if C[i,j] >= C[i,k-1] + C[k,j] then
               C[i,j] := C[i,k-1] + C[k,j];
               m := k;
            endif
         endfor
         C[i,j] := C[i,j] + W[i,j];
         r[i,j] := m;
      endfor
   endfor
end

    
    


    

    
This procedure creates the tree Tij

Procedure create-tree(Input: r[0:n,0:n], a[1:n], i, j; 
   Output: T)
begin
   if (i==j) then T=null; return; endif
   T := new(node); -- the root of Tij
   k := r[i,j];
   T --> data := a[k];
   if (j==i+1) return; endif
   create-tree(r[0:n,0:n], a[1:n], i, k-1; T --> left);
   create-tree(r[0:n,0:n], a[1:n], k, j; T --> right);
end

    
    


    

    
This procedure is the master program that 
creates the whole tree T0n

Procedure Final-tree(Input: a[1:n],p[1:n],q[1:n]; 
   Output: T)
begin
   Weight(p[1:n], q[0:n], W[0:n,0:n]);
   OBST(p[1:n], q[0:n], W[0:n,0:n], 
  C[0:n,0:n], r[0:n,0:n]);
   create-tree(r[0:n,0:n], a[1:n], 0, n, T); 
end

  • Example:
    • a1 < a2 < a3 < a4p1=1/10, p2=2/10, p3=3/10, p4=1/10
      q0=0, q1=1/10, q2=1/20, q3=1/20, q4=1/10
      W00=0W11=1/10W22=1/20W33=1/20W44=1/10
      W01=2/10W12=3.5/10W23=4/10W34=2.5/10
      W02=4.5/10W13=7/10W24=6/10
      W03=8/10W14=9/10
      W04=10/10

      C00=0C11=0C22=0C33=0C44=0
      C01=2/10
      r01=1      		C12=3.5/10
      r12=2      		C23=4/10
      r23=3      		C34=2.5/10
      r34=4
      C02=6.5/10
      r02=2      		C13=10.5/10
      r13=3      		C24=8.5/10
      r24=3
      C03=14/10
      r03=2      		C14=15/10
      r14=3
      C04=19/10
      r04=3
    • The tree T04 has as root a3 because r04=3
      The left subtree is then T02 and the right subtree is T34
      T34 is a single-node tree having a4 because r34=4
      T02 has as root a2 because r02=2
      The left subtree of T02 is T01 and its right subtree is T22 (which is empty)
      T01 is a single-node tree having a1 because r01=1
      this completes the tree (to be drawn in class).
    • Posted by at কোন মন্তব্য নেই:
    Labels: ,
    এতে সদস্যতা: পোস্টগুলি (Atom)