GATE CS & IT Engineering Algorithms Syllabus

In separate chaining, what is the expected search time under simple uniform hashing?

Expected time is $O(1 + \alpha)$, where $\alpha$ is the load factor. With $\alpha = O(1)$ (table size proportional to $n$), search, insert, and delete are $O(1)$ on average.

Define time complexity (asymptotic) and what Big-O notation represents.

Time complexity describes how an algorithm's running time grows with input size $n$. Big-O, $O(f(n))$, gives an asymptotic upper bound: $T(n) = O(f(n))$ if $T(n) \leq c \cdot f(n)$ for some constant $c > 0$ and all $n \geq n_0$.

Define Big-Omega $\Omega$ and Big-Theta $\Theta$ notation.

$\Omega(f(n))$ is an asymptotic lower bound: $T(n) \geq c f(n)$ for large $n$. $\Theta(f(n))$ is a tight bound: $T(n) = \Theta(f(n))$ iff $T(n) = O(f(n))$ and $T(n) = \Omega(f(n))$ simultaneously.

Order these common complexities from fastest- to slowest-growing: $O(n^{2})$, $O(1)$, $O(n \log n)$, $O(2^{n})$, $O(\log n)$, $O(n)$.

$$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^{2}) < O(2^{n})$$

State the Master Theorem for recurrences of the form $T(n) = aT(n/b) + f(n)$.

Let $c = \log_b a$. Then: (1) if $f(n) = O(n^{c-\epsilon})$, $T(n) = \Theta(n^{c})$; (2) if $f(n) = \Theta(n^{c})$, $T(n) = \Theta(n^{c} \log n)$; (3) if $f(n) = \Omega(n^{c+\epsilon})$ and regularity holds, $T(n) = \Theta(f(n))$.

Define space complexity and distinguish auxiliary space from total space.

Space complexity is the total memory an algorithm uses as a function of input size $n$. Total space = input space + auxiliary space; auxiliary space is the extra/temporary space used beyond the input itself.

What is the space complexity of a recursive algorithm with recursion depth $d$?

At least $O(d)$ due to the call stack, where $d$ is the maximum recursion depth. For example, recursive Binary Search uses $O(\log n)$ stack space.

Describe the greedy algorithm paradigm and the two properties a problem must have for it to be optimal.

A greedy algorithm builds a solution by making the locally optimal choice at each step. For correctness it needs (1) the greedy-choice property (a global optimum can be reached by local choices) and (2) optimal substructure.

Give two classic problems solvable optimally by greedy algorithms.

Examples: Activity Selection (interval scheduling), Huffman coding, Fractional Knapsack, and minimum spanning tree algorithms (Kruskal's, Prim's). Note: 0/1 Knapsack is NOT solved optimally by greedy.

Why does the greedy approach fail for the 0/1 Knapsack problem but work for Fractional Knapsack?

In Fractional Knapsack you can take fractions, so choosing highest value-to-weight ratio first is optimal. In 0/1 Knapsack items are indivisible, so the greedy ratio choice can be suboptimal; it requires dynamic programming instead.

Define dynamic programming and the two properties a problem must satisfy to use it.

Dynamic programming solves problems by combining solutions to overlapping subproblems, storing each subproblem result to avoid recomputation. It requires (1) optimal substructure and (2) overlapping subproblems.

Distinguish memoization (top-down) from tabulation (bottom-up) in dynamic programming.

Memoization is top-down recursion that caches results as subproblems are encountered. Tabulation is bottom-up, iteratively filling a table from base cases upward. Both avoid recomputation; tabulation avoids recursion overhead.

What are the time and space complexities of the classic 0/1 Knapsack DP with $n$ items and capacity $W$?

Time complexity is $O(nW)$ and space complexity is $O(nW)$ (reducible to $O(W)$ with a 1D array). This is pseudo-polynomial since $W$ is a numeric value, not the input size in bits.

How does dynamic programming differ from divide-and-conquer?

Both break problems into subproblems, but divide-and-conquer subproblems are independent (non-overlapping), while DP subproblems overlap and their solutions are stored/reused. Merge Sort is divide-and-conquer; Fibonacci with memoization is DP.

State the three steps of the divide-and-conquer paradigm.

(1) Divide the problem into smaller subproblems; (2) Conquer each subproblem by solving it recursively; (3) Combine the subproblem solutions into the solution for the original problem.

Give the recurrence and complexity of finding both min and max using divide-and-conquer.

$$T(n) = 2T\!\left(\frac{n}{2}\right) + 2$$ which yields about $\frac{3n}{2} - 2$ comparisons, i.e. $O(n)$ time.

Describe Breadth First Search (BFS), the data structure it uses, and its order of visiting.

BFS explores a graph level by level from a source, visiting all neighbors at the current depth before moving deeper. It uses a queue (FIFO) and marks vertices visited to avoid revisiting.

State the time and space complexity of BFS on a graph with $V$ vertices and $E$ edges.

Time complexity is $O(V + E)$ using adjacency lists. Space complexity is $O(V)$ for the queue and visited array.

What key property does BFS guarantee in an unweighted graph?

BFS finds the shortest path (minimum number of edges) from the source to every reachable vertex in an unweighted graph.

Describe Depth First Search (DFS), the data structure it uses, and its strategy.

DFS explores as far as possible along each branch before backtracking. It uses a stack (explicit, or implicit via recursion) and marks vertices visited. Time complexity $O(V+E)$, space $O(V)$.

Name three classic applications of DFS.

Topological sorting of a DAG, detecting cycles in a graph, finding connected components / strongly connected components, and classifying edges (tree, back, forward, cross).

What does Kruskal's algorithm compute, and what is its greedy strategy?

Kruskal's algorithm finds a Minimum Spanning Tree (MST). It sorts all edges by weight ascending and adds the next smallest edge that does not form a cycle, using a Union-Find (disjoint-set) structure to detect cycles.

State the time complexity of Kruskal's algorithm.

$O(E \log E)$ (or equivalently $O(E \log V)$) dominated by sorting the edges; the Union-Find operations add nearly $O(E \,\alpha(V))$ where $\alpha$ is the inverse Ackermann function.

What does Prim's algorithm compute, and what is its greedy strategy?

Prim's algorithm finds a Minimum Spanning Tree. It grows the MST from a starting vertex, repeatedly adding the minimum-weight edge that connects a vertex in the tree to a vertex outside it.

State the time complexity of Prim's algorithm with a binary heap versus an adjacency matrix.

With a binary heap and adjacency list: $O(E \log V)$. With an adjacency matrix (simple array): $O(V^{2})$. With a Fibonacci heap: $O(E + V \log V)$.

Compare when to prefer Kruskal's versus Prim's algorithm.

Kruskal's ($O(E \log E)$) is better for sparse graphs (few edges). Prim's with an adjacency matrix ($O(V^{2})$) is better for dense graphs (many edges). Both produce a correct MST.

What problem does Dijkstra's algorithm solve, and what is its key restriction?

Dijkstra's computes single-source shortest paths in a weighted graph. Its key restriction is that all edge weights must be non-negative; it fails with negative edges.

State the time complexity of Dijkstra's algorithm with a binary heap and with a Fibonacci heap.

With a binary min-heap: $O((V + E)\log V)$, often written $O(E \log V)$. With a Fibonacci heap: $O(E + V \log V)$.

What is the greedy relaxation step in Dijkstra's algorithm?

For an edge $(u,v)$ with weight $w$, relaxation updates: if $d[u] + w(u,v) < d[v]$, set $d[v] = d[u] + w(u,v)$. Dijkstra repeatedly extracts the unvisited vertex with smallest $d$ and relaxes its edges.

What problem does the Bellman-Ford algorithm solve, and what advantage does it have over Dijkstra's?

Bellman-Ford computes single-source shortest paths and, unlike Dijkstra's, handles negative edge weights. It can also detect negative-weight cycles reachable from the source.

State the time complexity of Bellman-Ford and how it detects a negative cycle.

Time complexity is $O(V \cdot E)$: it relaxes all $E$ edges $V-1$ times. To detect a negative cycle, it performs one more relaxation pass; if any distance can still be reduced, a negative-weight cycle exists.