2 Comments

1. 

   AYESHA MUMTAZ on February 8, 2019 at 11:08 am

   66. Compute the shortest-path weights bottom up FLOYD-WARSHALL(W, n)
   Ref: Handouts Page No.161
   Give a detailed example for 2d maxima problem
   Answer: –
   The problem with the brute-force algorithm is that it uses no intelligence in pruning out decisions. For example, once we know that a point pi is dominated by another point pj, we do not need to use pi for eliminating other points. This follows from the fact dominance relation is transitive. If pj dominates pi and pi dominates ph then pj also dominates ph; pi is not needed. Ref: Handouts Page No.17.

2. 

   AYESHA MUMTAZ on February 8, 2019 at 11:09 am

   67. How the generic greedy algorithm operates in minimum spanning tree?
   Answer: –
   A generic greedy algorithm operates by repeatedly adding any safe edge to the current spanning tree. When is an edge safe? Consider the theoretical issues behind determining whether an edge is safe or not. Let S be a subset of vertices S _ V. A cut (S, V − S) is just a partition of vertices into two disjoint subsets. An edge (u, v) crosses the cut if one endpoint is in S and the other is in V − S. Given a subset of edges A, a cut respects A if no edge in A crosses the cut. It is not hard to see why respecting cuts are important to this problem. If we have computed a partial MST and we wish to know which edges can be added that do not induce a cycle in the current MST, any edge that crosses a respecting cut is a possible candidate.
   Ref: Handouts Page No.143