{"pinia":{"ui":{"prefs":{"theme":"system","textScale":"md","fontFamily":"sans","reducedMotion":false,"highContrast":false}},"academy":{"universities":[],"universitySummaries":[{"slug":"rtu","name":"RTU","fullName":"Rajasthan Technical University","branches":[{"slug":"first-year-common","name":"First Year (Common)"},{"slug":"computer-science","name":"Computer Science"},{"slug":"mechanical","name":"Mechanical"},{"slug":"civil","name":"Civil"},{"slug":"ai-data-science","name":"AI & Data Science"},{"slug":"ee-ec-eee","name":"EE / EC / EEE"}]},{"slug":"aktu","name":"AKTU","fullName":"Dr. A. P. J. Abdul Kalam Technical University","branches":[{"slug":"first-year-common","name":"First Year (Common)"},{"slug":"computer-science","name":"Computer Science"}]}],"activePapers":[{"id":"design-and-analysis-of-algorithms-2023","title":"Design and Analysis of Algorithms (2023)","subjectSlug":"design-and-analysis-of-algorithms","subjectName":"Design and Analysis of Algorithms","universitySlug":"rtu","branchSlug":"computer-science","year":3,"semester":5,"examYear":2023,"paperCode":"5E1755","questions":[{"id":"v2-design-and-analysis-of-algorithms-2023-pA-q1","number":1,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"Define Algorithm."}],"answer":{"summary":"An Algorithm is a strictly defined, finite sequence of computational instructions designed to solve a specific problem.","explanation":[{"type":"paragraph","content":"In theoretical computer science, an Algorithm is a highly rigorous, unambiguous, and finite sequence of mathematical or logical instructions engineered to completely resolve a specific computational problem, guaranteeing termination and producing a physically correct output from a given input."}]}},{"id":"v2-design-and-analysis-of-algorithms-2023-pA-q2","number":2,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"What is Time Complexity?"}],"answer":{"summary":"Time Complexity mathematically quantifies the total CPU execution time an algorithm requires based on the input size.","explanation":[{"type":"paragraph","content":"Time Complexity is the absolute mathematical quantification of the total physical amount of time (or CPU clock cycles) an algorithm requires to execute to completion, rigorously expressed as a function of the length of the input string ($n$), completely independent of physical hardware speed."}]}},{"id":"v2-design-and-analysis-of-algorithms-2023-pA-q3","number":3,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"Define Asymptotic Notation."}],"answer":{"summary":"Asymptotic Notation provides a mathematical abstraction to describe the limiting behavior of an algorithm's time complexity.","explanation":[{"type":"paragraph","content":"Asymptotic Notation is a rigorous mathematical framework utilized to definitively categorize and describe the limiting, worst-case, best-case, or average-case scaling behavior of an algorithm's time or space complexity exactly as the input size ($n$) violently approaches infinity."}]}},{"id":"v2-design-and-analysis-of-algorithms-2023-pA-q4","number":4,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"What is a Greedy Algorithm?"}],"answer":{"summary":"A Greedy Algorithm aggressively makes the mathematically optimal choice at every local step to find a global optimum.","explanation":[{"type":"paragraph","content":"The Greedy Algorithm architecture is a heuristic paradigm that aggressively makes the absolute most optimal, mathematically beneficial choice at every single localized stage of execution, without ever backtracking, in the theoretical hope that these local optimums will coalesce into the global maximum solution."}]}},{"id":"v2-design-and-analysis-of-algorithms-2023-pA-q5","number":5,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"Define Dynamic Programming."}],"answer":{"summary":"Dynamic Programming breaks complex problems into overlapping subproblems, aggressively storing and reusing their calculated solutions to prevent redundant CPU cycles.","explanation":[{"type":"paragraph","content":"Dynamic Programming (DP) is a highly optimized algorithmic technique designed for solving complex mathematical optimization problems by violently shattering them into simpler, overlapping subproblems. It utilizes \"Memoization\" or \"Tabulation\" to permanently store the physical result of each subproblem, completely eradicating catastrophic redundant CPU calculations."}]}},{"id":"v2-design-and-analysis-of-algorithms-2023-pA-q6","number":6,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"What is the Divide and Conquer technique?"}],"answer":{"summary":"Divide and Conquer aggressively splits a problem into independent subproblems, solves them recursively, and merges the results.","explanation":[{"type":"paragraph","content":"Divide and Conquer is a fundamental, highly recursive algorithmic architecture. It rigorously mathematically divides a massive problem into several completely independent, smaller subproblems, violently solves those subproblems recursively, and then mechanically merges their localized solutions to mathematically synthesize the absolute final global solution."}]}},{"id":"v2-design-and-analysis-of-algorithms-2023-pA-q7","number":7,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"Define NP-Hard."}],"answer":{"summary":"NP-Hard problems are mathematically the absolute hardest computational problems, to which all NP problems can be reduced.","explanation":[{"type":"paragraph","content":"In computational complexity theory, NP-Hard defines an exclusive class of problems that are mathematically at least as hard as the absolute hardest problems in the entire NP class. If a deterministic polynomial-time algorithm is ever found for any single NP-Hard problem, then $P$ violently equals $NP$."}]}},{"id":"v2-design-and-analysis-of-algorithms-2023-pA-q8","number":8,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"What is Backtracking?"}],"answer":{"summary":"Backtracking is a recursive depth-first search strategy that violently prunes dead-end mathematical paths to optimize execution.","explanation":[{"type":"paragraph","content":"Backtracking is a highly aggressive, optimized Depth-First Search algorithmic architecture utilized for Constraint Satisfaction Problems. It incrementally builds candidates to the solutions, but the exact millisecond it mathematically proves a candidate path will fail, it violently abandons (\"backtracks\") it, saving massive computational overhead."}]}},{"id":"v2-design-and-analysis-of-algorithms-2023-pA-q9","number":9,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"Define Minimum Spanning Tree."}],"answer":{"summary":"A Minimum Spanning Tree is a mathematically derived subgraph connecting all vertices of a graph with absolute minimum total edge weight.","explanation":[{"type":"paragraph","content":"In graph theory, a Minimum Spanning Tree (MST) is a strictly derived, acyclic subset of the edges of a connected, edge-weighted undirected graph that physically connects every single vertex together without any cycles, while mathematically guaranteeing that the total sum of all edge weights is minimized."}]}},{"id":"v2-design-and-analysis-of-algorithms-2023-pA-q10","number":10,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"What is the Knapsack Problem?"}],"answer":{"summary":"The Knapsack Problem is a classic mathematical optimization challenge focused on maximizing total value without exceeding a strict weight capacity.","explanation":[{"type":"paragraph","content":"The Knapsack Problem is an absolute foundational challenge in combinatorial optimization. Given a strict, finite set of items—each possessing a specific mathematical weight and a defined financial value—the algorithm must aggressively determine the absolute optimal subset of items to include in a collection so that the total weight is less than a strict limit, while violently maximizing the total value."}]}},{"id":"v2-design-and-analysis-of-algorithms-2023-pB-q1","number":1,"marks":4,"tags":["Part B"],"text":[{"type":"paragraph","content":"Explain the different asymptotic notations (Big-O, Omega, Theta) with examples."}],"answer":{"summary":"A rigorous mathematical exploration of the three foundational Asymptotic Notations: Big-O (Worst-case), Omega (Best-case), and Theta (Average/Tight-bound), detailing their strict algebraic definitions.","explanation":[{"type":"heading","content":"Asymptotic Notations in Computational Complexity"},{"type":"paragraph","content":"In the rigorous discipline of algorithm analysis, predicting the exact CPU execution time is mathematically impossible due to fluctuating hardware architectures. Instead, computer scientists rely strictly on Asymptotic Notation. This mathematical framework aggressively abstracts away machine constants to purely evaluate how the algorithm's execution time scales as the input size ($n$) violently approaches infinity. The three absolute primary notations are Big-O ($O$), Big-Omega ($\\Omega$), and Big-Theta ($\\Theta$)."},{"type":"subheading","content":"1. Big-O Notation ($O$): The Worst-Case Absolute Ceiling"},{"type":"paragraph","content":"Big-O notation mathematically defines the strict upper bound of an algorithm's execution time. It guarantees that the algorithm will absolutely never take longer than this function, identifying the most catastrophic \"Worst-Case\" scenario."},{"type":"list","items":["**Mathematical Definition:** $f(n) = O(g(n))$ if and only if there exist positive constants $c$ and $n_0$ such that $0 \\le f(n) \\le c \\cdot g(n)$ for all $n \\ge n_0$.","**Example:** In a naive linear search algorithm probing an array of size $n$, if the target element is physically located at the very last index (or is entirely missing), the algorithm is violently forced to check every single element. Thus, the worst-case time complexity is rigorously $O(n)$."]},{"type":"subheading","content":"2. Big-Omega Notation ($\\Omega$): The Best-Case Absolute Floor"},{"type":"paragraph","content":"Big-Omega notation mathematically defines the strict lower bound of an algorithm's execution time. It guarantees that the algorithm will absolutely never execute faster than this function, identifying the highly optimistic \"Best-Case\" scenario."},{"type":"list","items":["**Mathematical Definition:** $f(n) = \\Omega(g(n))$ if and only if there exist positive constants $c$ and $n_0$ such that $0 \\le c \\cdot g(n) \\le f(n)$ for all $n \\ge n_0$.","**Example:** In the exact same linear search algorithm, if the target element happens to physically be the very first element in the array at index 0, the algorithm instantly halts after 1 operation. Thus, the best-case time complexity is aggressively $\\Omega(1)$."]},{"type":"subheading","content":"3. Big-Theta Notation ($\\Theta$): The Average/Tight Bound"},{"type":"paragraph","content":"Big-Theta notation is the holy grail of algorithmic analysis. It mathematically defines an exact, \"Tight\" bound, meaning the algorithm is aggressively trapped both from above and below by the exact same mathematical function (ignoring constants)."},{"type":"list","items":["**Mathematical Definition:** $f(n) = \\Theta(g(n))$ if and only if there exist positive constants $c_1, c_2,$ and $n_0$ such that $0 \\le c_1 \\cdot g(n) \\le f(n) \\le c_2 \\cdot g(n)$ for all $n \\ge n_0$.","**Example:** The Merge Sort algorithm violently shatters and rebuilds the array structure using exactly the same mathematical operations regardless of whether the array is pre-sorted or reverse-sorted. Therefore, its time complexity is tightly bound in every single scenario as strictly $\\Theta(n \\log n)$."]}]}},{"id":"v2-design-and-analysis-of-algorithms-2023-pB-q2","number":2,"marks":4,"tags":["Part B"],"text":[{"type":"paragraph","content":"Describe the Binary Search algorithm and analyze its time complexity."}],"answer":{"summary":"A technical deconstruction of the Binary Search algorithm, utilizing the Divide and Conquer paradigm on strictly sorted arrays, followed by a rigorous logarithmic time complexity analysis.","explanation":[{"type":"heading","content":"Binary Search: Architecture and Logarithmic Analysis"},{"type":"paragraph","content":"Binary Search is a highly advanced, fiercely optimized search algorithm that fundamentally utilizes the Divide and Conquer architectural paradigm. Unlike primitive linear searches that mindlessly scan every element, Binary Search mathematically exploits a strict physical pre-condition: the target array *must* be absolutely and perfectly sorted in ascending or descending order. By leveraging this sorted state, it aggressively halves the searchable data space during every single CPU iteration."},{"type":"subheading","content":"The Algorithmic Execution"},{"type":"paragraph","content":"The algorithm strictly maintains two physical pointers: `Low` (initial index 0) and `High` (initial index $n-1$)."},{"type":"list","items":["**1. Midpoint Calculation:** It mathematically calculates the absolute center index of the current active search space: `Mid = (Low + High) / 2` (utilizing integer floor division).","**2. The Triage:** It aggressively compares the Target Value against the element physically residing at `Array[Mid]`.","**3. The Halving Phase:**\n - If `Target == Array[Mid]`, the search instantly terminates with total success.\n - If `Target < Array[Mid]`, the mathematical logic dictates the target *must* physically reside in the left half. It violently discards the entire right half by updating `High = Mid - 1`.\n - If `Target > Array[Mid]`, it violently discards the entire left half by updating `Low = Mid + 1`.","**4. Recursion/Loop:** The algorithm ruthlessly repeats this sequence until the Target is located or the `Low` pointer mathematically crosses the `High` pointer (indicating absolute failure)."]},{"type":"subheading","content":"Rigorous Time Complexity Analysis"},{"type":"paragraph","content":"To calculate the absolute Worst-Case Time Complexity $O(f(n))$, we must analyze the mathematical rate of array destruction. In the worst-case scenario (the element is missing), the array of size $n$ is continuously divided by 2."},{"type":"list","items":["Iteration 1: Array size is $n / 2^0$","Iteration 2: Array size is $n / 2^1$","Iteration 3: Array size is $n / 2^2$","Iteration $k$: Array size is $n / 2^k$"]},{"type":"paragraph","content":"The algorithm halts precisely when the array size collapses to exactly 1 element. Therefore, we set the equation: $\\frac{n}{2^k} = 1$."},{"type":"paragraph","content":"Mathematically solving for $k$ (the total number of iterations): \n$n = 2^k$\n$\\log_2(n) = \\log_2(2^k)$\n$k = \\log_2(n)$."},{"type":"paragraph","content":"Thus, the absolute worst-case time complexity is rigidly proven to be $O(\\log n)$, making it exponentially superior to $O(n)$ linear searches for massive databases."}]}},{"id":"v2-design-and-analysis-of-algorithms-2023-pB-q3","number":3,"marks":4,"tags":["Part B"],"text":[{"type":"paragraph","content":"Explain the Merge Sort algorithm with an example and analyze its time complexity."}],"answer":{"summary":"A detailed exploration of the Merge Sort algorithm, highlighting its strict Divide and Conquer mechanics, the physical merging of sub-arrays, and the mathematical derivation yielding $O(n \\log n)$ time complexity.","explanation":[{"type":"heading","content":"Merge Sort Architecture and Mathematical Analysis"},{"type":"paragraph","content":"Merge Sort is a highly stable, comparison-based sorting algorithm engineered strictly around the Divide and Conquer architectural paradigm. It is completely immune to worst-case data degradation (unlike Quick Sort), guaranteeing absolute mathematical consistency across all datasets."},{"type":"subheading","content":"The Algorithmic Mechanics"},{"type":"paragraph","content":"Merge Sort executes through two fiercely independent phases: the Recursive Division phase and the Linear Merging phase."},{"type":"list","items":["**1. The Divide Phase:** The algorithm aggressively calculates the mathematical midpoint of the array and physically shatters the array into two distinct sub-arrays. It then violently recursively calls itself on these sub-arrays until the entire data structure is completely atomized into $n$ separate arrays, each containing exactly 1 element. (A 1-element array is mathematically considered sorted by definition).","**2. The Conquer (Merge) Phase:** The algorithm begins aggressively stitching the atomized arrays back together. It takes two sorted sub-arrays, utilizes two strict tracking pointers, and mathematically compares their lowest elements, pushing the absolute smallest element into a new, contiguous physical memory buffer. This merge process scales back up the recursive tree until a single, flawlessly sorted array of size $n$ is synthesized."]},{"type":"subheading","content":"Execution Example"},{"type":"paragraph","content":"Consider the array: `[38, 27, 43, 3]`\n- **Divide:** Shatter into `[38, 27]` and `[43, 3]`.\n- **Divide:** Shatter into `[38]`, `[27]`, `[43]`, `[3]`.\n- **Merge:** Stitch `[38]` and `[27]` into `[27, 38]`. Stitch `[43]` and `[3]` into `[3, 43]`.\n- **Final Merge:** Compare pointers between `[27, 38]` and `[3, 43]`. Output: `[3, 27, 38, 43]`."},{"type":"subheading","content":"Rigorous Time Complexity Analysis"},{"type":"paragraph","content":"The time complexity is derived utilizing a strict mathematical Recurrence Relation. The total time $T(n)$ to sort $n$ elements equals the time to recursively sort the two halves $2 T(n/2)$, plus the physical time required to execute the linear merge operation over $n$ elements, which takes $O(n)$ time."},{"type":"paragraph","content":"Recurrence Equation: $T(n) = 2T\\left(\\frac{n}{2}\\right) + O(n)$"},{"type":"paragraph","content":"Using the advanced Master Theorem to solve this relation:\n- $a = 2$, $b = 2$, $f(n) = O(n^1)$\n- Calculate $n^{\\log_b a} = n^{\\log_2 2} = n^1 = O(n)$\nBecause $f(n)$ is mathematically equal to $n^{\\log_b a}$, we are strictly in Case 2 of the Master Theorem. We aggressively multiply by $\\log n$."},{"type":"paragraph","content":"Therefore, the absolute Tight-Bound Time Complexity is flawlessly proven to be $\\Theta(n \\log n)$ for all best, average, and worst-case scenarios. However, this comes at the severe architectural cost of $O(n)$ physical Space Complexity due to the required auxiliary merge buffer."}]}},{"id":"v2-design-and-analysis-of-algorithms-2023-pB-q4","number":4,"marks":4,"tags":["Part B"],"text":[{"type":"paragraph","content":"Discuss Kruskal's Algorithm for finding Minimum Spanning Tree."}],"answer":{"summary":"An architectural breakdown of Kruskal's Algorithm utilizing the Greedy paradigm and the highly optimized Disjoint-Set (Union-Find) data structure to mathematically construct a Minimum Spanning Tree.","explanation":[{"type":"heading","content":"Kruskal's Algorithm for Minimum Spanning Trees"},{"type":"paragraph","content":"Kruskal's Algorithm is a highly aggressive, classic implementation of the Greedy Algorithmic paradigm. Its singular mathematical objective is to calculate the absolute Minimum Spanning Tree (MST) of a connected, undirected graph with heavily weighted edges. The MST mathematically connects every single node in the graph together without ever forming a cycle, while strictly minimizing the total sum of all edge weights. Unlike Prim's algorithm which grows a single continuous tree, Kruskal's algorithm treats the graph as a massive \"forest\" of isolated nodes and aggressively stitches them together."},{"type":"subheading","content":"The Algorithmic State Machine"},{"type":"paragraph","content":"Kruskal's execution relies heavily on the advanced **Disjoint-Set (Union-Find)** data structure to execute extremely fast cycle detection."},{"type":"list","items":["**1. Absolute Sorting:** The algorithm begins by violently ripping all edges out of the graph architecture and sorting them in strict mathematically ascending order based on their physical weight. (This step takes $O(E \\log E)$ time, where $E$ is the number of edges).","**2. Initialization:** Every single node in the graph is initialized as its own isolated mathematical set (a forest of $V$ trees, where $V$ is the number of vertices).","**3. The Greedy Selection Loop:** The algorithm aggressively iterates through the sorted edge list, starting with the absolute lightest edge.","**4. The Union-Find Cycle Check:** For the selected edge connecting `Node U` and `Node V`, the algorithm queries the Disjoint-Set structure using the `Find()` operation. \n- If `Find(U) == Find(V)`, it means both nodes are already mathematically connected in the same set. Adding this edge would violently cause a fatal cycle. The edge is ruthlessly rejected and discarded.\n- If `Find(U) != Find(V)`, no cycle will form. The algorithm safely adds the edge to the final MST and aggressively executes the `Union(U, V)` operation, merging the two isolated sets into a single massive tree.","**5. Termination:** The algorithm terminates the exact millisecond the MST successfully contains exactly $(V - 1)$ edges, as mathematically required for a spanning tree."]},{"type":"subheading","content":"Time Complexity Analysis"},{"type":"paragraph","content":"The dominant operation is the initial edge sorting, which dictates an absolute time complexity of $O(E \\log E)$ or $O(E \\log V)$. The `Union` and `Find` operations, when utilizing advanced Path Compression and Union-by-Rank heuristics, execute in near-constant time $O(\\alpha(V))$ (where $\\alpha$ is the Inverse Ackermann function), making the cycle detection mathematically negligible."}]}},{"id":"v2-design-and-analysis-of-algorithms-2023-pB-q5","number":5,"marks":4,"tags":["Part B"],"text":[{"type":"paragraph","content":"Explain the concept of Dynamic Programming with the Fibonacci example."}],"answer":{"summary":"A definitive explanation of Dynamic Programming (DP), showcasing how Tabulation and Memoization completely eradicate the catastrophic exponential time complexity of naive recursive Fibonacci calculations.","explanation":[{"type":"heading","content":"Dynamic Programming: Eradicating Redundant Calculations"},{"type":"paragraph","content":"Dynamic Programming (DP) is arguably the most powerful mathematical optimization technique in algorithmic engineering. It is specifically designed to completely annihilate the catastrophic CPU waste found in naive recursive algorithms. DP strictly applies to optimization problems that exhibit two absolute mathematical properties:"},{"type":"list","items":["**1. Overlapping Subproblems:** The problem can be violently shattered into smaller problems, but crucially, these smaller problems are evaluated repeatedly (the identical mathematical calculation is executed thousands of times).","**2. Optimal Substructure:** The absolute optimal global solution to the massive problem can be perfectly mathematically constructed from the optimal solutions of its subproblems."]},{"type":"subheading","content":"The Fibonacci Crisis (Naive Recursion)"},{"type":"paragraph","content":"The mathematical Fibonacci sequence is defined as $F(n) = F(n-1) + F(n-2)$. A naive recursive algorithm directly translates this equation into code.\n- To calculate $F(5)$, the CPU must calculate $F(4)$ and $F(3)$.\n- But to calculate $F(4)$, it must calculate $F(3)$ and $F(2)$.\nNotice that the exact same mathematical function $F(3)$ is calculated completely independently multiple times. For massive inputs like $F(50)$, the CPU executes trillions of redundant operations, resulting in a catastrophic Exponential Time Complexity of $O(2^n)$."},{"type":"subheading","content":"The Dynamic Programming Solution"},{"type":"paragraph","content":"DP solves this violently utilizing two architectural techniques to store the answers to subproblems so they are never calculated twice."},{"type":"list","items":["**Top-Down (Memoization):** We keep the recursive architecture, but we aggressively inject a memory array (a Cache). When the CPU calculates $F(3)$ for the absolute first time, it stores the result in `Cache[3]`. The next time the recursive tree asks for $F(3)$, the algorithm intercepts the call, completely halts the recursion, and instantly returns the value from `Cache[3]` in $O(1)$ time.","**Bottom-Up (Tabulation):** We violently abandon recursion entirely. We build a simple physical array `DP[]` of size $N$. We manually initialize the base cases `DP[0] = 0` and `DP[1] = 1`. Then, we utilize a highly efficient `for` loop to linearly iterate from 2 to $N$, calculating `DP[i] = DP[i-1] + DP[i-2]`. This completely avoids the massive memory overhead of the recursive call stack."]},{"type":"paragraph","content":"By utilizing Dynamic Programming, the catastrophic $O(2^n)$ time complexity of Fibonacci is violently crushed down to a blisteringly fast Linear Time Complexity of $O(n)$."}]}},{"id":"v2-design-and-analysis-of-algorithms-2023-pB-q6","number":6,"marks":4,"tags":["Part B"],"text":[{"type":"paragraph","content":"Describe the N-Queens problem using Backtracking."}],"answer":{"summary":"A technical exploration of the N-Queens problem, detailing how the Backtracking algorithm utilizes a Depth-First Search tree and aggressive mathematical pruning to locate safe configurations.","explanation":[{"type":"heading","content":"Solving N-Queens via Aggressive Backtracking"},{"type":"paragraph","content":"The N-Queens problem is a highly complex, classic constraint satisfaction challenge in computer science. The mathematical objective is to physically place exactly $N$ chess queens on an $N \\times N$ grid (chessboard) such that absolutely no two queens can violently attack each other. According to the strict rules of chess, this means no two queens can share the exact same row, the exact same column, or any exact diagonal vector. Because the physical state-space explodes exponentially as $N$ increases, naive brute-force generation is computationally catastrophic. This requires the deployment of an optimized **Backtracking** architecture."},{"type":"subheading","content":"The Backtracking Architecture"},{"type":"paragraph","content":"Backtracking is fundamentally an aggressively optimized Depth-First Search (DFS) executed on a conceptual State-Space Tree. It incrementally builds the solution vector step-by-step."},{"type":"list","items":["**1. Iterative Placement:** The algorithm aggressively attempts to place exactly one queen in the first column (starting at row 0). It then physically locks that position and recursively dives deeper into the tree, attempting to place the second queen in the second column.","**2. The Mathematical Safety Check (The Pruning Engine):** Before the algorithm physically commits a queen to a cell $(row, col)$, it executes a rigorous safety function. It mathematically scans the current row, the upper-left diagonal, and the lower-left diagonal to guarantee no previously placed queen threatens this exact cell.","**3. The Backtracking Trigger:** If the safety check fails for every single row in the current column, the algorithm hits a fatal mathematical dead-end. It realizes the current configuration is completely doomed. Instead of blindly continuing, it violently \"Backtracks.\" It physically retreats to the previous column, rips the previously placed queen off the board, and attempts to place her in the next available safe row.","**4. Absolute Termination:** The algorithm terminates with absolute success the exact millisecond all $N$ queens are safely placed (i.e., it successfully reaches column $N+1$). If it completely exhausts all configurations in the first column and fails, it mathematically proves no solution exists."]},{"type":"paragraph","content":"By violently pruning branches of the State-Space Tree that mathematically cannot yield a solution, Backtracking bypasses billions of useless CPU cycles, acting as the definitive algorithm for combinatorial puzzles."}]}},{"id":"v2-design-and-analysis-of-algorithms-2023-pB-q7","number":7,"marks":4,"tags":["Part B"],"text":[{"type":"paragraph","content":"Explain the concept of P and NP complexity classes."}],"answer":{"summary":"A rigorous theoretical classification of Computational Complexity, defining the mathematical distinction between P (Polynomial time) and NP (Nondeterministic Polynomial time) problem classes.","explanation":[{"type":"heading","content":"The Architecture of P and NP Complexity Classes"},{"type":"paragraph","content":"In theoretical computational complexity, algorithms are not just analyzed by their speed, but problems themselves are mathematically classified into massive, distinct domains based on the absolute theoretical limits of computer architecture. The two foundational classes that dominate computer science are **P** and **NP**. This classification dictates what is mathematically possible to compute before the heat death of the universe."},{"type":"subheading","content":"The Class P (Polynomial Time)"},{"type":"paragraph","content":"The class P contains all computational decision problems that can be both mathematically solved AND physically verified by a standard, Deterministic Turing Machine (a normal CPU) in Polynomial Time. \n- **Mathematical Definition:** The execution time is strictly bounded by $O(n^k)$, where $n$ is the input size and $k$ is a constant.\n- **Significance:** These are the \"easy\" problems. They scale gracefully. If a dataset doubles in size, the execution time increases by a manageable, predictable mathematical factor.\n- **Examples:** Sorting arrays (Merge Sort $O(n \\log n)$), searching graphs (BFS $O(V+E)$), finding shortest paths (Dijkstra's algorithm)."},{"type":"subheading","content":"The Class NP (Nondeterministic Polynomial Time)"},{"type":"paragraph","content":"The class NP is significantly more abstract. It contains all decision problems for which, if a theoretical solution (a \"certificate\") is magically provided, a normal CPU can mathematically VERIFY that the solution is correct in absolute Polynomial Time. However, actually *finding* that solution from scratch might take catastrophic Exponential Time ($O(2^n)$) on a normal computer."},{"type":"list","items":["**The Nondeterministic Machine:** The \"N\" in NP stands for Nondeterministic. Theoretically, a Nondeterministic Turing Machine (a hyper-advanced conceptual computer that can guess perfectly or run infinite parallel timelines) could mathematically *solve* an NP problem in polynomial time.","**The Verification Clause:** Consider the Sudoku puzzle. Solving a massive $1000 \\times 1000$ Sudoku puzzle from scratch is mathematically brutal (NP). But if someone hands you a completed board, you can verify if the rules were followed in incredibly fast polynomial time (P).","**Examples:** The Traveling Salesperson Problem, Boolean Satisfiability (SAT), the Knapsack Problem."]},{"type":"paragraph","content":"The absolute greatest unsolved mathematical crisis in human history is the question: **Does P = NP?** If they are equal, it means every single problem whose answer is easy to check is also easy to solve, which would completely obliterate global cryptography."}]}},{"id":"v2-design-and-analysis-of-algorithms-2023-pC-q1","number":1,"marks":10,"tags":["Part C"],"text":[{"type":"paragraph","content":"(a) Explain the methods of solving recurrence relations: Substitution Method, Recursion Tree Method, and Master Theorem."},{"type":"paragraph","content":"(b) Solve T(n) = 2T(n/2) + n using the Master Theorem."}],"answer":{"summary":"An exhaustive mathematical exposition on solving Recurrence Relations, detailing the aggressive algebraic guessing of the Substitution Method, the geometric visualization of the Recursion Tree, and the absolute formulaic dominance of the Master Theorem.","explanation":[{"type":"heading","content":"Mathematical Methods for Solving Recurrence Relations"},{"type":"paragraph","content":"When engineering highly advanced Divide and Conquer algorithms (like Merge Sort or Quick Sort), the time complexity cannot be calculated using standard linear analysis. Because the algorithm continuously calls itself, its execution time is mathematically expressed as a Recurrence Relation—an equation that recursively defines a mathematical sequence where the next term is a function of previous terms (e.g., $T(n) = 2T(n/2) + O(n)$). To convert this recursive equation into a strict, absolute asymptotic bound (like $O(n \\log n)$), computer scientists utilize three highly rigorous mathematical frameworks: The Substitution Method, the Recursion Tree Method, and the Master Theorem."},{"type":"subheading","content":"1. The Substitution Method (The Algebraic Approach)"},{"type":"paragraph","content":"The Substitution Method is a two-phase, highly aggressive algebraic proof strategy heavily reliant on human intuition and mathematical induction."},{"type":"list","items":["**Phase 1 (The Guess):** The engineer mathematically analyzes the structure of the recurrence relation and makes an educated, theoretical guess regarding the final absolute time complexity boundary. For example, given $T(n) = 2T(n/2) + n$, the engineer might guess that the solution is tightly bound by $T(n) = O(n \\log n)$.","**Phase 2 (Mathematical Induction):** The engineer must now violently prove this guess is absolutely correct using formal mathematical induction. They must prove that $T(n) \\le c cdot n \\log n$ for a specific constant $c > 0$. They substitute the guessed bounds back into the original recursive equation and aggressively execute algebraic simplification to prove that the inequality holds true for all $n$ beyond a certain base case. If the algebra fails, the guess was catastrophic, and the engineer must restart."]},{"type":"subheading","content":"2. The Recursion Tree Method (The Geometric Approach)"},{"type":"paragraph","content":"When guessing the bound is mathematically impossible, the Recursion Tree provides a highly visual, geometric mechanism to derive a tight bound by mapping out the exact physical execution structure of the algorithm."},{"type":"list","items":["**The Construction:** The recursive equation is violently drawn out as a physical tree structure. Each node in the tree explicitly represents the CPU cost of the non-recursive part of the algorithm (the \"Merge\" step) at that specific depth.","**The Derivation:** For $T(n) = 2T(n/2) + n$, the absolute root node has a cost of $n$. It mathematically branches into two child nodes, each costing $n/2$. Those branch into four nodes, each costing $n/4$.","**The Summation:** The engineer calculates the total mathematical cost of each horizontal level of the tree (e.g., level 1 is $n$, level 2 is $n/2 + n/2 = n$). They then mathematically calculate the absolute maximum depth of the tree (which is $\\log_2 n$). Finally, they execute a massive mathematical summation, multiplying the cost per level by the total depth (e.g., $n \\cdot \\log_2 n$), yielding the final asymptotic time complexity."]},{"type":"subheading","content":"3. The Master Theorem (The Formulaic Approach)"},{"type":"paragraph","content":"The Master Theorem is the absolute most powerful and rapid architectural tool for solving standard Divide and Conquer recurrences. It completely bypasses complex algebra and tree drawing, providing a direct mathematical formula for equations strictly in the form: \n$$ T(n) = aT(n/b) + f(n) $$ \nWhere $a \\ge 1$ (number of subproblems), $b > 1$ (factor by which input shrinks), and $f(n)$ is the cost of dividing/merging."},{"type":"paragraph","content":"The engineer strictly compares the execution cost of the recursive leaves $O(n^{\\log_b a})$ against the cost of the division/merge phase $f(n)$. The theorem rigidly forces the result into one of three absolute mathematical cases:"},{"type":"list","items":["**Case 1 (Leaves Dominate):** If $f(n)$ is polynomially physically smaller than $n^{\\log_b a}$, then the massive bulk of CPU time is spent at the absolute bottom of the tree. The final complexity is strictly $\\Theta(n^{\\log_b a})$.","**Case 2 (Perfect Balance):** If $f(n)$ is exactly mathematically equal to $n^{\\log_b a}$, the CPU time is perfectly distributed across all levels. The final complexity is strictly $\\Theta(n^{\\log_b a} \\log n)$.","**Case 3 (Root Dominates):** If $f(n)$ is polynomially physically larger than $n^{\\log_b a}$ (and satisfies the regularity condition), the vast majority of CPU time is spent at the absolute root of the tree doing the merge. The final complexity is strictly $\\Theta(f(n))$."]}]}},{"id":"v2-design-and-analysis-of-algorithms-2023-pC-q2","number":2,"marks":10,"tags":["Part C"],"text":[{"type":"paragraph","content":"(a) Explain the Quick Sort algorithm in detail with a suitable example."},{"type":"paragraph","content":"(b) Analyze the best case, average case, and worst case time complexity of Quick Sort."}],"answer":{"summary":"A definitive architectural and mathematical breakdown of the Quick Sort algorithm, detailing its highly aggressive pivot partitioning mechanics, in-place memory optimization, and a rigorous analysis of its catastrophic $O(n^2)$ worst-case degradation.","explanation":[{"type":"heading","content":"The Architecture of the Quick Sort Algorithm"},{"type":"paragraph","content":"Quick Sort, engineered by Tony Hoare in 1959, is fundamentally the most deployed, highly aggressive, and practical comparison-based sorting algorithm in modern computer science (forming the backbone of standard libraries in C, C++, and Java). Like Merge Sort, it rigidly utilizes the Divide and Conquer architectural paradigm. However, it operates in the exact mathematical reverse. While Merge Sort does all its heavy lifting during the bottom-up \"Merge\" phase, Quick Sort executes all its massive mathematical processing during the top-down \"Divide\" phase (known as Partitioning). Furthermore, it is an \"In-Place\" algorithm, meaning it aggressively modifies the original array directly, completely annihilating the massive $O(n)$ RAM overhead required by Merge Sort buffers."},{"type":"subheading","content":"The Algorithmic Execution and Partitioning Engine"},{"type":"paragraph","content":"The absolute core of Quick Sort is the highly complex Partitioning function. Its singular objective is to select a specific element and violently move it to its exact, mathematically correct final position in the array."},{"type":"list","items":["**1. Pivot Selection:** The algorithm selects a single element from the array to act as the \"Pivot.\" (This can be the first element, the last element, a random element, or the median-of-three. The choice of pivot mathematically dictates the entire speed of the algorithm).","**2. The Violent Partitioning (Lomuto or Hoare Scheme):** Two pointers aggressively scan the array from opposite ends. The algorithm violently swaps elements to ensure a strict mathematical condition is met: EVERY single element physically located to the left of the Pivot must be mathematically less than or equal to the Pivot, and EVERY single element physically located to the right must be strictly greater than the Pivot.","**3. The Recursive Divide:** Once the Pivot is locked into its absolute final physical position, the array is shattered into two independent sub-arrays (the left side and the right side). The algorithm recursively calls itself on these two sub-arrays."]},{"type":"subheading","content":"Concrete Computational Example"},{"type":"paragraph","content":"Let us sort the array: `[10, 80, 30, 90, 40, 50, 70]` (Choosing the last element, 70, as the Pivot)."},{"type":"list","items":["**Initial State:** Pivot = 70. The scanning pointer aggressively checks elements from left to right against 70.","10 < 70 (Keep left). 80 > 70 (Must go right). 30 < 70 (Keep left). 90 > 70 (Must go right). 40 < 70 (Keep left). 50 < 70 (Keep left).","**The Swaps:** The algorithm physically swaps the large elements with the small elements to enforce the partition rule. The array transforms into: `[10, 30, 40, 50, 70, 90, 80]`.","**Result:** The Pivot (70) is now locked perfectly in the middle. The left sub-array `[10, 30, 40, 50]` and right sub-array `[90, 80]` are now fiercely independent and will be recursively Quick Sorted."]},{"type":"subheading","content":"Rigorous Time Complexity and The Worst-Case Catastrophe"},{"type":"paragraph","content":"Quick Sort's mathematical execution time is completely dependent on how evenly the Pivot shatters the array."},{"type":"list","items":["**Best and Average Case:** If the chosen Pivot consistently happens to be the exact mathematical median of the array, the array is shattered into two perfectly equal halves every single time. The recurrence relation is $T(n) = 2T(n/2) + O(n)$, yielding a highly optimized, blisteringly fast time complexity of $\\Theta(n \\log n)$.","**The Worst-Case Degradation:** If the array is already perfectly sorted (or reverse sorted) and the algorithm naively picks the last element as the Pivot, the Pivot will always be the largest element. The array will fail to split in half. It will violently shatter into one sub-array of size $n-1$ and another of size $0$. The recurrence collapses to $T(n) = T(n-1) + O(n)$. This causes a catastrophic, algorithmic meltdown, resulting in a devastating Time Complexity of $O(n^2)$, functioning no better than a primitive Bubble Sort."]}]}},{"id":"v2-design-and-analysis-of-algorithms-2023-pC-q3","number":3,"marks":10,"tags":["Part C"],"text":[{"type":"paragraph","content":"(a) Explain Dijkstra's Algorithm for Single Source Shortest Path with a suitable example."},{"type":"paragraph","content":"(b) Explain the Bellman-Ford Algorithm and compare it with Dijkstra's Algorithm."}],"answer":{"summary":"A highly advanced mathematical breakdown of Dijkstra's Algorithm, detailing its aggressive Greedy methodology, physical reliance on Priority Queues (Min-Heaps), and edge relaxation to calculate the absolute Single Source Shortest Path.","explanation":[{"type":"heading","content":"Dijkstra's Algorithm: Single Source Shortest Path"},{"type":"paragraph","content":"Engineered by Edsger W. Dijkstra in 1956, this algorithm is an absolute masterpiece of the Greedy Algorithmic paradigm. Its singular mathematical objective is to calculate the absolute shortest physical path (minimum total edge weight) from one specific starting node (the Source) to every single other node in a heavily weighted, directed, or undirected graph. It is the foundational architecture operating behind modern GPS navigation systems and OSPF network routing protocols. However, it possesses one fatal mathematical limitation: it will catastrophically fail and enter infinite loops if the graph contains edges with negative mathematical weights (which requires the slower Bellman-Ford architecture to resolve)."},{"type":"subheading","content":"The Algorithmic State Machine and Data Structures"},{"type":"paragraph","content":"To achieve extreme execution speed, Dijkstra's Algorithm heavily utilizes an advanced **Priority Queue** (specifically implemented as a Min-Heap) and a `Distance Array`."},{"type":"list","items":["**1. Absolute Initialization:** The algorithm violently creates a `Distance Array` to track the shortest known distance to every node. The Source node is mathematically initialized to `0` (distance to itself is zero). Every other single node in the entire graph is violently initialized to mathematical Infinity ($\\infty$). All nodes are aggressively pushed into the Priority Queue.","**2. The Greedy Extraction:** The algorithm enters a massive loop. It commands the Priority Queue to instantly extract the node possessing the absolute minimum distance value. (In the first iteration, this is guaranteed to be the Source node at `0`). This extracted node is now permanently locked and marked as \"Visited.\" Its calculated shortest path is now mathematically absolute and cannot be improved.","**3. The Edge Relaxation Engine:** The algorithm aggressively scans every single neighboring node connected to the extracted node. For a neighboring `Node V` connected to the extracted `Node U` by an edge with weight $W$:\nIt calculates a theoretical new distance: `New_Distance = Distance[U] + W`.\nIt mathematically compares this against the currently known distance to V: `Distance[V]`.\nIf `New_Distance < Distance[V]`, it executes a process known as \"Relaxation.\" It violently overwrites the infinity (or the old larger distance) with the `New_Distance`, and aggressively updates `Node V`'s position in the Priority Queue to reflect this new, faster path.","**4. Termination:** The loop relentlessly continues extracting the next minimum node and relaxing its neighbors until the Priority Queue is completely empty."]},{"type":"subheading","content":"Concrete Computational Example"},{"type":"paragraph","content":"Consider a Graph with Nodes A, B, C. Source is A. Edges: A->B (weight 4), A->C (weight 1), C->B (weight 2)."},{"type":"list","items":["**Start:** Distance Array: `[A:0, B:inf, C:inf]`.","**Step 1:** Extract absolute minimum: A (0). Relax neighbors B and C. \nPath A->B = 0+4 = 4. (4 < inf). Update B to 4.\nPath A->C = 0+1 = 1. (1 < inf). Update C to 1.\nDistance Array: `[A:0, B:4, C:1]`.","**Step 2:** Extract next absolute minimum: C (1). Relax neighbor B.\nPath C->B = Distance[C] + Edge(C,B) = 1 + 2 = 3. \nBecause 3 < 4, we mathematically found a faster route to B! Violently overwrite B's distance. \nDistance Array: `[A:0, B:3, C:1]`.","**Step 3:** Extract next minimum: B (3). It has no unvisited neighbors.","**Result:** The absolute shortest paths from A are mathematically proven: To C takes 1, to B takes 3 (via C)."]},{"type":"subheading","content":"Time Complexity"},{"type":"paragraph","content":"If implemented using a highly optimized Fibonacci Heap, the extraction phase takes $O(V \\log V)$ and the relaxation phase takes $O(E)$, yielding a blistering absolute time complexity of $O(E + V \\log V)$."},{"type":"svg","content":""}]}},{"id":"v2-design-and-analysis-of-algorithms-2023-pC-q4","number":4,"marks":10,"tags":["Part C"],"text":[{"type":"paragraph","content":"Explain the 0/1 Knapsack problem using Dynamic Programming with a suitable example. Also explain the Matrix Chain Multiplication problem using Dynamic Programming."}],"answer":{"summary":"A rigorous exposition of Dynamic Programming (DP) techniques, violently deconstructing both the 0/1 Knapsack Problem and the Matrix Chain Multiplication Problem, showcasing how overlapping subproblems are tabulated in 2D arrays to prevent exponential CPU collapse.","explanation":[{"type":"heading","content":"Dynamic Programming: The 0/1 Knapsack Problem"},{"type":"paragraph","content":"The 0/1 Knapsack Problem is a catastrophic NP-Hard combinatorial optimization crisis. You are given a knapsack with a strict maximum weight capacity $W$, and $n$ distinct items, each possessing a specific weight $w_i$ and financial value $v_i$. The absolute mathematical objective is to select a subset of items that violently maximizes the total value without physically exceeding the capacity $W$. The \"0/1\" designation strictly mandates that an item must either be taken entirely (1) or completely left behind (0); it cannot be fractured. A naive recursive algorithm will attempt every single combination, resulting in a fatal $O(2^n)$ time complexity. Dynamic Programming completely annihilates this by utilizing a 2D Tabulation matrix."},{"type":"subheading","content":"The DP State Engine"},{"type":"paragraph","content":"We violently construct a massive 2D array `DP[i][w]`. This specific cell mathematically represents the absolute maximum value achievable using only the first $i$ items, given a strictly limited knapsack capacity of $w$."},{"type":"list","items":["**The Mathematical Recurrence Relation:** For every item $i$ and every incremental weight capacity $w$:","If the current item's weight is heavier than the current capacity ($w_i > w$), it physically cannot fit. The value is strictly inherited from the row above: `DP[i][w] = DP[i-1][w]`.","If the item CAN physically fit ($w_i \\le w$), the algorithm must mathematically make a critical choice to maximize value: either violently exclude the item, or aggressively include the item (adding its value $v_i$, and subtracting its weight $w_i$ from the remaining capacity).","**The Formula:** `DP[i][w] = MAX( DP[i-1][w] , v_i + DP[i-1][w - w_i] )`."]},{"type":"paragraph","content":"By mechanically filling this table from the bottom up, the absolute maximum value is guaranteed to be physically located in the final cell `DP[n][W]`. The time complexity is heavily optimized to a Pseudo-Polynomial $O(n \\cdot W)$."},{"type":"heading","content":"Dynamic Programming: Matrix Chain Multiplication"},{"type":"paragraph","content":"When mathematically multiplying a massive chain of matrices $A_1 \\times A_2 \\times ... \\times A_n$, the final physical matrix result is absolutely identical regardless of how the operations are grouped (due to the associative property). However, the specific placement of parentheses (e.g., $(A_1 \\times A_2) \\times A_3$ vs. $A_1 \\times (A_2 \\times A_3)$) violently alters the total number of scalar multiplications the CPU must execute. A bad grouping can waste billions of CPU cycles."},{"type":"subheading","content":"The DP Optimization Architecture"},{"type":"paragraph","content":"The objective is NOT to multiply the matrices, but to mathematically calculate the absolute most efficient parenthesization sequence to minimize scalar multiplications."},{"type":"list","items":["We aggressively construct a 2D array `M[i][j]` which mathematically stores the absolute minimum cost to multiply the sub-chain of matrices from $A_i$ to $A_j$.","**The Recurrence Relation:** To find the optimal split point $k$ (where $i \\le k < j$), the algorithm mathematically evaluates every single possible split point and aggressively selects the minimum.","**The Formula:** `M[i][j] = MIN( M[i][k] + M[k+1][j] + (row_i * col_k * col_j) )` for all $k$."]},{"type":"paragraph","content":"This DP approach heavily optimizes the execution time from an astronomical exponential bound down to a strict $O(n^3)$ polynomial time, saving massive computational overhead."}]}},{"id":"v2-design-and-analysis-of-algorithms-2023-pC-q5","number":5,"marks":10,"tags":["Part C"],"text":[{"type":"paragraph","content":"(a) Explain the concept of NP-Completeness."},{"type":"paragraph","content":"(b) Discuss Cook's Theorem and its significance."},{"type":"paragraph","content":"(c) Explain the Travelling Salesman Problem (TSP) and its complexity."}],"answer":{"summary":"A deep theoretical exposition on the catastrophic concept of NP-Completeness, detailing Cook's Theorem, Polynomial-Time Reducibility, and the severe implications this mathematical classification holds for the P vs NP crisis.","explanation":[{"type":"heading","content":"The Theoretical Architecture of NP-Completeness"},{"type":"paragraph","content":"In the highest echelons of theoretical computer science and complexity theory, the classification of **NP-Completeness** represents the absolute frontier of computational impossibility. Discovered simultaneously by Stephen Cook and Leonid Levin in 1971, this concept mathematically groups together the absolute hardest, most brutal computational problems that exist within the NP (Nondeterministic Polynomial time) class. These problems are so mathematically intertwined that if a computer scientist were to engineer a fast (Polynomial-Time) algorithm to solve just *one* of them, they would instantaneously provide a fast algorithm for *every single problem* in NP, violently solving the legendary P = NP crisis."},{"type":"subheading","content":"Mathematical Definition and Criteria"},{"type":"paragraph","content":"For a specific computational problem $X$ to be officially classified as mathematically NP-Complete, it must aggressively satisfy two absolute, non-negotiable theoretical conditions:"},{"type":"list","items":["**Condition 1 (Membership in NP):** The problem $X$ must absolutely belong to the class NP. This mathematically dictates that if an advanced oracle provides a proposed solution (a certificate) to problem $X$, a standard CPU must be able to rigidly verify if that solution is correct in strict Polynomial Time ($O(n^k)$).","**Condition 2 (NP-Hardness via Reduction):** Every single other problem in the entire NP class must be mathematically reducible to problem $X$ in strict Polynomial Time. This means if you possess a hypothetical \"black box\" that solves $X$ instantly, you can mathematically manipulate the inputs of ANY other NP problem, feed them into the black box, and solve them just as fast. This proves $X$ is at least as hard as the hardest problems in NP."]},{"type":"subheading","content":"Polynomial-Time Reducibility ($Y \\le_p X$)"},{"type":"paragraph","content":"The absolute core of NP-Completeness relies on the mathematical concept of Reduction. If we have a known, impossibly hard problem $Y$ (like the Traveling Salesperson Problem), and we want to prove a brand new problem $X$ is NP-Complete, we do not need to test every problem in the universe. We mathematically prove that we can take any instance of $Y$, violently transform it into an instance of $X$ using a fast polynomial-time algorithm, and use the solution for $X$ to answer $Y$. If $Y$ reduces to $X$, then $X$ mathematically inherits the catastrophic difficulty of $Y$."},{"type":"subheading","content":"Cook's Theorem (The Genesis Problem)"},{"type":"paragraph","content":"Before you can use reduction, you need an absolute \"first\" problem that is mathematically proven to be NP-Complete from scratch. Stephen Cook provided this massive breakthrough by mathematically proving that the **Boolean Satisfiability Problem (SAT)** is NP-Complete. He demonstrated that the physical mechanics of any Nondeterministic Turing Machine executing any NP algorithm can be mathematically translated entirely into a massive Boolean logic formula. Therefore, solving SAT is physically equivalent to solving any NP problem."},{"type":"paragraph","content":"Today, thousands of critical problems (like Graph Coloring, Knapsack, and Hamiltonian Path) have been mathematically proven to be NP-Complete by violently reducing them back to the SAT problem."}]}}]},{"id":"design-and-analysis-of-algorithms-2024","title":"Design and Analysis of Algorithms (2024)","subjectSlug":"design-and-analysis-of-algorithms","subjectName":"Design and Analysis of Algorithms","universitySlug":"rtu","branchSlug":"computer-science","year":3,"semester":5,"examYear":2024,"paperCode":"5E1755","questions":[{"id":"v2-design-and-analysis-of-algorithms-2024-pA-q1","number":1,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"Define Recurrence Relation."}],"answer":{"summary":"A recurrence relation defines a sequence where each term is a function of one or more previous terms.","explanation":[{"type":"paragraph","content":"A Recurrence Relation is an equation that defines each element of a sequence in terms of one or more of its preceding elements. In algorithm analysis, it expresses the running time T(n) of a recursive algorithm in terms of the running time on smaller inputs."},{"type":"paragraph","content":"Example: T(n) = T(n-1) + 1 (recursive linear scan), T(n) = 2T(n/2) + n (Merge Sort), T(n) = T(n-1) + T(n-2) (Fibonacci). Solving recurrences (Substitution, Recursion Tree, or Master Theorem) gives the closed-form time complexity."}]}},{"id":"v2-design-and-analysis-of-algorithms-2024-pA-q2","number":2,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"What is Space Complexity?"}],"answer":{"summary":"Space Complexity is the amount of memory an algorithm uses as a function of input size.","explanation":[{"type":"paragraph","content":"Space Complexity is the measure of the amount of working storage (memory) an algorithm requires as a function of the size of the input n. It includes both the space needed for the input data and the auxiliary space used by the algorithm during execution."},{"type":"paragraph","content":"Space complexity is expressed using asymptotic notations. Example: Merge Sort requires O(n) auxiliary space for temporary arrays; Binary Search (iterative) requires O(1) auxiliary space; DFS uses O(V) space for the stack. It is as important as time complexity in resource-constrained systems."}]}},{"id":"v2-design-and-analysis-of-algorithms-2024-pA-q3","number":3,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"Define Heap."}],"answer":{"summary":"A Heap is a complete binary tree satisfying the heap property: max-heap (parent ≥ children) or min-heap (parent ≤ children).","explanation":[{"type":"paragraph","content":"A Heap is a specialized tree-based data structure that satisfies the heap property. It is a complete binary tree (all levels filled except possibly the last, which is filled left to right). Stored efficiently in an array: for node at index i, left child is at 2i+1, right child at 2i+2, parent at (i-1)/2."},{"type":"paragraph","content":"Max-Heap: Every parent node is greater than or equal to its children. Min-Heap: Every parent node is less than or equal to its children. Operations: Build Heap O(n), Insert O(log n), Extract-Max/Min O(log n). Used in Heap Sort, Priority Queues, Dijkstra's and Prim's algorithms."}]}},{"id":"v2-design-and-analysis-of-algorithms-2024-pA-q4","number":4,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"What is Amortized Analysis?"}],"answer":{"summary":"Amortized Analysis determines the average cost per operation over a sequence of operations, smoothing out expensive occasional operations.","explanation":[{"type":"paragraph","content":"Amortized Analysis is a technique for analyzing the time complexity of an algorithm by averaging the worst-case cost over a sequence of n operations. It provides a more realistic average cost per operation even when occasional operations are expensive."},{"type":"paragraph","content":"Three methods: (1) Aggregate Method — total cost of n operations divided by n; (2) Accounting Method — assign amortized costs, some prepay for future expensive operations; (3) Potential Method — use a potential function to measure stored energy. Example: Dynamic array doubling — individual push may cost O(n) when resizing, but amortized over all n pushes, each push costs O(1) amortized."}]}},{"id":"v2-design-and-analysis-of-algorithms-2024-pA-q5","number":5,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"Define Graph Traversal."}],"answer":{"summary":"Graph traversal is the process of visiting all vertices in a graph in a systematic manner, either using BFS or DFS.","explanation":[{"type":"paragraph","content":"Graph Traversal refers to the process of visiting (checking or updating) each vertex in a graph exactly once in a systematic way. The two fundamental graph traversal algorithms are Breadth-First Search (BFS) and Depth-First Search (DFS)."},{"type":"paragraph","content":"BFS explores vertices level by level using a queue — visits all neighbors before going deeper. Time: O(V+E). DFS explores as far as possible along a branch before backtracking, using a stack or recursion. Time: O(V+E). Applications: BFS for shortest path in unweighted graphs; DFS for topological sort, cycle detection, and SCC."}]}},{"id":"v2-design-and-analysis-of-algorithms-2024-pA-q6","number":6,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"What is Optimal Substructure?"}],"answer":{"summary":"Optimal Substructure means the optimal solution to a problem contains optimal solutions to its subproblems.","explanation":[{"type":"paragraph","content":"A problem exhibits Optimal Substructure if an optimal solution to the problem can be constructed efficiently from optimal solutions to its subproblems. This property is a necessary condition for both Dynamic Programming and Greedy algorithms to work correctly."},{"type":"paragraph","content":"Examples: Shortest path exhibits optimal substructure — if the shortest path from u to v goes through w, then the subpath from u to w and from w to v must also be shortest paths. 0/1 Knapsack and LCS also have optimal substructure. Note: Longest simple path does NOT have optimal substructure."}]}},{"id":"v2-design-and-analysis-of-algorithms-2024-pA-q7","number":7,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"Define Branch and Bound."}],"answer":{"summary":"Branch and Bound is an algorithm design paradigm that systematically enumerates candidate solutions while using bounds to prune suboptimal branches.","explanation":[{"type":"paragraph","content":"Branch and Bound is an algorithm design technique for solving discrete optimization problems. It exhaustively searches the solution space while using bounding functions to eliminate (prune) subspaces that cannot contain the optimal solution, thereby avoiding unnecessary exploration."},{"type":"paragraph","content":"Three key steps: (1) Branch — divide the problem into subproblems (branch the search tree); (2) Bound — compute an optimistic bound (upper/lower) on the best solution achievable in each subspace; (3) Prune — discard branches where the bound is worse than the current best solution. Used for TSP, 0/1 Knapsack, and Integer Programming."}]}},{"id":"v2-design-and-analysis-of-algorithms-2024-pA-q8","number":8,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"What is a Randomized Algorithm?"}],"answer":{"summary":"A Randomized Algorithm uses random numbers to make decisions during execution, giving good expected performance.","explanation":[{"type":"paragraph","content":"A Randomized Algorithm is an algorithm that employs a degree of randomness as part of its logic. It uses random number generation to make some decisions, resulting in algorithms whose behavior may vary across different runs on the same input."},{"type":"paragraph","content":"Two types: (1) Las Vegas — always produces a correct answer but running time varies (e.g., Randomized QuickSort with random pivot — expected O(n log n)); (2) Monte Carlo — runs in fixed time but may produce an incorrect answer with small probability (e.g., Miller-Rabin primality test). Randomization helps avoid worst-case inputs."}]}},{"id":"v2-design-and-analysis-of-algorithms-2024-pA-q9","number":9,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"Define Approximation Algorithm."}],"answer":{"summary":"An Approximation Algorithm finds near-optimal solutions to NP-Hard optimization problems in polynomial time with a guaranteed performance ratio.","explanation":[{"type":"paragraph","content":"An Approximation Algorithm is an algorithm that finds approximate solutions to computationally hard (NP-Hard) optimization problems, running in polynomial time but producing a solution within a provable factor of the optimal solution."},{"type":"paragraph","content":"The approximation ratio ρ(n) guarantees: cost(approx) ≤ ρ(n) × cost(optimal) for minimization problems. Example: A 2-approximation algorithm for the Vertex Cover problem always produces a cover at most twice the size of the minimum cover. Christofides' algorithm for metric TSP achieves a 3/2-approximation."}]}},{"id":"v2-design-and-analysis-of-algorithms-2024-pA-q10","number":10,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"What is Floyd-Warshall Algorithm?"}],"answer":{"summary":"Floyd-Warshall Algorithm finds shortest paths between all pairs of vertices in a weighted graph, including negative edges (but no negative cycles).","explanation":[{"type":"paragraph","content":"The Floyd-Warshall Algorithm is a dynamic programming algorithm that computes shortest paths between every pair of vertices in a weighted directed graph. It handles negative edge weights but not negative cycles. Time Complexity: O(V³), Space: O(V²)."},{"type":"paragraph","content":"It works by iteratively improving the shortest path estimate between every pair (i, j) by considering each vertex k as an intermediate vertex: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) for each k from 1 to V. After considering all intermediate vertices, dist[i][j] holds the shortest path length."}]}},{"id":"v2-design-and-analysis-of-algorithms-2024-pB-q1","number":1,"marks":4,"tags":["Part B"],"text":[{"type":"paragraph","content":"Explain Heap Sort algorithm and its time complexity."}],"answer":{"summary":"Heap Sort uses a max-heap to sort in O(n log n) time in-place with O(1) extra space.","explanation":[{"type":"paragraph","content":"Heap Sort is a comparison-based sorting algorithm that uses a binary max-heap data structure. It first builds a max-heap from the input array, then repeatedly extracts the maximum element to produce a sorted array."},{"type":"heading","content":"Algorithm Steps"},{"type":"list","items":["Phase 1 — Build Max-Heap: Starting from the last non-leaf node (index n/2-1) down to 0, apply heapify. Time: O(n).","Phase 2 — Sort: Repeat n-1 times: swap the root (maximum) with the last element of the heap, reduce heap size by 1, and heapify the root. Time: O(n log n).","Heapify: Ensures the subtree rooted at a node satisfies the max-heap property by swapping with the larger child and recursing."]},{"type":"heading","content":"Time Complexity"},{"type":"list","items":["Build Max-Heap: O(n).","Each heapify during extraction: O(log n).","Total for n extractions: O(n log n).","Best, Average, Worst Case: O(n log n) — always, unlike Quick Sort.","Space Complexity: O(1) — in-place sort, unlike Merge Sort's O(n)."]}]}},{"id":"v2-design-and-analysis-of-algorithms-2024-pB-q2","number":2,"marks":4,"tags":["Part B"],"text":[{"type":"paragraph","content":"Describe Prim's Algorithm for Minimum Spanning Tree with an example."}],"answer":{"summary":"Prim's algorithm grows the MST from a starting vertex by repeatedly adding the minimum-weight edge connecting the tree to a new vertex.","explanation":[{"type":"paragraph","content":"Prim's Algorithm is a greedy algorithm that finds the Minimum Spanning Tree (MST) by starting from an arbitrary vertex and repeatedly adding the minimum-weight edge that connects a vertex in the MST to a vertex outside it."},{"type":"heading","content":"Algorithm Steps"},{"type":"list","items":["Initialize: key[source] = 0, key[all others] = ∞. Add all vertices to a priority queue. parent[] array tracks MST structure.","While priority queue is not empty: extract vertex u with minimum key value.","For each neighbor v of u not yet in MST: if weight(u,v) < key[v], update key[v] = weight(u,v) and parent[v] = u.","Repeat until all vertices are in the MST."]},{"type":"heading","content":"Example"},{"type":"paragraph","content":"Graph with vertices A,B,C,D and edges A-B(4), A-C(2), B-C(1), B-D(5), C-D(8). Start at A: Add A-C(2), then C-B(1), then B-D(5). MST has edges {A-C, B-C, B-D} with total weight 8."},{"type":"paragraph","content":"Time Complexity: O((V+E) log V) with a binary heap. O(E log V) for dense graphs. Unlike Kruskal's (edge-based), Prim's grows the tree vertex by vertex, making it more suitable for dense graphs."}]}},{"id":"v2-design-and-analysis-of-algorithms-2024-pB-q3","number":3,"marks":4,"tags":["Part B"],"text":[{"type":"paragraph","content":"Explain the activity selection problem using the Greedy approach."}],"answer":{"summary":"The Activity Selection Problem greedily selects the maximum number of non-overlapping activities by always picking the activity that finishes earliest.","explanation":[{"type":"paragraph","content":"The Activity Selection Problem: Given n activities each with start time sᵢ and finish time fᵢ, select the maximum number of mutually compatible (non-overlapping) activities. Two activities i and j are compatible if their intervals don't overlap (fᵢ ≤ sⱼ or fⱼ ≤ sᵢ)."},{"type":"heading","content":"Greedy Strategy: Earliest Finish Time"},{"type":"list","items":["Sort all activities by their finish time in non-decreasing order.","Select the first activity (earliest finish time).","For each subsequent activity: if its start time ≥ finish time of the last selected activity, select it.","Repeat until all activities are considered."]},{"type":"heading","content":"Example"},{"type":"paragraph","content":"Activities sorted by finish time: A1(1,4), A2(3,5), A3(0,6), A4(5,7), A5(8,9), A6(5,9). Select A1(f=4), next: A4(s=5≥4, select, f=7), next: A5(s=8≥7, select). Optimal selection: {A1, A4, A5} with 3 activities."},{"type":"paragraph","content":"Why greedy works: The activity finishing earliest leaves maximum room for remaining activities. Greedy Choice Property is provable by exchange argument. Time Complexity: O(n log n) for sorting + O(n) for selection = O(n log n)."}]}},{"id":"v2-design-and-analysis-of-algorithms-2024-pB-q4","number":4,"marks":4,"tags":["Part B"],"text":[{"type":"paragraph","content":"Discuss the Longest Common Subsequence (LCS) problem using Dynamic Programming."}],"answer":{"summary":"LCS finds the longest subsequence common to two sequences using DP with a 2D table, running in O(mn) time.","explanation":[{"type":"paragraph","content":"The Longest Common Subsequence (LCS) problem: Given two sequences X = ⟨x₁, x₂, ..., xₘ⟩ and Y = ⟨y₁, y₂, ..., yₙ⟩, find the longest subsequence common to both. A subsequence preserves relative order but need not be contiguous."},{"type":"heading","content":"DP Recurrence"},{"type":"paragraph","content":"Define c[i][j] = length of LCS of Xᵢ and Yⱼ (first i chars of X and first j chars of Y). c[i][j] = 0 if i=0 or j=0; c[i][j] = c[i-1][j-1] + 1 if xᵢ == yⱼ; c[i][j] = max(c[i-1][j], c[i][j-1]) if xᵢ ≠ yⱼ."},{"type":"heading","content":"Example"},{"type":"paragraph","content":"X = ABCBDAB, Y = BDCAB. Build the c[][] table of size (m+1)×(n+1). The LCS has length 4. By backtracking the table, the LCS is BCAB or BDAB. Time Complexity: O(mn). Space Complexity: O(mn), reducible to O(min(m,n))."},{"type":"paragraph","content":"Applications: Diff tools (comparing files), DNA sequence alignment in bioinformatics, version control systems, and spell checkers."}]}},{"id":"v2-design-and-analysis-of-algorithms-2024-pB-q5","number":5,"marks":4,"tags":["Part B"],"text":[{"type":"paragraph","content":"Explain the concept of Graph Coloring and Hamiltonian Cycle."}],"answer":{"summary":"Graph Coloring assigns colors to vertices so no adjacent vertices share a color. Hamiltonian Cycle visits every vertex exactly once and returns to start.","explanation":[{"type":"heading","content":"Graph Coloring"},{"type":"paragraph","content":"Graph Coloring is the assignment of colors (labels) to vertices of a graph such that no two adjacent vertices share the same color. The Chromatic Number χ(G) is the minimum number of colors needed. The m-Coloring Decision Problem (can G be colored with m colors?) is NP-Complete for m ≥ 3."},{"type":"list","items":["2-Colorable graphs are bipartite graphs, solvable in O(V+E) using BFS.","3-Coloring is NP-Complete.","Application: Register allocation in compilers, scheduling, map coloring."]},{"type":"heading","content":"Hamiltonian Cycle"},{"type":"paragraph","content":"A Hamiltonian Cycle is a cycle in a graph that visits every vertex exactly once and returns to the starting vertex. The Hamiltonian Cycle Problem (does such a cycle exist?) is NP-Complete. Note: This differs from Eulerian Cycle (visits every edge once)."},{"type":"list","items":["Finding a Hamiltonian Cycle by backtracking: Try adding vertices one by one; backtrack if a vertex is already visited or no valid edge exists.","Dirac's Theorem (sufficient condition): If every vertex has degree ≥ n/2, a Hamiltonian Cycle exists.","Application: TSP, DNA fragment assembly, circuit board manufacturing."]}]}},{"id":"v2-design-and-analysis-of-algorithms-2024-pB-q6","number":6,"marks":4,"tags":["Part B"],"text":[{"type":"paragraph","content":"Describe the Subset Sum problem using Backtracking."}],"answer":{"summary":"Subset Sum problem finds subsets summing to a target value using backtracking to prune invalid branches early.","explanation":[{"type":"paragraph","content":"The Subset Sum Problem: Given a set S = {s₁, s₂, ..., sₙ} of positive integers and a target sum T, find all subsets of S whose elements sum exactly to T. This is NP-Complete."},{"type":"heading","content":"Backtracking Approach"},{"type":"list","items":["Sort the set in non-decreasing order for efficient pruning.","Build a subset tree: at each node, decide to include or exclude the current element.","Include element sᵢ: if current_sum + sᵢ == T, print solution; if current_sum + sᵢ < T, recurse for sᵢ₊₁.","Exclude element sᵢ: if current_sum + sᵢ₊₁ ≤ T, recurse without including sᵢ.","Bounding: prune if current_sum > T (too large) or current_sum + remaining_sum < T (too small)."]},{"type":"heading","content":"Example"},{"type":"paragraph","content":"S = {3, 5, 6, 7}, T = 15. Sort: {3, 5, 6, 7}. Include 3: recurse {5,6,7} with sum=3. Include 5: recurse {6,7} with sum=8. Include 6: sum=14 < 15. Include 7: sum=21 > 15 → backtrack. Exclude 6: include 7, sum=15 → Solution: {3,5,7}. Found! The algorithm prunes many branches, making it efficient in practice."}]}},{"id":"v2-design-and-analysis-of-algorithms-2024-pB-q7","number":7,"marks":4,"tags":["Part B"],"text":[{"type":"paragraph","content":"Explain the concept of String Matching algorithms (Naive and KMP)."}],"answer":{"summary":"Naive string matching scans all positions in O(nm) time; KMP uses a failure function to skip redundant comparisons in O(n+m) time.","explanation":[{"type":"heading","content":"Naive String Matching"},{"type":"paragraph","content":"The Naive algorithm slides the pattern P of length m over text T of length n, checking for a match at each position. For each shift s from 0 to n-m, compare P[1..m] with T[s+1..s+m]. Time: O((n-m+1)·m) ≈ O(nm) in the worst case. Space: O(1). Simple but inefficient for large texts."},{"type":"heading","content":"KMP (Knuth-Morris-Pratt) Algorithm"},{"type":"paragraph","content":"KMP avoids redundant comparisons by precomputing a failure function (also called lps — Longest Proper Prefix which is also Suffix) for the pattern P. The failure function lps[i] gives the length of the longest proper prefix of P[0..i] that is also a suffix."},{"type":"list","items":["Precompute lps[] array for pattern P in O(m) time.","Matching: scan text T left to right. When a mismatch occurs at P[j], instead of restarting, shift to P[lps[j-1]] using precomputed information.","This ensures no character of T is compared more than twice.","Total Time: O(n + m) — preprocessing O(m) + matching O(n).","Space: O(m) for lps array."]},{"type":"paragraph","content":"Example: Pattern P = 'AABAAB', Text T = 'AABAAAABAAB'. lps = [0,1,0,1,2,3]. KMP finds the match starting at index 5 in T without backtracking in the text."}]}},{"id":"v2-design-and-analysis-of-algorithms-2024-pC-q1","number":1,"marks":10,"tags":["Part C"],"text":[{"type":"paragraph","content":"(a) Explain the Strassen's Matrix Multiplication algorithm in detail."},{"type":"paragraph","content":"(b) Compare Strassen's algorithm with the conventional matrix multiplication and analyze its time complexity."}],"answer":{"summary":"Strassen's algorithm multiplies two n×n matrices in O(n^2.807) using 7 recursive multiplications instead of the conventional 8, reducing asymptotic complexity.","explanation":[{"type":"heading","content":"Part (a): Strassen's Matrix Multiplication"},{"type":"paragraph","content":"Strassen's Algorithm (1969) is a divide-and-conquer algorithm for matrix multiplication that improves over the conventional O(n³) algorithm by using only 7 recursive multiplications instead of 8, at the cost of 18 additions/subtractions."},{"type":"heading","content":"Algorithm: Divide n×n matrices into four n/2 × n/2 submatrices"},{"type":"paragraph","content":"For C = A × B, partition: A = [[A₁₁, A₁₂], [A₂₁, A₂₂]], B = [[B₁₁, B₁₂], [B₂₁, B₂₂]], C = [[C₁₁, C₁₂], [C₂₁, C₂₂]]."},{"type":"heading","content":"Seven Products (Strassen's Formulas)"},{"type":"list","items":["P₁ = A₁₁ × (B₁₂ - B₂₂)","P₂ = (A₁₁ + A₁₂) × B₂₂","P₃ = (A₂₁ + A₂₂) × B₁₁","P₄ = A₂₂ × (B₂₁ - B₁₁)","P₅ = (A₁₁ + A₂₂) × (B₁₁ + B₂₂)","P₆ = (A₁₂ - A₂₂) × (B₂₁ + B₂₂)","P₇ = (A₁₁ - A₂₁) × (B₁₁ + B₁₂)"]},{"type":"heading","content":"Result Computation"},{"type":"list","items":["C₁₁ = P₅ + P₄ - P₂ + P₆","C₁₂ = P₁ + P₂","C₂₁ = P₃ + P₄","C₂₂ = P₅ + P₁ - P₃ - P₇"]},{"type":"svg","src":"/assets/diagrams/rtu/cs/2024/design-and-analysis-of-algorithms/strassen-matrix-partition.svg","alt":"Strassen's Matrix Partition","caption":"Partitioning of matrices into quadrants for Strassen's recursive multiplication"},{"type":"heading","content":"Part (b): Comparison and Time Complexity Analysis"},{"type":"heading","content":"Conventional Matrix Multiplication"},{"type":"paragraph","content":"Standard algorithm: C[i][j] = Σₖ A[i][k] × B[k][j] for 1 ≤ k ≤ n. Uses 3 nested loops. Time: O(n³) — performs n³ multiplications and n³ additions. Recurrence for divide-and-conquer version: T(n) = 8T(n/2) + Θ(n²) → T(n) = Θ(n³) by Master Theorem Case 1 (n^log₂8 = n³)."},{"type":"heading","content":"Strassen's Time Complexity"},{"type":"paragraph","content":"Strassen's recurrence: T(n) = 7T(n/2) + Θ(n²). Using Master Theorem: a=7, b=2, f(n)=n². n^log_b(a) = n^log₂7 ≈ n^2.807. Since f(n) = n² = O(n^(2.807-ε)), Case 1 applies: T(n) = Θ(n^log₂7) ≈ Θ(n^2.807)."},{"type":"list","items":["Conventional: O(n³) ≈ O(n^3.000)","Strassen: O(n^2.807)","For n = 1000: n³ = 10⁹ vs n^2.807 ≈ 10^8.4 — approximately 4x faster.","Practical notes: Strassen's has larger constant factors and is numerically less stable. Used in practice for very large matrices. Best known algorithm: Coppersmith-Winograd at O(n^2.373)."]}]}},{"id":"v2-design-and-analysis-of-algorithms-2024-pC-q2","number":2,"marks":10,"tags":["Part C"],"text":[{"type":"paragraph","content":"(a) Explain the All-Pairs Shortest Path problem using the Floyd-Warshall algorithm."},{"type":"paragraph","content":"(b) Solve a given weighted graph using the Floyd-Warshall algorithm with a suitable example."}],"answer":{"summary":"Floyd-Warshall solves All-Pairs Shortest Path in O(V³) using DP by iteratively considering each vertex as an intermediate node.","explanation":[{"type":"heading","content":"Part (a): Floyd-Warshall Algorithm"},{"type":"paragraph","content":"The Floyd-Warshall algorithm finds the shortest paths between every pair of vertices in a weighted directed graph (with possible negative edges but no negative cycles). It uses Dynamic Programming with the principle: the shortest path from i to j using intermediate vertices from {1, 2, ..., k}."},{"type":"heading","content":"DP Formulation"},{"type":"paragraph","content":"Define d⁽ᵏ⁾[i][j] = weight of shortest path from i to j using only vertices {1, 2, ..., k} as intermediates. Recurrence: d⁽ᵏ⁾[i][j] = min(d⁽ᵏ⁻¹⁾[i][j], d⁽ᵏ⁻¹⁾[i][k] + d⁽ᵏ⁻¹⁾[k][j]). Base case: d⁽⁰⁾[i][j] = w(i,j) if edge exists; 0 if i=j; ∞ otherwise."},{"type":"heading","content":"Algorithm Pseudocode"},{"type":"list","items":["Initialize dist[i][j] with the weight matrix (∞ for no edge, 0 for diagonal).","For k from 1 to V (each intermediate vertex):"," For i from 1 to V:"," For j from 1 to V:"," dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])","After completion, dist[i][j] = shortest path from i to j.","Negative cycle detection: if dist[i][i] < 0 for any i, a negative cycle exists."]},{"type":"heading","content":"Part (b): Worked Example"},{"type":"paragraph","content":"Graph with 4 vertices and edges: (1→2, w=3), (1→3, w=8), (1→4, w=-4), (2→3, w=1), (2→4, w=7), (3→2, w=4), (4→3, w=2), (4→1, w=-4 is missing), (3→1, w=-5), (4→3, w=2)."},{"type":"paragraph","content":"Initial dist matrix (∞ = no direct edge): d[1][2]=3, d[1][3]=8, d[1][4]=-4, d[2][3]=1, d[2][4]=7, d[3][1]=-5, d[3][2]=4, d[4][3]=2. After running 3 iterations (k=1,2,3,4), d[1][2]=1, d[1][3]=3, d[1][4]=-4, d[2][1]=-4, d[2][3]=-1, d[2][4]=-5, etc. Total Time: O(V³) = O(64) for V=4."},{"type":"svg","src":"/assets/diagrams/rtu/cs/2024/design-and-analysis-of-algorithms/floyd-warshall-example.svg","alt":"Floyd-Warshall Algorithm Example","caption":"Weighted directed graph and the resulting all-pairs shortest path matrix"},{"type":"paragraph","content":"Time Complexity: O(V³). Space: O(V²). Advantage over running Dijkstra V times: handles negative edges, simpler implementation, same asymptotic complexity for dense graphs."}]}},{"id":"v2-design-and-analysis-of-algorithms-2024-pC-q3","number":3,"marks":10,"tags":["Part C"],"text":[{"type":"paragraph","content":"(a) Explain the concept of Huffman Coding using the Greedy approach."},{"type":"paragraph","content":"(b) Construct the Huffman tree and derive codes for a given set of characters with their frequencies."}],"answer":{"summary":"Huffman Coding is a greedy optimal prefix-free encoding that assigns shorter codes to more frequent characters, minimizing total encoded length.","explanation":[{"type":"heading","content":"Part (a): Huffman Coding Concept"},{"type":"paragraph","content":"Huffman Coding is a lossless data compression algorithm devised by David Huffman in 1952. It assigns variable-length binary codes to characters based on their frequencies — more frequent characters get shorter codes. It produces an optimal prefix-free code (no codeword is a prefix of another), ensuring unambiguous decoding."},{"type":"heading","content":"Greedy Strategy"},{"type":"list","items":["Create a leaf node for each character and add it to a min-priority queue (keyed by frequency).","While the queue has more than one node:"," Extract the two nodes with minimum frequency (x and y)."," Create a new internal node z with frequency = freq(x) + freq(y)."," Set x and y as left and right children of z."," Insert z back into the priority queue.","The remaining node is the root of the Huffman tree.","Traverse the tree: left = 0, right = 1 to assign codes."]},{"type":"heading","content":"Part (b): Worked Example"},{"type":"paragraph","content":"Characters and frequencies: A=5, B=9, C=12, D=13, E=16, F=45."},{"type":"heading","content":"Building the Huffman Tree"},{"type":"list","items":["Initial queue: A(5), B(9), C(12), D(13), E(16), F(45).","Step 1: Extract A(5) and B(9). Create Z1(14). Queue: C(12), D(13), Z1(14), E(16), F(45).","Step 2: Extract C(12) and D(13). Create Z2(25). Queue: Z1(14), E(16), Z2(25), F(45).","Step 3: Extract Z1(14) and E(16). Create Z3(30). Queue: Z2(25), Z3(30), F(45).","Step 4: Extract Z2(25) and Z3(30). Create Z4(55). Queue: F(45), Z4(55).","Step 5: Extract F(45) and Z4(55). Create root(100)."]},{"type":"heading","content":"Resulting Codes"},{"type":"list","items":["F: 0 (1 bit)","C: 100 (3 bits)","D: 101 (3 bits)","A: 1100 (4 bits)","B: 1101 (4 bits)","E: 111 (3 bits)"]},{"type":"svg","src":"/assets/diagrams/rtu/cs/2024/design-and-analysis-of-algorithms/huffman-tree.svg","alt":"Huffman Coding Tree","caption":"Huffman tree for characters A(5), B(9), C(12), D(13), E(16), F(45) — root has frequency 100"},{"type":"heading","content":"Verification"},{"type":"paragraph","content":"Total encoded bits = 5×4 + 9×4 + 12×3 + 13×3 + 16×3 + 45×1 = 20 + 36 + 36 + 39 + 48 + 45 = 224 bits. Fixed-length encoding would require ⌈log₂6⌉ = 3 bits per character × 100 = 300 bits. Huffman saves (300-224)/300 ≈ 25.3% space. Time Complexity: O(n log n). Huffman coding is used in JPEG, MP3, ZIP compression formats."}]}},{"id":"v2-design-and-analysis-of-algorithms-2024-pC-q4","number":4,"marks":10,"tags":["Part C"],"text":[{"type":"paragraph","content":"Explain the concept of Dynamic Programming in detail. Solve the 0/1 Knapsack problem and the Coin Change problem with examples."}],"answer":{"summary":"Dynamic Programming solves optimization problems with overlapping subproblems and optimal substructure. 0/1 Knapsack and Coin Change are classic DP problems solved with 2D and 1D tables respectively.","explanation":[{"type":"heading","content":"Dynamic Programming: Core Concepts"},{"type":"paragraph","content":"Dynamic Programming (DP) is a method for solving complex problems by breaking them down into simpler, overlapping subproblems and storing the results to avoid redundant computation. It applies when the problem has:"},{"type":"list","items":["Overlapping Subproblems: Same subproblems are solved multiple times (unlike Divide & Conquer).","Optimal Substructure: Optimal solution is composed of optimal solutions to subproblems.","Two implementation styles: Top-Down (Memoization) — recursive + cache; Bottom-Up (Tabulation) — iterative table filling."]},{"type":"heading","content":"Problem 1: 0/1 Knapsack"},{"type":"paragraph","content":"Items: (v=6,w=2), (v=10,w=4), (v=12,w=6). Capacity W=10. Build dp[i][w] table (i = items 0 to 3, w = capacity 0 to 10)."},{"type":"list","items":["dp[0][w] = 0 for all w (no items → no value).","Item 1 (v=6,w=2): dp[1][w] = 6 for w≥2, else 0.","Item 2 (v=10,w=4): dp[2][w] = max(dp[1][w], 10+dp[1][w-4]). dp[2][4]=10, dp[2][6]=16 (6+10).","Item 3 (v=12,w=6): dp[3][10] = max(dp[2][10], 12+dp[2][4]) = max(16, 22) = 22.","Optimal: Take items 1 (w=2,v=6) and 3 (w=6,v=12) and item 2 (w=4,v=10) but 2+6+4>10. Take items 2+3: 4+6=10, v=22. ✓"]},{"type":"svg","src":"/assets/diagrams/rtu/cs/2024/design-and-analysis-of-algorithms/knapsack-dp-2024.svg","alt":"0/1 Knapsack DP Table 2024","caption":"DP table for 0/1 Knapsack with 3 items and capacity 10"},{"type":"heading","content":"Problem 2: Coin Change Problem"},{"type":"paragraph","content":"Given coins of denominations {1, 3, 4} and target amount = 6, find the minimum number of coins to make the amount."},{"type":"paragraph","content":"DP Formulation: dp[0] = 0. For w from 1 to 6: dp[w] = min over all coins c where c ≤ w of { dp[w-c] + 1 }."},{"type":"list","items":["dp[0] = 0","dp[1] = min(dp[0]+1) = 1 (coin 1)","dp[2] = min(dp[1]+1) = 2 (1+1)","dp[3] = min(dp[2]+1, dp[0]+1) = 1 (coin 3)","dp[4] = min(dp[3]+1, dp[1]+1, dp[0]+1) = 1 (coin 4)","dp[5] = min(dp[4]+1, dp[2]+1, dp[1]+1) = 2 (4+1)","dp[6] = min(dp[5]+1, dp[3]+1, dp[2]+1) = 2 (3+3)"]},{"type":"paragraph","content":"Minimum coins for 6 = 2 (using coins {3, 3}). Time Complexity: O(amount × number_of_coins). Space: O(amount). This is the classic unbounded version where each coin can be used multiple times."}]}},{"id":"v2-design-and-analysis-of-algorithms-2024-pC-q5","number":5,"marks":10,"tags":["Part C"],"text":[{"type":"paragraph","content":"(a) Explain the concept of Approximation Algorithms."},{"type":"paragraph","content":"(b) Discuss the Vertex Cover Problem and the Travelling Salesman Problem (TSP) approximation algorithms."}],"answer":{"summary":"Approximation algorithms provide polynomial-time solutions with guaranteed quality bounds for NP-Hard problems. Vertex Cover has a 2-approximation; TSP has a 2-approximation for metric instances.","explanation":[{"type":"heading","content":"Part (a): Approximation Algorithms"},{"type":"paragraph","content":"Since NP-Hard optimization problems cannot be solved exactly in polynomial time (assuming P ≠ NP), Approximation Algorithms provide efficient (polynomial-time) algorithms that find solutions guaranteed to be within a constant factor of the optimal solution."},{"type":"heading","content":"Performance Ratio (Approximation Ratio)"},{"type":"paragraph","content":"An algorithm has approximation ratio ρ(n) if for all inputs of size n: max(C/C*, C*/C) ≤ ρ(n), where C is the algorithm's solution cost and C* is the optimal cost. For minimization: C ≤ ρ(n)·C*. For maximization: C ≥ C*/ρ(n). A ρ=1 means exact; ρ=2 means at most twice optimal."},{"type":"heading","content":"Part (b1): Vertex Cover Approximation"},{"type":"paragraph","content":"Vertex Cover Problem: Find the smallest set of vertices such that every edge in the graph has at least one endpoint in the set. This is NP-Complete."},{"type":"heading","content":"2-Approximation Algorithm"},{"type":"list","items":["Initialize cover C = ∅.","While there are uncovered edges in G:"," Pick any uncovered edge (u, v)."," Add both u and v to C."," Remove all edges incident to u or v.","Return C."]},{"type":"paragraph","content":"Correctness: Every edge selected has both endpoints in C, so all edges are covered. Approximation Ratio = 2: The edges selected form a matching M. Any optimal vertex cover must include at least one endpoint of each edge in M, so |C*| ≥ |M|. Our algorithm picks 2|M| vertices, so |C| = 2|M| ≤ 2|C*|. Time: O(V+E)."},{"type":"heading","content":"Part (b2): TSP Approximation Algorithm"},{"type":"paragraph","content":"For metric TSP (satisfying triangle inequality: cost(u,w) ≤ cost(u,v) + cost(v,w)), a 2-approximation exists using MST."},{"type":"heading","content":"MST-based 2-Approximation for Metric TSP"},{"type":"list","items":["Find MST T of the complete graph using Prim's or Kruskal's algorithm.","List vertices in preorder DFS traversal of T.","Return the Hamiltonian cycle following that preorder (shortcutting repeated vertices)."]},{"type":"paragraph","content":"Proof of 2-approximation: Let H* be the optimal TSP tour. Removing one edge from H* gives a spanning tree with cost ≥ cost(MST). So cost(H*) ≥ cost(MST). The full walk of MST (visiting each edge twice) has cost 2·cost(MST). Shortcutting (by triangle inequality) only reduces cost. So cost(approx) ≤ 2·cost(MST) ≤ 2·cost(H*)."},{"type":"heading","content":"Christofides' Algorithm (3/2-Approximation)"},{"type":"paragraph","content":"For metric TSP, Christofides' algorithm achieves a better approximation ratio of 3/2: (1) Find MST T; (2) Find minimum-weight perfect matching M on odd-degree vertices of T; (3) Combine T and M to form an Eulerian graph; (4) Find Eulerian circuit; (5) Convert to Hamiltonian cycle by shortcutting. This gives cost ≤ 3/2 × optimal."}]}}]}],"loading":false,"error":null}}}

Q3Design and Analysis of Algorithms

Question

Answer