JNTU B.Tech IV ADVANCED ALGORITHMS Previous Question Paper (December - 2020 - R16)

The given recurrence relation is:

We will solve this using the substitution method. Assume the solution is of the form T(n) = O(n^k) for some constant k.

Step 1: Guess the form of the solution.

Let's guess T(n) = cn² for some constant c. We will try to prove this by induction.

Step 2: Inductive Hypothesis.

Assume that T(k) ≤ ck² for all k < n.

Step 3: Inductive Step.

We need to show that T(n) ≤ cn².

Substitute the hypothesis into the recurrence relation:

Using the inductive hypothesis, T(n/2) ≤ c(n/2)² = cn²/4.

So, T(n) ≤ 4(c(n/2)²) + n²

T(n) ≤ cn² + n²

T(n) ≤ (c+1)n²

To satisfy T(n) ≤ cn², we need c+1 ≤ c. This is not possible for any positive constant c.

This suggests that our initial guess T(n) = cn² might be too tight, or we need to consider an additive term.

Let's try a slightly modified guess: T(n) = cn² - dn for some constants c and d. However, the substitution method often works best when the guess is close to the expected form. Let's re-examine the recurrence and consider the possibility of a lower-order term.

Let's try T(n) = cn² + bn for some constants c and b. This is still not quite right. The standard approach for substitution is to prove an upper bound.

Let's go back to T(n) ≤ cn² and see if we can find a c that works, potentially with a base case adjustment.

T(n) ≤ 4T(n/2) + n²

Assume T(k) ≤ ck² for k < n. We want to show T(n) ≤ cn².

T(n) ≤ 4(c(n/2)²) + n²

T(n) ≤ 4(cn²/4) + n²

T(n) ≤ cn² + n²

This implies T(n) ≤ (c+1)n². For this to fit the form T(n) ≤ cn², we need c+1 ≤ c, which is impossible. This means that the O(n²) term dominates and the recurrence is indeed O(n²). However, to *prove* it by substitution, we often need to add a lower-order term to the assumed solution to make the inductive step work.

Let's try T(n) ≤ cn² - dn for some d > 0. This is a common technique when the direct guess doesn't quite close.

Assume T(k) ≤ ck² - dk for all k < n.

T(n) = 4T(n/2) + n²

≤ 4(c(n/2)² - d(n/2)) + n²

≤ 4(cn²/4 - dn/2) + n²

≤ cn² - 2dn + n²

≤ (c+1)n² - 2dn

We want to show that (c+1)n² - 2dn ≤ cn² - dn.

This simplifies to: n² - dn ≤ 0, which means n(n-d) ≤ 0. This is not true for large n.

Let's reconsider the original guess T(n) = cn² and the result T(n) ≤ (c+1)n². The issue arises because the additive term n² has the same order as the recursive part. The substitution method can be tricky when the additive term is of the same degree as the dominant term in the solution. However, the Master Theorem (Case 2) would suggest T(n) = Θ(n² log n) if the recurrence was T(n) = 4T(n/2) + n² log n. For T(n) = 4T(n/2) + n², Case 2 of the Master Theorem applies, giving T(n) = Θ(n²).

Let's try to prove T(n) ≤ cn² for a sufficiently large c. We need to handle the base case and ensure the inductive step holds.

Assume T(k) ≤ ck² for k < n. We want to show T(n) ≤ cn².

T(n) = 4T(n/2) + n²

≤ 4(c(n/2)²) + n²

≤ cn² + n²

This inequality T(n) ≤ (c+1)n² is true. To make it T(n) ≤ cn², we need to choose c such that c+1 ≤ c, which is impossible. This indicates that the simple guess T(n) = cn² is not sufficient on its own to close the induction tightly in the standard way. However, the form O(n²) is correct.

Let's try to prove T(n) ≤ cn² for a specific c and with an additive term in the assumption.

Assume T(k) ≤ ck² for k < n. We want to show T(n) ≤ cn².

T(n) = 4T(n/2) + n².

Let's try to prove T(n) ≤ cn² for some constant c.

We need to find a c such that T(n) ≤ cn² holds for all n.

Let's assume T(n) ≤ cn² for all n. We need to show that this holds for the recurrence.

T(n) = 4T(n/2) + n²

If T(n/2) ≤ c(n/2)², then

T(n) ≤ 4 * c(n/2)² + n²

T(n) ≤ 4 * c(n²/4) + n²

T(n) ≤ cn² + n²

T(n) ≤ (c+1)n²

For T(n) ≤ cn² to hold, we need (c+1)n² ≤ cn², which implies c+1 ≤ c, which is impossible. This means the simple O(n²) guess does not work directly for substitution to prove T(n) ≤ cn².

However, the Master Theorem (Case 2) states that for T(n) = aT(n/b) + f(n), if f(n) = Θ(n^log_ba), then T(n) = Θ(n^log_ba log n). Here a=4, b=2, log_ba = log₂4 = 2. So n^log_ba = n². Since f(n) = n² = Θ(n²), we are in Case 2, and T(n) = Θ(n² log n).

Let's re-evaluate the substitution method for T(n) = Θ(n² log n).

Let's guess T(n) = cn² log n. We need to prove T(n) ≤ cn² log n.

Assume T(k) ≤ ck² log k for k < n.

T(n) = 4T(n/2) + n²

≤ 4[c(n/2)² log(n/2)] + n²

≤ 4[c(n²/4) (log n - log 2)] + n²

≤ cn² (log n - 1) + n²

≤ cn² log n - cn² + n²

≤ cn² log n + n²(1 - c)

We want this to be ≤ cn² log n. This requires n²(1 - c) ≤ 0, which means 1 - c ≤ 0, or c ≥ 1.

So, if we choose c = 1, we get T(n) ≤ n² log n. This proves T(n) = O(n² log n).

Now, let's prove the lower bound T(n) = Ω(n² log n). We guess T(n) = cn² log n and try to prove T(n) ≥ cn² log n.

Assume T(k) ≥ ck² log k for k < n.

T(n) = 4T(n/2) + n²

≥ 4[c(n/2)² log(n/2)] + n²

≥ 4[c(n²/4) (log n - log 2)] + n²

≥ cn² (log n - 1) + n²

≥ cn² log n - cn² + n²

≥ cn² log n + n²(1 - c)

We want this to be ≥ cn² log n. This requires n²(1 - c) ≥ 0, which means 1 - c ≥ 0, or c ≤ 1.

So, if we choose c = 1, we get T(n) ≥ n² log n. This proves T(n) = Ω(n² log n).

Combining both, T(n) = Θ(n² log n).

Final Answer: The solution to the recurrence relation T(n) = 4T(n/2) + n² using the substitution method is T(n) = Θ(n² log n).

Dynamic Programming (DP) is an algorithmic technique for solving complex problems by breaking them down into simpler subproblems. It solves each subproblem only once and stores their solutions, typically in a table (memoization or tabulation), to avoid recomputing them. This approach is particularly effective for problems exhibiting overlapping subproblems and optimal substructure.

The applications of Dynamic Programming are vast and span various domains of computer science and beyond:

1. Optimization Problems:

• Shortest Path Problems: Algorithms like Floyd-Warshall and Bellman-Ford use DP to find the shortest paths between all pairs of vertices in a graph, or from a single source to all other vertices, especially in graphs with negative edge weights.
• Traveling Salesperson Problem (TSP): DP provides an exact solution for smaller instances of TSP, finding the shortest possible route that visits each city exactly once and returns to the origin city.
• Knapsack Problem: Determining the most valuable combination of items that can fit into a knapsack with a limited weight capacity. This includes the 0/1 Knapsack problem (each item can either be taken or not) and the Bounded Knapsack problem.
• Matrix Chain Multiplication: Finding the most efficient way to multiply a sequence of matrices by minimizing the total number of scalar multiplications required.
• Longest Increasing Subsequence (LIS): Finding the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
• Minimum Edit Distance: Calculating the minimum number of single-character edits (insertions, deletions, or substitutions) required to change one word into another (e.g., Levenshtein distance).

2. Combinatorial Problems:

• Counting Problems: Many problems involving counting the number of ways to achieve a certain outcome can be solved using DP. For example, counting the number of ways to make change for a given amount using a set of coins.
• Subset Sum Problem: Determining if there exists a subset of a given set of integers that sums up to a specific target value.
• Partition Problem: Determining if a set can be partitioned into two subsets such that the sum of elements in both subsets is equal.

3. String Algorithms:

• Longest Common Subsequence (LCS): Finding the longest subsequence common to two given sequences. This is fundamental in areas like DNA sequencing and file comparison.
• Palindrome Partitioning: Dividing a string into the minimum number of palindromic substrings.

4. Game Theory:

• Optimal Strategy Games: DP can be used to find optimal strategies in certain combinatorial games where players make sequential decisions.

5. Bioinformatics:

• Sequence Alignment: DP is crucial for aligning DNA, RNA, and protein sequences to identify similarities and evolutionary relationships.

6. Operations Research and Economics:

• Resource Allocation: Optimizing the allocation of limited resources to maximize profit or minimize cost.
• Inventory Management: Determining optimal inventory levels over time.

7. Computer Graphics and Image Processing:

• Pathfinding Algorithms: Used in some pathfinding algorithms for optimal routes in grids or terrains.

In essence, any problem that can be broken down into smaller, overlapping subproblems where the optimal solution to the overall problem can be constructed from the optimal solutions of its subproblems is a candidate for a Dynamic Programming solution.