DAA Exam Prep Q&A Bank

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}\).

• Case 1: If \(f(n) = O(n^{\log_b a - \epsilon})\) (grows polynomially slower), then \(T(n) = \Theta(n^{\log_b a})\).
• Case 2: If \(f(n) = \Theta(n^{\log_b a})\) (grows at the same rate), then \(T(n) = \Theta(n^{\log_b a} \log n)\).
• Case 3: If \(f(n) = \Omega(n^{\log_b a + \epsilon})\) (grows polynomially faster) AND \(a f(n/b) \le c f(n)\) for \(c < 1\), then \(T(n) = \Theta(f(n))\).

• Big-O (\(O\)): Asymptotic Upper Bound. The algorithm will not take more time than this. (Worst case)
• Omega (\(\Omega\)): Asymptotic Lower Bound. The algorithm will take at least this much time. (Best case)
• Theta (\(\Theta\)): Asymptotic Tight Bound. The algorithm's time grows exactly at this rate. (Average/Exact case)
• Little Omega (\(\omega\)): A strictly loose lower bound (grows infinitely faster).

The Fractional Knapsack problem allows taking fractions of items to maximize profit.

1. Calculate the ratio \(Profit / Weight\) for each item.
2. Sort all items in descending order based on this ratio.
3. Initialize total profit = 0.
4. Iterate through the sorted items:
   • If the item's weight \(\le\) remaining capacity, add the whole item and update profit and capacity.
   • If the item's weight \(>\) remaining capacity, add a fraction of the item that completely fills the knapsack, update profit, and break.

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.

1. Sort all jobs in descending order of their profits.
2. Find the maximum deadline among all jobs to determine the maximum number of time slots available.
3. Initialize an array of slots to track free/occupied time slots.
4. For each job (from highest profit to lowest):
   • Start from its deadline and check slots backwards down to 1.
   • Assign the job to the first available free slot found.

Time Complexity: \(O(n^2)\) worst case due to nested loops searching for free slots.

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.

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.

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.

• P (Polynomial Time): Decision problems that can be solved in polynomial time by a deterministic Turing machine.
• NP (Non-Deterministic Polynomial Time): Decision problems where a proposed solution (certificate) can be verified as correct in polynomial time.
• NP-Hard: Problems that are at least as hard as the hardest problems in NP. Any problem in NP can be reduced to an NP-Hard problem in polynomial time.
• NP-Complete: The intersection of NP and NP-Hard. A problem is NP-Complete if it is in NP AND it is NP-Hard. E.g., Circuit-SAT, TSP.

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.

• Heap Sort: \(O(n \log n)\) in Best, Average, and Worst cases.
• Quick Sort: Best/Average case is \(O(n \log n)\). Worst case is \(O(n^2)\) (occurs when the array is already sorted).
• Merge Sort: \(O(n \log n)\) in all cases.

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).