Jawaharlal Nehru Technological University Hyderabad B.Tech II DESIGN AND ANALYSIS OF ALGORITHMS Previous Question Paper (July/August - 2021 - R15)

To solve the recurrence relation T(n) = 4T(n/2) + n², we use the Master Theorem. The recurrence is in the form T(n) = aT(n/b) + f(n), where a = 4, b = 2, and f(n) = n².

First, calculate the value of n^log_ba:

Comparing f(n) = n² with n^log_ba = n², we observe that f(n) = Θ(n^log_ba). This corresponds to Case 2 of the Master Theorem.

According to Case 2, if f(n) = Θ(n^log_ba), then the solution is:

Substituting the values, we get:

A Bi-connected component (or biconnected component) is a maximal biconnected subgraph of a given undirected graph. A graph is biconnected if it remains connected after the removal of any single vertex and its incident edges.

The properties of Bi-connected components include:

• Articulation Points: An articulation point is a vertex whose removal increases the number of connected components. Every articulation point belongs to at least two different biconnected components.
• Edge Disjointness: Any two distinct biconnected components share at most one vertex, which must be an articulation point. No two biconnected components share an edge.
• Partitioning: Every edge of the graph belongs to exactly one biconnected component. Thus, the set of biconnected components forms a partition of the edges of the graph.
• Cycles: A biconnected component is either a simple cycle, a single edge (bridge), or a complex structure where any two vertices lie on a common simple cycle.
• Robustness: These components represent the most robust parts of a network; even if one node fails, the connectivity within the component is maintained (excluding the articulation points).