Complete collection of important PYQ topics with simple tables and explanations.
Master's Theorem provides a fast method to solve recurrence relations of the form \(T(n) = aT(n/b) + f(n)\), where \(a \ge 1\) and \(b > 1\). It compares \(f(n)\) to the critical polynomial \(n^{\log_b a}\).
| Feature | Recursion | Iteration |
|---|---|---|
| Definition | A function calls itself to solve smaller instances of the problem. | Uses looping constructs (for, while) to repeat a block of code. |
| Memory Overhead | High overhead due to maintaining the system call stack. Can cause Stack Overflow. | Very low memory overhead, runs in constant space \(O(1)\). |
| Speed | Generally slower because of function call overhead. | Generally faster. |
| Code Structure | Shorter, more elegant, and closer to mathematical formulations. | Can be longer and slightly more complex to write for tree/graph traversals. |
| Feature | Prim's Algorithm | Kruskal's Algorithm |
|---|---|---|
| Approach | Builds a single tree, growing it by adding the cheapest edge from the tree to an unvisited vertex. | Maintains a forest of trees, sorting all edges and adding the cheapest edge that doesn't form a cycle. |
| Data Structure | Uses a Min-Priority Queue (or Heap). | Uses a Disjoint-Set (Union-Find). |
| Best for | Dense graphs (many edges). | Sparse graphs. |
The Fractional Knapsack problem allows taking fractions of items to maximize profit.
Time Complexity: \(O(n \log n)\) dominated by the sorting step.
Goal: Maximize profit by scheduling jobs (each taking 1 unit time) before their deadlines.
Time Complexity: \(O(n^2)\) worst case due to nested loops searching for free slots.
| Feature | Dynamic Programming (DP) | Divide & Conquer (D&C) |
|---|---|---|
| Subproblems | Subproblems are dependent and overlap (they share sub-subproblems). | Subproblems are completely independent and non-overlapping. |
| Memory (Memoization) | Stores results of subproblems in a table to avoid redundant calculations. | Does not store results; recalculates them every time. |
| Approach | Usually Bottom-Up. | Always Top-Down. |
| Examples | 0/1 Knapsack, Matrix Chain Multiplication, Floyd-Warshall. | Merge Sort, Quick Sort, Binary Search. |
In the 0/1 Knapsack problem, items cannot be broken into fractions. The Greedy method makes irrevocable local optimal choices by picking items based on the highest profit-to-weight ratio.
If a high-ratio item consumes almost all the capacity but leaves a small, unusable gap, it might prevent picking a combination of slightly lower-ratio items that perfectly fill the knapsack and yield a higher total profit. DP explores all combinations to guarantee optimality.
The Floyd-Warshall Algorithm uses Dynamic Programming to find the All-Pairs Shortest Path in a weighted graph (even with negative weights, provided there are no negative cycles).
It works by considering every vertex as an intermediate vertex. For a graph with \(V\) vertices, it maintains a 2D distance matrix. In the \(k\)-th iteration, it checks if a path going through vertex \(k\) is shorter than the currently known path:
\(D^{(k)}[i][j] = \min( D^{(k-1)}[i][j], D^{(k-1)}[i][k] + D^{(k-1)}[k][j] ) \)
Time Complexity: \(O(V^3)\) due to three nested loops.
| Feature | Dijkstra's Algorithm | Bellman-Ford Algorithm |
|---|---|---|
| Paradigm | Greedy approach (picks the closest unvisited vertex). | Dynamic Programming approach (relaxes all edges iteratively). |
| Negative Edge Weights | Fails with negative weights. | Fully supports negative edge weights. |
| Negative Cycle Detection | Cannot handle or detect negative cycles. | Can detect negative weight cycles (if distances update on the \(V\)-th iteration). |
| Time Complexity | \(O(E \log V)\) (with Min-Heap). | \(O(V \cdot E)\). |
The Max-Flow Min-Cut Theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is exactly equal to the total capacity of the minimum cut separating the source and the sink.
A "cut" partitions the network into two sets of vertices (one containing the source, one containing the sink). The theorem proves that the "bottleneck" (minimum cut) of the network strictly dictates the maximum flow it can handle.
| Feature | Backtracking | Branch and Bound |
|---|---|---|
| Objective | Finds all feasible solutions to a constraint satisfaction problem (e.g., N-Queens). | Finds the single optimal solution to an optimization problem (e.g., TSP). |
| Search Technique | Explores state-space tree using Depth-First Search (DFS). | Uses Breadth-First Search (BFS) or Best-First Search. |
| Memory Usage | Requires much less memory \(O(V)\) due to the DFS stack. | Requires exponential memory to store the active queue of nodes. |
The Graph Coloring Problem asks whether we can color all vertices of a graph using at most \(m\) colors such that no two adjacent vertices (vertices connected by a direct edge) have the same color. It is typically solved using Backtracking (DFS). The smallest number of colors needed is called the Chromatic Number.
Cook's Theorem (or Cook-Levin Theorem) states that the Boolean Satisfiability Problem (SAT) is NP-Complete. It was the very first problem proven to be NP-Complete, forming the foundation for proving other problems are NP-Complete through polynomial reductions.
Polynomial Reducibility (\(A \le_p B\)) means there is a polynomial-time algorithm that transforms any instance of problem A into an instance of problem B. Therefore, if we can solve problem B in polynomial time, we can also solve problem A in polynomial time.
Answer: Best case \(O(1)\), Average/Worst case \(O(\log n)\). It is a polynomial-time algorithm.
Answer: False. An adjacency matrix shows direct 1-step edges. A path matrix (transitive closure) shows if a path of any length exists between vertices.
Answer: \(O(V \cdot E^2)\).
Answer: Depth-First Search (DFS).
Answer: 92 total solutions (or 12 fundamental unique solutions if symmetry is excluded).
Answer: Queue (FIFO).
Answer: Stack (LIFO).
Answer: A Clique is a subset of vertices in an undirected graph such that every two distinct vertices in the subset are connected by a direct edge (a complete subgraph).