Design and Analysis of Algorithms

Minimum Spanning Tree (MST): Given a connected, undirected, and weighted graph \(G = (V, E)\), a spanning tree is an acyclic subgraph that connects all the vertices in the graph. The Minimum Spanning Tree is a spanning tree whose sum of edge weights is minimized. Key properties of an MST include:

• It must contain all vertices of the original graph (\(V\)).
• It must have exactly \(|V| - 1\) edges.
• It must contain no cycles (acyclic).

Differences between Prim's and Kruskal's Algorithms:

Dynamic Programming (DP): An algorithmic paradigm that solves a complex problem by breaking it into overlapping subproblems, solving each subproblem exactly once, and storing their solutions (in a table) to avoid redundant computations. It is built on two primary principles:

1. Optimal Substructure: An optimal solution to the problem contains optimal solutions to its subproblems.
2. Overlapping Subproblems: The recursive algorithm solves the same subproblems repeatedly, rather than generating new ones.

Differences from the Greedy Method:

int fun(int n) {
    int count = 0;
    for (int i = n; i > 0; i /= 2) {
        for (int j = 0; j < i; j++) {
            count += 1;
        }
    }
    return count;
}

Mathematical Analysis:

• The outer loop initializes i = n and halves it in each iteration (i /= 2) until i <= 0. The sequence of values of i is: \(n, n/2, n/4, n/8, \dots, 1\).
• The inner loop runs exactly i times for each value of i in the outer loop (from j = 0 to j < i - 1).
• Therefore, the total number of operations (executions of the inner statement count += 1) is the sum of the inner loop counts across all iterations:
  \[\text{Total Iterations} = n + \frac{n}{2} + \frac{n}{4} + \frac{n}{8} + \dots + 1\]
• This is a geometric series with first term \(a = n\) and common ratio \(r = 1/2\). Using the infinite geometric series sum formula \(S = \frac{a}{1 - r}\):
  \[S \approx \frac{n}{1 - 1/2} = 2n\]

Asymptotic Notations represent the rates of growth of algorithms. Big-O and Omega notation serve as upper and lower bounds respectively.

Example (Insertion Sort):

• Worst-Case (Reverse Sorted Input): Insertion sort requires shifting elements at every position, yielding a quadratic running time. Thus, the worst-case time complexity is \(O(n^2)\).
• Best-Case (Already Sorted Input): Insertion sort only performs one comparison per element and no shifts, yielding a linear running time. Thus, the best-case complexity is \(\Omega(n)\).

Problems Solved by Dynamic Programming: DP is applicable to optimization problems that exhibit two critical properties:

1. Optimal Substructure: An optimal solution to the global problem can be constructed from the optimal solutions of its subproblems.
2. Overlapping Subproblems: The space of subproblems is small, meaning a recursive algorithm visits the same subproblems repeatedly, rather than generating new ones.

Common examples include: Matrix Chain Multiplication (MCM), Longest Common Subsequence (LCS), 0/1 Knapsack, Bellman-Ford (Single-source shortest path with negative edges), and Floyd-Warshall (All-pairs shortest path).

Can we solve All-Pairs Shortest Path (APSP) using Dijkstra's Algorithm?

Yes, we can solve APSP by running Dijkstra's algorithm \(|V|\) times, using each vertex as the source once. Let's analyze the properties of this approach:

• Complexity: If we implement Dijkstra using a Min-Heap/Priority Queue, the cost for a single run is \(O(E \log V)\). Running it \(V\) times results in a total complexity of \(O(V \cdot E \log V)\). For sparse graphs, this is \(O(V^2 \log V)\), which is highly efficient.
• Limitations: Dijkstra's algorithm cannot handle graphs with negative weight edges. If any negative edge weights exist, we must use the Floyd-Warshall algorithm (\(O(V^3)\)) or Johnson's Algorithm (\(O(V^2 \log V + VE)\)), which reweights edges to allow Dijkstra's to run safely.

Given matrices \(A_1(2 \times 3)\), \(A_2(3 \times 4)\), and \(A_3(4 \times 5)\), the dimensions array is \(P = [2, 3, 4, 5]\) with \(n = 3\) matrices. The cost recurrence relation is:

Step-by-Step DP Computation:

1. Chain Length 1 (Base Case):
   \(m[1, 1] = m[2, 2] = m[3, 3] = 0\) (No multiplication needed for a single matrix)
2. Chain Length 2:
   • \(m[1, 2]\) (Multiplying \(A_1 A_2\)): Only one split possible (\(k = 1\)):
     \(m[1, 2] = m[1, 1] + m[2, 2] + P[0] \cdot P[1] \cdot P[2] = 0 + 0 + 2 \times 3 \times 4 = 24\).
     Split record: \(s[1, 2] = 1\).
   • \(m[2, 3]\) (Multiplying \(A_2 A_3\)): Only one split possible (\(k = 2\)):
     \(m[2, 3] = m[2, 2] + m[3, 3] + P[1] \cdot P[2] \cdot P[3] = 0 + 0 + 3 \times 4 \times 5 = 60\).
     Split record: \(s[2, 3] = 2\).
3. Chain Length 3 (\(m[1, 3]\) - Multiplying \(A_1 A_2 A_3\)): We evaluate two possible splits:
   • Split at \(k = 1\) (\(A_1 \times (A_2 A_3)\)):
     \(cost = m[1, 1] + m[2, 3] + P[0] \cdot P[1] \cdot P[3] = 0 + 60 + 2 \times 3 \times 5 = 60 + 30 = 90\)
   • Split at \(k = 2\) (\((A_1 A_2) \times A_3\)):
     \(cost = m[1, 2] + m[3, 3] + P[0] \cdot P[2] \cdot P[3] = 24 + 0 + 2 \times 4 \times 5 = 24 + 40 = 64\)
   We take the minimum: \(\min(90, 64) = 64\) at split \(k = 2\).
   Split record: \(s[1, 3] = 2\).

The Ford-Fulkerson Algorithm computes the maximum possible flow in a flow network from a source node \(S\) to a sink node \(T\). It works by repeatedly finding "augmenting paths" in the "residual graph" and adding their bottleneck capacities to the total flow.

Ford-Fulkerson(Graph G, Node S, Node T):
    1. Initialize flow f(u, v) = 0 for all edges (u, v) in G
    2. Construct the residual graph G_f where:
       - Forward edge capacity: c_f(u, v) = c(u, v) - f(u, v)
       - Reverse edge capacity: c_f(v, u) = f(u, v)
       
    3. While there exists a path P from S to T in G_f such that c_f(u, v) > 0 for all (u, v) in P:
       a. Find the bottleneck capacity of the path:
          c_f(P) = min { c_f(u, v) : (u, v) is in P }
          
       b. Update flow along path P:
          For each edge (u, v) in P:
             If (u, v) is a forward edge in G:
                f(u, v) = f(u, v) + c_f(P)   // Augment flow
             Else:
                f(v, u) = f(v, u) - c_f(P)   // Decrease reverse flow (push back)
                
       c. Update the capacities in the residual graph G_f
       
    4. Return the maximum flow (sum of flow leaving source S)

Time Complexity Analysis:

• If augmenting paths are found using standard DFS, the runtime is \(O(E \cdot |f^*|)\), where \(|f^*|\) is the maximum flow value. This is pseudopolynomial since it depends on the capacities.
• If we find augmenting paths using BFS, the algorithm is called the Edmonds-Karp Algorithm, which guarantees a polynomial time complexity of \(O(V \cdot E^2)\).

The recurrence relation is \(T(n) = 2T(n/2) + n \log n\). We compare this with the standard Master's Theorem form:

Here, we identify:

• \(a = 2\) (number of subproblems)
• \(b = 2\) (subproblem division factor)
• \(f(n) = n \log n\)

Step 1: Compute \(n^{\log_b a}\)

\[n^{\log_b a} = n^{\log_2 2} = n^1 = n\]

Step 2: Compare \(f(n)\) with \(n^{\log_b a}\)

We notice that \(f(n) = n \log n\) grows faster than \(n\), but not by a polynomial factor. It matches the Extended Case 2 of the Master Theorem:

If \(f(n) = \Theta(n^{\log_b a} \log^k n)\) for some \(k \ge 0\):

• Here, \(n^{\log_b a} = n\), and \(f(n) = n \log^1 n\), which perfectly fits with \(k = 1\).

According to this case, the solution is:

\[T(n) = \Theta(n^{\log_b a} \log^{k+1} n)\]

Substituting the values:

\[T(n) = \Theta(n^1 \log^{1+1} n) = \Theta(n \log^2 n)\]

The Activity Selection Problem is a classic optimization problem. Given \(n\) activities with start times \(S[i]\) and finish times \(F[i]\), we want to find the size of the largest subset of mutually compatible activities (where no two selected activities overlap).

This is solved optimally using a Greedy Algorithm: we sort activities by finish times, then greedily pick the next compatible activity that finishes earliest.

Activity-Selection(Start[], Finish[], n):
    1. Sort the activities according to their finish times in ascending order.
       Assume the sorted activities are A_1, A_2, ..., A_n.
       
    2. Select the first activity A_1 (it has the earliest finish time).
       Print/Store A_1.
       
    3. Initialize last_selected_finish = Finish[1]
    
    4. For i = 2 to n:
       a. If Start[i] >= last_selected_finish:
          i. Activity A_i is compatible. Select it.
          ii. Update last_selected_finish = Finish[i]
          
    5. Return the list of selected activities.

Complexity Analysis:

• Sorting the activities takes \(O(n \log n)\) time.
• The single linear scan for selection takes \(O(n)\) time.
• Overall Time Complexity is \(O(n \log n)\).

Why this Greedy Strategy is Optimal: Picking the activity that finishes first leaves the maximum possible resource window open for subsequent activities, guaranteeing an optimal choice (Greedy Choice Property).

Differences between Dynamic Programming and Divide & Conquer:

Greedy Algorithm Definition:

A greedy algorithm is an algorithmic paradigm that builds a solution step-by-step, making the locally optimal choice at each stage in the hope that this choice will lead to a globally optimal solution. It is characterized by two key properties: Greedy Choice Property (a global optimum can be reached by making local choices) and Optimal Substructure. Once a greedy choice is made, it is never revised (no backtracking), making it fast but not universally applicable.

Backtracking: Backtracking is an algorithmic technique for solving constraint-satisfaction problems by searching a state-space tree incrementally. It builds candidate solutions step-by-step. As soon as it determines that a partial candidate cannot possibly be extended to a valid complete solution, it abandons it ("backtracks") to the previous decision point.

Relationship to Recursion: Backtracking is fundamentally implemented using recursion. The recursive function calls represent deeper levels of exploration in the state-space tree. The activation records on the call stack keep track of the path from the root node. When a dead-end is hit, returning from a recursive function call naturally cleans up local states and steps back up the tree, making backtracking highly clean to express recursively.

Differences between Backtracking and Branch & Bound:

Single Source Shortest Path (SSSP): Given a weighted graph \(G = (V, E)\) (directed or undirected) and a designated source vertex \(S \in V\), the SSSP problem is to find the path of minimum total weight from \(S\) to every other vertex \(v \in V\). The path weight is defined as the sum of all individual edge weights along that path.

When does the Shortest Path NOT exist?

A shortest path from a source vertex \(S\) to a destination vertex \(D\) is undefined/does not exist in the following conditions:

1. Disconnected Graph: If there is no reachable path in the graph from \(S\) to \(D\), the distance is defined as infinity (\(\infty\)).
2. Negative Weight Cycle: If the graph contains a cycle whose sum of edge weights is negative, and this cycle is reachable from \(S\) and can reach \(D\). In this scenario, we can loop around the negative cycle infinitely many times, reducing the total path weight to negative infinity (\(-\infty\)). Thus, no "shortest" path can exist because a path with a smaller weight can always be generated.

Characteristics of Greedy Algorithms:

• Greedy-Choice Property: A global optimal solution can be arrived at by making locally optimal (greedy) choices at each step.
• Optimal Substructure: An optimal solution to the problem contains optimal solutions to its subproblems.
• No Backtracking: Once a choice is made, it cannot be undone or adjusted.
• Efficiency: High efficiency, usually taking \(O(n)\) or \(O(n \log n)\) time.

Why Greedy Fails for the 0/1 Knapsack Problem:

In the 0/1 Knapsack, an item must be chosen in its entirety or left behind (no fractional items allowed). When we make choices greedily based on the highest profit-to-weight ratio, we might leave empty space in the knapsack that cannot be filled, making the total value suboptimal. A non-greedy combination of items with lower individual ratios might fill the knapsack capacity perfectly and yield a higher overall profit.

Example Counter-Example:

• Capacity = 10 kg
• Item A: Weight = 6 kg, Value = \$60 (Ratio = 10)
• Item B: Weight = 5 kg, Value = \$45 (Ratio = 9)
• Item C: Weight = 5 kg, Value = \$45 (Ratio = 9)

Greedy choice picks Item A first (highest ratio 10). Remaining capacity = 4 kg. Neither B nor C can fit. Total profit = \$60.

Optimal choice picks Item B and Item C. Total weight = 10 kg, Total profit = \$45 + \$45 = \$90. This proves greedy fails.

Quick Sort is based on the Divide and Conquer strategy. The time complexity depends heavily on how balanced the partitions are after selecting a pivot.

1. Best Case Analysis:

Occurs when the pivot selection always splits the array into two equal halves of size \(n/2\) at each level of recursion. The recurrence relation is:

\[T(n) = 2T(n/2) + \Theta(n)\]

Where \(\Theta(n)\) represents the partition time. Using the Master's Theorem:

• \(a = 2, b = 2, f(n) = \Theta(n)\)
• Compute \(n^{\log_b a} = n^{\log_2 2} = n^1 = n\)
• Since \(f(n) = \Theta(n^{\log_b a})\), this falls under Case 2 of Master's Theorem.
• Thus, \(T(n) = \Theta(n^{\log_b a} \log n) = \Theta(n \log n)\).

2. Worst Case Analysis:

Occurs when the pivot is always the smallest or largest element, splitting the array into partitions of size \(0\) and \(n-1\). This happens if the array is already sorted and we choose the first or last element as pivot. The recurrence relation is:

\[T(n) = T(n-1) + T(0) + c \cdot n = T(n-1) + c \cdot n\]

We solve this using the substitution method:

• \(T(n) = T(n-1) + cn\)
• \(T(n) = (T(n-2) + c(n-1)) + cn = T(n-2) + c(n + n-1)\)
• \(T(n) = T(n-k) + c \sum_{i=0}^{k-1} (n - i)\)
• For base case \(n-k = 1 \implies k = n-1\):
• \(T(n) = T(1) + c \sum_{i=2}^n i = T(1) + c \left[\frac{n(n+1)}{2} - 1\right]\)

Since the highest term is quadratic, the complexity is:

The Floyd-Warshall Algorithm is a dynamic programming algorithm that finds the shortest paths between all pairs of vertices in a weighted directed graph. It supports positive and negative edge weights, but must not contain negative cycles.

DP Formulation: Let \(d_{ij}^{(k)}\) be the weight of the shortest path from vertex \(i\) to vertex \(j\) using only vertices in the set \(\{1, 2, \dots, k\}\) as intermediate nodes. The recurrence relation is:

Algorithm Pseudocode:

Floyd-Warshall(Graph W, V):
    1. Let D^(0) be the initial V x V weight matrix where:
       D^(0)[i][j] = 0           if i == j
       D^(0)[i][j] = weight(i,j) if edge (i,j) exists
       D^(0)[i][j] = Infinity    if no edge exists
       
    2. For k = 1 to V:          // k represents the intermediate vertex
       For i = 1 to V:       // i is the source vertex
          For j = 1 to V:    // j is the destination vertex
             D^(k)[i][j] = min( D^(k-1)[i][j], D^(k-1)[i][k] + D^(k-1)[k][j] )
             
    3. Return D^(V)          // Contains all-pairs shortest path distances

Complexity Analysis:

• The algorithm contains three nested loops, each executing exactly \(V\) times.
• Inside the nested loops, only constant-time comparisons and additions are performed.
• Thus, the Time Complexity is \(\Theta(V^3)\).
• Space complexity is \(O(V^2)\) since we only need to maintain the current and previous distance tables.

We solve the Fractional Knapsack Problem using the Greedy Approach. We are given capacity \(M = 10\) kg and five items with weights \(W\) and profits \(P\).

Step 1: Calculate Profit-to-Weight ratios (\(P_i / W_i\))

• Item 1: \(P_1 = 10, W_1 = 3 \implies Ratio_1 = 10/3 \approx 3.33\)
• Item 2: \(P_2 = 15, W_2 = 3 \implies Ratio_2 = 15/3 = 5.00\)
• Item 3: \(P_3 = 10, W_3 = 2 \implies Ratio_3 = 10/2 = 5.00\)
• Item 4: \(P_4 = 12, W_4 = 5 \implies Ratio_4 = 12/5 = 2.40\)
• Item 5: \(P_5 = 8, W_5 = 1 \implies Ratio_5 = 8/1 = 8.00\)

Step 2: Sort items in descending order of ratios

Order: Item 5 (8.00) \(\to\) Item 2 (5.00) \(\to\) Item 3 (5.00) \(\to\) Item 1 (3.33) \(\to\) Item 4 (2.40).

Step 3: Greedily load the knapsack (Capacity limit = 10 kg)

A Randomized Algorithm is an algorithm that uses random numbers to influence its decision-making logic. Instead of executing deterministically based on the input, it leverages a random source to obtain average-case behavior on worst-case inputs.

Randomized algorithms are broadly classified into two main types:

1. Las Vegas Algorithms: These algorithms always produce the correct result, but their execution time is a random variable. The goal is to minimize the expected running time.
   Example: Randomized Quick Sort (choosing a random pivot avoids worst-case \(O(n^2)\) splits, guaranteeing expected \(O(n \log n)\) time).
2. Monte Carlo Algorithms: These algorithms have a deterministic execution time, but their outputs have a small, bounded probability of being incorrect. The accuracy probability can be improved by running the algorithm multiple times.
   Example: Miller-Rabin Primality Test (checks if a number is prime in polynomial time with a tiny error probability), or Karger's Min-Cut Algorithm.

Key Advantages: They are typically simpler, faster, and require less memory than their deterministic counterparts, making them essential for cryptography, load balancing, and large data processing.

Algorithm: An algorithm is a finite, step-by-step sequence of well-defined, unambiguous instructions designed to solve a specific problem or compute a particular output from a given set of inputs.

According to Donald Knuth, any valid algorithm must satisfy these five essential characteristics:

1. Input: It must accept zero or more quantities externally as input.
2. Output: It must produce at least one output quantity that has a specified relation to the inputs.
3. Definiteness (Unambiguity): Each step of the algorithm must be clear, precise, and unambiguous. There should be no doubt about what operation is to be performed.
4. Finiteness: The algorithm must terminate after a finite number of execution steps. It cannot run into an infinite loop.
5. Effectiveness: Every instruction must be basic enough to be carried out in practice, using simple pencil and paper in a finite amount of time.

Given matrices \(A_1(10 \times 20)\), \(A_2(20 \times 50)\), \(A_3(50 \times 1)\), and \(A_4(1 \times 100)\). The dimensions array is \(P = [10, 20, 50, 1, 100]\) for \(n = 4\) matrices. The recurrence relation is:

DP Calculation Table:

1. Chain Length 1:
   \(m[1, 1] = m[2, 2] = m[3, 3] = m[4, 4] = 0\)
2. Chain Length 2:
   • \(m[1, 2] = 10 \times 20 \times 50 = 10,000\) (Split \(s[1,2] = 1\))
   • \(m[2, 3] = 20 \times 50 \times 1 = 1,000\) (Split \(s[2,3] = 2\))
   • \(m[3, 4] = 50 \times 1 \times 100 = 5,000\) (Split \(s[3,4] = 3\))
3. Chain Length 3:
   • \(m[1, 3]\) (Multiplying \(A B C\)): Possible splits:
     • \(k = 1\): \(m[1, 1] + m[2, 3] + P[0] \cdot P[1] \cdot P[3] = 0 + 1000 + 10 \times 20 \times 1 = 1200\)
     • \(k = 2\): \(m[1, 2] + m[3, 3] + P[0] \cdot P[2] \cdot P[3] = 10000 + 0 + 10 \times 50 \times 1 = 10500\)
     Minimum is 1,200 at split \(s[1, 3] = 1\).
   • \(m[2, 4]\) (Multiplying \(B C D\)): Possible splits:
     • \(k = 2\): \(m[2, 2] + m[3, 4] + P[1] \cdot P[2] \cdot P[4] = 0 + 5000 + 20 \times 50 \times 100 = 105,000\)
     • \(k = 3\): \(m[2, 3] + m[4, 4] + P[1] \cdot P[3] \cdot P[4] = 1000 + 0 + 20 \times 1 \times 100 = 3,000\)
     Minimum is 3,000 at split \(s[2, 4] = 3\).
4. Chain Length 4 (\(m[1, 4]\) - Multiplying \(A B C D\)): Possible splits:
   • \(k = 1\): \(m[1, 1] + m[2, 4] + P[0] \cdot P[1] \cdot P[4] = 0 + 3000 + 10 \times 20 \times 100 = 23,000\)
   • \(k = 2\): \(m[1, 2] + m[3, 4] + P[0] \cdot P[2] \cdot P[4] = 10000 + 5000 + 10 \times 50 \times 100 = 65,000\)
   • \(k = 3\): \(m[1, 3] + m[4, 4] + P[0] \cdot P[3] \cdot P[4] = 1200 + 0 + 10 \times 1 \times 100 = 2,200\)
   Minimum is 2,200 at split \(s[1, 4] = 3\).

The Bellman-Ford Algorithm solves the Single Source Shortest Path problem in graphs containing negative edge weights. It runs in \(O(V \cdot E)\) time. It relaxes all edges \(|V| - 1\) times and runs a final check to detect negative-weight cycles.

Bellman-Ford(Graph G, Source S):
    1. Initialize distances:
       For each vertex v in G:
          dist[v] = Infinity
       dist[S] = 0
       
    2. Relax all edges |V| - 1 times:
       For i = 1 to |V| - 1:
          For each edge (u, v) in G with weight w:
             If dist[u] != Infinity and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                
    3. Detect negative weight cycles:
       For each edge (u, v) in G with weight w:
          If dist[u] != Infinity and dist[u] + w < dist[v]:
             Return "Graph contains a negative weight cycle!"
             
    4. Return dist

Why \(|V| - 1\) iterations? The shortest path between any two vertices in a graph without negative cycles contains at most \(|V| - 1\) edges. Thus, relaxing all edges \(|V| - 1\) times guarantees that the shortest paths propagate throughout the graph.

Dynamic Programming (DP) is a robust paradigm, but it comes with distinct trade-offs.

Advantages:

• Optimality: Unlike greedy methods, DP evaluates all possible combinations systematically, guaranteeing a globally optimal solution.
• Avoids Redundant Calculations: Drastically reduces time complexities (e.g., from exponential \(O(2^n)\) to polynomial \(O(n^2)\) or \(O(n)\)) by storing subproblem answers so they are never solved twice.
• Standard Abstractions: Provides structured math formulas (recurrences) that are easy to analyze and verify.

Drawbacks:

• High Space Complexity: Storing subproblem solutions in tables requires significant memory, which can be prohibitive for multi-dimensional DP state spaces.
• Complexity in Design: Determining states, choices, and mapping transitions requires creative math skills, which is much harder than coding greedy or simple recursive solutions.
• Strict Requirements: Only works if the problem satisfies the strict conditions of Overlapping Subproblems and Optimal Substructure.

Graph Edges: \(S \to a (1)\), \(S \to b (5)\), \(a \to c (2)\), \(a \to d (3)\), \(b \to c (2)\), \(b \to d (1)\), \(c \to e (3)\), \(d \to e (2)\), \(c \to d (5)\).

Step-by-Step Execution Trace:

Complexity theory classifies decision problems based on the computational resources needed to solve or verify them.

This statement is a fundamental theorem of complexity theory. Let's prove it logically:

1. By definition, a problem \(L\) is NP-Complete if:
   • \(L \in NP\), and
   • For every problem \(X \in NP\), there exists a polynomial-time reduction to \(L\) (written as \(X \le_p L\)).
2. A polynomial-time reduction (\(X \le_p L\)) means we can transform any instance of \(X\) into an instance of \(L\) using a deterministic machine in \(O(n^k)\) time.
3. If we can solve \(L\) itself in polynomial time (say, in \(O(n^m)\) time), then to solve any problem \(X \in NP\), we can:
   a. Convert \(X\) to \(L\) in polynomial time.
   b. Solve the resulting instance of \(L\) in polynomial time.
4. The combined execution time is the composition of two polynomial functions, which is also polynomial. Therefore, every problem \(X \in NP\) would be solvable in polynomial time, which means \(NP \subseteq P\).
5. Since \(P \subseteq NP\) by definition, this implies \(P = NP\).

Reducibility is a formal method of transforming one problem into another. If a problem \(A\) is reducible to a problem \(B\), it means that any algorithm that solves problem \(B\) can also be used as a subroutine to solve problem \(A\).

Formally, in complexity theory, we use Polynomial-time Reduction (denoted as \(A \le_p B\)). This states that there exists a polynomial-time computable function \(f\) such that for every input instance \(x\):

Implications of Reducibility:

• It establishes a relative difficulty: If \(A \le_p B\), then \(B\) is at least as hard as \(A\).
• If we have an efficient (polynomial time) algorithm to solve \(B\), we automatically obtain an efficient algorithm to solve \(A\).
• It is the primary tool used to prove NP-Completeness (by reducing a known NP-Complete problem like 3-SAT to a target problem).

The code is: int fun2(int n) { if (n<=1) return n; return fun2(n-1) + fun2(n-1); }

Step 1: Formulate the Recurrence Relation

• For the base case where \(n \le 1\), the code runs in constant time. So, \(T(1) = \Theta(1)\).
• For \(n > 1\), the function makes two independent recursive calls of size \(n - 1\), plus a constant time addition and return step.

Step 2: Solve the Recurrence Relation (Expansion Method)

• \(T(n) = 2T(n-1) + c\)
• \(T(n) = 2 [2T(n-2) + c] + c = 2^2 T(n-2) + 2c + c\)
• \(T(n) = 2^2 [2T(n-3) + c] + 3c = 2^3 T(n-3) + 4c + 2c + c\)
• Generalizing this after \(k\) steps: \[T(n) = 2^k T(n-k) + c \sum_{i=0}^{k-1} 2^i\] \[T(n) = 2^k T(n-k) + c(2^k - 1)\]
• The base case is reached when \(n-k = 1 \implies k = n-1\): \[T(n) = 2^{n-1} T(1) + c(2^{n-1} - 1)\]

The recurrence relation is \(T(n) = 2T(n/2) + n\), with base case \(T(1) = c\).

We solve this using the Substitution (Expansion) Method:

1. Write the general form: \[T(n) = 2T(n/2) + n \quad \text{--- (Eq 1)}\]
2. Substitute \(T(n/2)\) by applying Eq 1 to \(n/2\): \[T(n/2) = 2T(n/4) + n/2\] Substitute this back into Eq 1: \[T(n) = 2 \left[ 2T(n/4) + n/2 \right] + n = 2^2 T(n/2^2) + 2n \quad \text{--- (Eq 2)}\]
3. Substitute \(T(n/4)\): \[T(n/4) = 2T(n/8) + n/4\] Substitute into Eq 2: \[T(n) = 2^2 \left[ 2T(n/8) + n/4 \right] + 2n = 2^3 T(n/2^3) + 3n \quad \text{--- (Eq 3)}\]
4. Generalizing this to \(k\) steps: \[T(n) = 2^k T(n/2^k) + k \cdot n\]
5. The base case is reached when the subproblem size is 1: \[n/2^k = 1 \implies n = 2^k \implies k = \log_2 n\]
6. Substitute \(k = \log_2 n\) and \(2^k = n\) back into our generalized equation: \[T(n) = n T(1) + (\log_2 n) \cdot n\] \[T(n) = c \cdot n + n \log_2 n\]

The Fractional Knapsack Algorithm uses a greedy approach. Items can be broken down to fit the capacity, so we greedily select items with the highest value-to-weight ratio first.

Fractional-Knapsack(Weights[], Profits[], Capacity, n):
    1. Create an array of structures or indices: Item_Ratios[]
    
    2. For i = 0 to n-1:
       Item_Ratios[i].index = i
       Item_Ratios[i].ratio = Profits[i] / Weights[i]
       
    3. Sort Item_Ratios[] in descending order of ratio values.
    
    4. Initialize:
       total_profit = 0.0
       current_capacity = Capacity
       
    5. For i = 0 to n-1:
       item_idx = Item_Ratios[i].index
       
       If Weights[item_idx] <= current_capacity:
          // Take the entire item
          current_capacity = current_capacity - Weights[item_idx]
          total_profit = total_profit + Profits[item_idx]
       Else:
          // Take a fraction of the item to fill the remaining capacity
          fraction = current_capacity / Weights[item_idx]
          total_profit = total_profit + (Profits[item_idx] * fraction)
          current_capacity = 0
          Break // Knapsack is full
          
    6. Return total_profit

Complexity: Sorting takes \(O(n \log n)\), and the selection loop takes \(O(n)\). Total time complexity is \(O(n \log n)\).

N-Queens Problem: The problem of placing \(N\) non-attacking queens on an \(N \times N\) chessboard, such that no two queens share the same row, column, or diagonal. It is solved using Backtracking by placing queens row by row and backtracking whenever a placement conflict is detected.

15-Puzzle Problem: A sliding puzzle consisting of a grid of numbered square tiles in random order with one tile missing. The grid size is \(4 \times 4\) (15 tiles, 1 empty space). The goal is to rearrange the tiles from an initial configuration to a target sorted configuration by sliding tiles into the empty space. It is solved using Branch and Bound (using heuristics like Manhattan distance in a Best-First search).

Comparison Table:

Given weights \(W = \{3, 5, 3, 4\}\), profits \(P = \{11, 7, 5, 10\}\), and capacity \(M = 15\) kg.

Step 1: Check the total weight of all items

\[\text{Total Weight} = W_1 + W_2 + W_3 + W_4 = 3 + 5 + 3 + 4 = 15 \text{ kg}\]

Step 2: Compare with Capacity

The total weight of all available items is exactly equal to the knapsack capacity (\(15 \le 15\)). Therefore, we do not need to leave any item behind. We can select all four items to achieve the maximum possible profit.

Step 3: Calculate Total Profit

\[\text{Total Profit} = P_1 + P_2 + P_3 + P_4 = 11 + 7 + 5 + 10 = 33\]

i) No, a valid shortest path cannot be determined. If a graph contains a negative weight cycle (a cycle whose sum of edge weights is less than 0) that is reachable from the source and can reach the destination, we can loop through this cycle indefinitely. Each loop decreases the total path cost. As a result, the distance between the source and destination approaches negative infinity (\(-\infty\)), making the concept of a "shortest" path mathematically undefined.

ii) The Bellman-Ford Algorithm can detect the presence of negative weight cycles. It does this by running an extra relaxation step. After relaxing all edges \(|V| - 1\) times, the algorithm attempts to relax all edges one more time (the \(|V|\)-th iteration). If any distance value updates (decreases) during this step, it indicates that a negative weight cycle exists in the graph.

To prove that the Clique Decision Problem is NP-Complete, we must complete two steps:

Step 1: Prove Clique is in NP

• A problem is in NP if a candidate solution (certificate) can be verified by a deterministic machine in polynomial time.
• Certificate: A subset of vertices \(V' \subseteq V\) of size \(k\).
• Verification Algorithm: For every pair of vertices \(u, v \in V'\), check if there is an edge \((u, v) \in E\).
• Complexity: There are \(\binom{k}{2} \approx k^2\) pairs to check. Since \(k \le V\), this takes \(O(V^2)\) time, which is polynomial. Thus, Clique is in NP.

Step 2: Prove Clique is NP-Hard (Reduction from 3-SAT)

• We reduce the 3-SAT problem (which is known to be NP-complete) to Clique in polynomial time.
• Given a 3-SAT formula with \(k\) clauses, e.g., \(\phi = C_1 \land C_2 \land \dots \land C_k\), where each clause \(C_i\) has three literals.
• Graph Construction:
  • For each clause \(C_i\), create three vertices in graph \(G\), one for each literal in the clause.
  • Draw an edge between two vertices \(u\) and \(v\) if and only if:
    1. They belong to different clauses.
    2. They are not negations of each other (i.e., we don't connect \(x\) and \(\neg x\)).
• Equivalence Proof:
  • If \(\phi\) is satisfiable, there is a truth assignment that makes at least one literal in each clause TRUE. Selecting one TRUE literal from each of the \(k\) clauses yields a set of \(k\) vertices in \(G\). Since they are in different clauses and do not contradict each other, they are all connected by edges, forming a \(k\)-clique.
  • Conversely, if \(G\) has a \(k\)-clique, the \(k\) vertices must belong to different clauses and cannot contain negations. We can assign truth values to make these literals TRUE, satisfying the 3-SAT formula.
• The graph construction takes polynomial time, completing the proof that Clique is NP-Complete.

Given capacity \(M = 5\) kg and 4 items with weights \(W = \{2, 1, 3, 2\}\) and profits \(P = \{12, 10, 20, 15\}\).

The DP relation is: \(K[i][w] = \max(K[i-1][w], P[i] + K[i-1][w - W[i]])\) if \(W[i] \le w\), else \(K[i-1][w]\).

Step 1: Construct the DP Table

Step 2: Trace Back to Find Selected Items

• \(K[4][5] = 37 \ne K[3][5] (32) \implies\) Select Item 4 (Weight 2, Profit 15). Remaining Capacity = \(5 - 2 = 3\) kg.
• \(K[3][3] = 22 = K[2][3] (22) \implies\) Do NOT select Item 3. Remaining Capacity = 3 kg.
• \(K[2][3] = 22 \ne K[1][3] (12) \implies\) Select Item 2 (Weight 1, Profit 10). Remaining Capacity = \(3 - 1 = 2\) kg.
• \(K[1][2] = 12 \ne K[0][2] (0) \implies\) Select Item 1 (Weight 2, Profit 12). Remaining Capacity = \(2 - 2 = 0\) kg.

Given matrices \(A_1(2 \times 3), A_2(3 \times 4), A_3(4 \times 5), A_4(5 \times 2)\). The dimensions array is \(P = [2, 3, 4, 5, 2]\) with \(n = 4\) matrices. Recurrence: \(m[i, j] = \min \{m[i, k] + m[k+1, j] + P[i-1] \cdot P[k] \cdot P[j]\}\).

Step-by-Step DP Calculations:

1. Chain Length 1 (Base Case): \(m[i, i] = 0\) for all \(i\).
2. Chain Length 2:
   • \(m[1, 2] = 2 \times 3 \times 4 = 24\) (Split at \(k = 1\))
   • \(m[2, 3] = 3 \times 4 \times 5 = 60\) (Split at \(k = 2\))
   • \(m[3, 4] = 4 \times 5 \times 2 = 40\) (Split at \(k = 3\))
3. Chain Length 3:
   • \(m[1, 3]\) (Multiplying \(A_1 A_2 A_3\)):
     - Split at \(k = 1\): \(m[1, 1] + m[2, 3] + 2 \times 3 \times 5 = 0 + 60 + 30 = 90\)
     - Split at \(k = 2\): \(m[1, 2] + m[3, 3] + 2 \times 4 \times 5 = 24 + 0 + 40 = 64\)
     Minimum is 64 at \(k = 2\). Split record: \(s[1, 3] = 2\).
   • \(m[2, 4]\) (Multiplying \(A_2 A_3 A_4\)):
     - Split at \(k = 2\): \(m[2, 2] + m[3, 4] + 3 \times 4 \times 2 = 0 + 40 + 24 = 64\)
     - Split at \(k = 3\): \(m[2, 3] + m[4, 4] + 3 \times 5 \times 2 = 60 + 0 + 30 = 90\)
     Minimum is 64 at \(k = 2\). Split record: \(s[2, 4] = 2\).
4. Chain Length 4 (\(m[1, 4]\) - Multiplying \(A_1 A_2 A_3 A_4\)):
   • Split at \(k = 1\): \(m[1, 1] + m[2, 4] + P[0] \cdot P[1] \cdot P[4] = 0 + 64 + 2 \times 3 \times 2 = 76\)
   • Split at \(k = 2\): \(m[1, 2] + m[3, 4] + P[0] \cdot P[2] \cdot P[4] = 24 + 40 + 2 \times 4 \times 2 = 80\)
   • Split at \(k = 3\): \(m[1, 3] + m[4, 4] + P[0] \cdot P[3] \cdot P[4] = 64 + 0 + 2 \times 5 \times 2 = 84\)
   Minimum is 76 at split \(k = 1\). Split record: \(s[1, 4] = 1\).

The Matrix Chain Order algorithm computes the minimum multiplication costs and stores the split points in an auxiliary table \(s\) to construct the optimal parenthesization.

Matrix-Chain-Order(p):
    1. n = length(p) - 1
    2. Create tables m[1..n, 1..n] and s[1..n-1, 2..n]
    
    3. For i = 1 to n:
       m[i, i] = 0 // Base case: cost is 0 for single matrix
       
    4. For L = 2 to n: // L is the chain length
       For i = 1 to n - L + 1:
          j = i + L - 1
          m[i, j] = Infinity
          For k = i to j - 1:
             q = m[i, k] + m[k+1, j] + p[i-1]*p[k]*p[j]
             If q < m[i, j]:
                m[i, j] = q
                s[i, j] = k // Store split index
                
    5. Return m and s

Complexity Analysis: The three nested loops run in \(O(n^3)\) time complexity. The space complexity is \(O(n^2)\) to store the \(m\) and \(s\) matrices.

Circuit Satisfiability (Circuit-SAT) Problem: Given a combinatorial boolean circuit containing input wires, logic gates (AND, OR, NOT), and a single output wire, the problem is to determine if there exists an assignment of truth values to the inputs that makes the final output wire TRUE (1).

Proof that Circuit-SAT is in NP:

1. A problem is in NP if a candidate solution (certificate) can be verified by a deterministic machine in polynomial time.
2. Certificate: The certificate is a specific assignment of truth values (0 or 1) to each of the \(n\) input wires of the circuit.
3. Verification Algorithm:
   • Given the input values, evaluate the output of each logic gate layer-by-layer.
   • The gates are evaluated in topological order from inputs to outputs.
   • At each step, we compute the boolean output of a gate based on its inputs (which is a constant time operation).
4. Complexity: If the circuit contains \(G\) gates and \(W\) wires, the evaluation takes \(O(G + W)\) time. Since the size of the circuit description is \(O(G + W)\), the verification runs in linear (polynomial) time with respect to the input size.
5. Therefore, Circuit-SAT is in NP.

The state-space tree shows the step-by-step placement of queens in rows 1, 2, 3, and 4. Backtracking prunes paths immediately when a conflict occurs. Below is the detailed tree, where \(Q(r, c)\) represents a queen placed at row \(r\), column \(c\), and (X) denotes pruning due to conflicts.

                               Root (Start)
          /                     |                     \                   \
      Q(1,1)                  Q(1,2)                 Q(1,3)              Q(1,4)
      /    \                 /      \                /    \              /     \
   Q(2,3)  Q(2,4)         Q(2,4)   Q(2,1)-(X)     Q(2,1)  Q(2,2)-(X)  Q(2,1)  Q(2,2)-(X)
   /   \     /           /    \                   /    \              /    \
Q(3,X) Q(3,2)          Q(3,1) Q(3,3)-(X)       Q(3,4) Q(3,2)-(X)   Q(3,3) Q(3,X)
(X)      /              /                        /                   /
      Q(4,X)         Q(4,3)                   Q(4,2)              Q(4,X)
       (X)     [SOLUTION 1: 2-4-1-3]    [SOLUTION 2: 3-1-4-2]      (X)
                Col placements:          Col placements:
                Row 1 -> Col 2           Row 1 -> Col 3
                Row 2 -> Col 4           Row 2 -> Col 1
                Row 3 -> Col 1           Row 3 -> Col 4
                Row 4 -> Col 3           Row 4 -> Col 2
                

This state-space tree visualizes how backtracking searches depth-first and prunes subtrees to arrive at the two valid solutions for the 4-Queens problem.

We solve this using the Greedy Activity Selection method.

Step 1: Sort activities by finish times (ascending order)

1. Act1: Start = 1, Finish = 3
2. Act2: Start = 2, Finish = 4
3. Act3: Start = 0, Finish = 5
4. Act4: Start = 6, Finish = 7
5. Act5: Start = 8, Finish = 9
6. Act6: Start = 6, Finish = 10

The input activities are already sorted by finish times.

Step 2: Greedily pick compatible activities

• Pick Act1 (1, 3): First activity, always selected. Current finish time boundary = 3.
• Evaluate Act2 (2, 4): Start time (2) is less than boundary (3). Reject (overlaps).
• Evaluate Act3 (0, 5): Start time (0) is less than boundary (3). Reject (overlaps).
• Evaluate Act4 (6, 7): Start time (6) \(\ge\) boundary (3). Select Act4. Update finish boundary = 7.
• Evaluate Act5 (8, 9): Start time (8) \(\ge\) boundary (7). Select Act5. Update finish boundary = 9.
• Evaluate Act6 (6, 10): Start time (6) is less than boundary (9). Reject (overlaps).

We solve the All-Pairs Shortest Path problem using the Floyd-Warshall Algorithm.

Step 1: Construct Initial Distance Matrix \(D^{(0)}\)

\[D^{(0)} = \begin{pmatrix} 0 & -5 & 2 & \infty \\ \infty & 0 & 4 & \infty \\ \infty & \infty & 0 & 1 \\ 3 & 2 & \infty & 0 \end{pmatrix}\]

Step 2: Compute \(D^{(1)}\) (Intermediate vertex \(k = 0\))

We check if we can shorten paths using node 0: \(D^{(1)}[i][j] = \min(D^{(0)}[i][j], D^{(0)}[i][0] + D^{(0)}[0][j])\).

• \(D^{(1)}[3][1] = \min(2, D^{(0)}[3][0] + D^{(0)}[0][1]) = \min(2, 3 + (-5)) = -2\)
• \(D^{(1)}[3][2] = \min(\infty, D^{(0)}[3][0] + D^{(0)}[0][2]) = \min(\infty, 3 + 2) = 5\)

\[D^{(1)} = \begin{pmatrix} 0 & -5 & 2 & \infty \\ \infty & 0 & 4 & \infty \\ \infty & \infty & 0 & 1 \\ 3 & -2 & 5 & 0 \end{pmatrix}\]

Step 3: Compute \(D^{(2)}\) (Intermediate vertex \(k = 1\))

Check paths via node 1: \(D^{(2)}[i][j] = \min(D^{(1)}[i][j], D^{(1)}[i][1] + D^{(1)}[1][j])\).

• \(D^{(2)}[0][2] = \min(2, D^{(1)}[0][1] + D^{(1)}[1][2]) = \min(2, -5 + 4) = -1\)
• \(D^{(2)}[3][2] = \min(5, D^{(1)}[3][1] + D^{(1)}[1][2]) = \min(5, -2 + 4) = 2\)

\[D^{(2)} = \begin{pmatrix} 0 & -5 & -1 & \infty \\ \infty & 0 & 4 & \infty \\ \infty & \infty & 0 & 1 \\ 3 & -2 & 2 & 0 \end{pmatrix}\]

Step 4: Compute \(D^{(3)}\) (Intermediate vertex \(k = 2\))

Check paths via node 2: \(D^{(3)}[i][j] = \min(D^{(2)}[i][j], D^{(2)}[i][2] + D^{(2)}[2][j])\).

• \(D^{(3)}[0][3] = \min(\infty, D^{(2)}[0][2] + D^{(2)}[2][3]) = \min(\infty, -1 + 1) = 0\)
• \(D^{(3)}[1][3] = \min(\infty, D^{(2)}[1][2] + D^{(2)}[2][3]) = \min(\infty, 4 + 1) = 5\)

\[D^{(3)} = \begin{pmatrix} 0 & -5 & -1 & 0 \\ \infty & 0 & 4 & 5 \\ \infty & \infty & 0 & 1 \\ 3 & -2 & 2 & 0 \end{pmatrix}\]

Step 5: Compute \(D^{(4)}\) (Intermediate vertex \(k = 3\))

Check paths via node 3: \(D^{(4)}[i][j] = \min(D^{(3)}[i][j], D^{(3)}[i][3] + D^{(3)}[3][j])\).

• \(D^{(4)}[1][0] = \min(\infty, D^{(3)}[1][3] + D^{(3)}[3][0]) = \min(\infty, 5 + 3) = 8\)
• \(D^{(4)}[2][0] = \min(\infty, D^{(3)}[2][3] + D^{(3)}[3][0]) = \min(\infty, 1 + 3) = 4\)
• \(D^{(4)}[2][1] = \min(\infty, D^{(3)}[2][3] + D^{(3)}[3][1]) = \min(\infty, 1 + (-2)) = -1\)

\[D^{(4)} = \begin{pmatrix} 0 & -5 & -1 & 0 \\ 8 & 0 & 4 & 5 \\ 4 & -1 & 0 & 1 \\ 3 & -2 & 2 & 0 \end{pmatrix}\]

All values on the main diagonal are 0, verifying that there are no negative weight cycles. This is the final shortest paths matrix.