UGC NET Computer Science Data Structures and Algorithms Syllabus

What is the time complexity of binary search and what precondition does it require?

O(log n). It requires the array (or list) to be sorted.

Differentiate between time complexity and space complexity.

Time complexity measures how the running time grows with input size n; space complexity measures how the auxiliary/total memory used grows with n. Both are typically expressed in asymptotic notation.

Define Big-O, Big-Omega, and Big-Theta asymptotic notations.

Big-O (O) is an asymptotic upper bound; Big-Omega (Ω) is an asymptotic lower bound; Big-Theta (Θ) is a tight bound meaning the function is both O and Ω of g(n).

Order these growth rates from slowest to fastest: O(n!), O(n log n), O(log n), O(2^n), O(n²), O(1), O(n).

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!).

What is the difference between little-o and Big-O notation?

Big-O (f = O(g)) allows f and g to grow at the same rate (bound may be tight). Little-o (f = o(g)) is a strictly looser upper bound: f grows strictly slower than g, i.e., f(n)/g(n) → 0 as n → ∞.

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

Compare f(n) with n^(log_b a): Case 1, if f(n)=O(n^(log_b a−ε)) then T(n)=Θ(n^(log_b a)); Case 2, if f(n)=Θ(n^(log_b a)) then T(n)=Θ(n^(log_b a) log n); Case 3, if f(n)=Ω(n^(log_b a+ε)) and regularity holds then T(n)=Θ(f(n)).

Solve the recurrence T(n) = 2T(n/2) + O(n) using the Master Theorem.

Here a=2, b=2, so n^(log_b a)=n; f(n)=Θ(n) matches Case 2, giving T(n)=Θ(n log n) (e.g., merge sort).

What are the three steps of the Divide and Conquer paradigm?

Divide the problem into subproblems, Conquer the subproblems by solving them recursively, and Combine the subproblem solutions into the solution for the original problem.

What two properties must a problem have to be solvable efficiently by Dynamic Programming?

Optimal substructure (an optimal solution is built from optimal solutions of subproblems) and overlapping subproblems (the same subproblems recur, so results can be stored/memoized).

What is the difference between memoization and tabulation in dynamic programming?

Memoization is top-down: recursion with caching of results as subproblems are encountered. Tabulation is bottom-up: iteratively filling a table from base cases up to the final answer.

What is the recurrence for the 0/1 Knapsack dynamic programming solution?

K(i,w) = max( K(i−1,w), value[i] + K(i−1, w−weight[i]) ) if weight[i] ≤ w, else K(i,w)=K(i−1,w). Time complexity O(nW).

What defines a greedy algorithm, and what property guarantees its correctness?

A greedy algorithm makes the locally optimal choice at each step. It yields a globally optimal solution when the problem exhibits the greedy-choice property and optimal substructure.

Give two classic problems solved optimally by greedy algorithms.

Examples: Huffman coding (optimal prefix codes), Kruskal's and Prim's minimum spanning tree, Dijkstra's shortest path (non-negative weights), and fractional knapsack / activity selection.

What is backtracking and how does it differ from brute force?

Backtracking incrementally builds candidates and abandons (prunes) a partial candidate as soon as it cannot lead to a valid solution. Unlike pure brute force, it prunes infeasible branches early, exploring the state-space tree more efficiently.

Name two classic problems typically solved with backtracking.

N-Queens, Sudoku, graph coloring, the Hamiltonian path/cycle problem, and subset-sum.

How does Branch and Bound differ from backtracking?

Both explore a state-space tree, but Branch and Bound is mainly for optimization problems: it computes a bound (best possible value) at each node and prunes branches whose bound cannot beat the current best solution. Backtracking is mainly for feasibility/constraint satisfaction using DFS.

What is a comparison tree (decision tree) and what does it model?

A binary tree modeling the sequence of comparisons an algorithm makes; each internal node is a comparison and each leaf is an outcome. It is used to derive lower bounds on comparison-based algorithms.

Using the comparison-tree model, what is the lower bound on comparisons for any comparison-based sorting algorithm?

Ω(n log n). A comparison tree sorting n elements must have at least n! leaves, so its height is at least log₂(n!) = Ω(n log n).

What is a lower bound proved through reduction?

A technique that proves problem B is at least as hard as problem A by transforming A into B: if A has known lower bound L and reduces to B in less time, then B also has lower bound L. It transfers hardness from a known problem to a new one.

Describe Breadth-First Search (BFS): its data structure, order of visiting, and a key application.

BFS explores a graph level by level using a queue, visiting all neighbors at the current distance before moving deeper. It runs in O(V+E) and finds shortest paths (fewest edges) in an unweighted graph.

Describe Depth-First Search (DFS): its data structure and two key applications.

DFS explores as deep as possible before backtracking, using a stack (or recursion). It runs in O(V+E) and is used for topological sorting, detecting cycles, and finding connected/strongly-connected components.

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

It computes single-source shortest paths in a weighted graph. Restriction: edge weights must be non-negative. With a binary heap it runs in O((V+E) log V).

Which shortest-path algorithm handles negative edge weights, and what is its complexity?

The Bellman-Ford algorithm. It runs in O(V·E) and can also detect negative-weight cycles.

What does the Floyd-Warshall algorithm compute and what is its time complexity?

All-pairs shortest paths in a weighted graph (allowing negative edges but no negative cycles), using dynamic programming. Time complexity O(V³).

State the max-flow min-cut theorem.

In a flow network, the maximum value of a flow from source to sink equals the minimum capacity over all s-t cuts (the minimum cut).

What is the Ford-Fulkerson method, and what is the Edmonds-Karp refinement's complexity?

Ford-Fulkerson finds max flow by repeatedly augmenting flow along augmenting paths in the residual graph. Edmonds-Karp chooses the shortest augmenting path via BFS, giving O(V·E²) time.

What is a Minimum Spanning Tree (MST), and how many edges does it have for V vertices?

A spanning tree (connected, acyclic subgraph touching all vertices) of minimum total edge weight. For a connected graph with V vertices, any spanning tree has exactly V−1 edges.

Compare Kruskal's and Prim's MST algorithms.

Kruskal's sorts edges and adds the smallest edge that doesn't form a cycle (using Union-Find), O(E log E); good for sparse graphs. Prim's grows a single tree from a start vertex, always adding the cheapest crossing edge (using a priority queue), O(E log V); good for dense graphs.

Define the complexity classes P and NP.

P is the class of decision problems solvable by a deterministic Turing machine in polynomial time. NP is the class of decision problems whose 'yes' answers can be verified in polynomial time (equivalently, solvable in polynomial time by a nondeterministic machine).

What does it mean for a problem to be NP-complete?

A problem is NP-complete if it is in NP and every problem in NP reduces to it in polynomial time (NP-hard). It is among the hardest problems in NP; if any NP-complete problem is in P, then P = NP.

What is a polynomial-time (many-one/Karp) reduction and why is it used in NP-completeness proofs?

A polynomial-time transformation of instances of problem A into instances of problem B such that A's answer is 'yes' iff B's is 'yes'. It shows B is at least as hard as A; used to prove NP-hardness by reducing a known NP-complete problem to B.

What was the first problem proved NP-complete, and by which theorem?

Boolean satisfiability (SAT), proved NP-complete by the Cook-Levin theorem.

What does Euclid's algorithm compute and what is its recurrence?

It computes the greatest common divisor (GCD) of two integers using gcd(a, b) = gcd(b, a mod b), with gcd(a, 0) = a. It runs in O(log(min(a,b))) divisions.

What does the Extended Euclidean Algorithm find in addition to the GCD?

It finds integers x and y satisfying Bézout's identity ax + by = gcd(a, b); this is used to compute modular multiplicative inverses (when gcd(a,m)=1).

What is the time complexity of naive polynomial multiplication versus FFT-based multiplication of two degree-n polynomials?

Naive (schoolbook) multiplication: O(n²). FFT-based multiplication: O(n log n).

What does the Fast Fourier Transform (FFT) compute, and what is its key idea and complexity?

The FFT computes the Discrete Fourier Transform in O(n log n) instead of O(n²), using divide-and-conquer that splits the polynomial into even- and odd-indexed coefficients and evaluates at the nth roots of unity.

What problem does the KMP (Knuth-Morris-Pratt) string-matching algorithm solve and what is its complexity?

It finds all occurrences of a pattern of length m in a text of length n in O(n + m) time by precomputing a prefix/failure function so it never re-examines text characters after a mismatch.

What is the worst-case and average-case complexity of the Rabin-Karp string-matching algorithm?

Average/expected: O(n + m) using rolling hashes. Worst case: O(nm) due to hash collisions (spurious hits requiring verification).

In parallel computing, what does Brent's theorem / the work-span model say about runtime on p processors?

If an algorithm performs total work W (T₁) and has span (critical path) T∞, then the time on p processors is bounded by Tp ≤ W/p + T∞, and at best Tp ≥ max(W/p, T∞).

What is a parallel approach to merging/sorting, and what time can sorting achieve with enough processors?

Parallel sorting networks (e.g., bitonic sort) and parallel merge sort merge sorted halves concurrently. Bitonic sort runs in O(log²n) parallel time using O(n log²n) comparisons; the AKS network achieves O(log n) depth.

What is an approximation algorithm and what is meant by its approximation ratio?

A polynomial-time algorithm for an optimization problem (often NP-hard) that returns a near-optimal solution. The approximation ratio ρ bounds how far the result is from optimal: for minimization, ALG ≤ ρ·OPT (ρ ≥ 1).

What approximation ratio does the standard greedy/2-approximation give for the metric Travelling Salesman and Vertex Cover problems?

Vertex Cover: a 2-approximation via maximal matching. Metric TSP: a 2-approximation via MST doubling, improved to 3/2 by Christofides' algorithm.

What is the difference between a Las Vegas and a Monte Carlo randomized algorithm?

A Las Vegas algorithm always produces a correct result but its running time is random (e.g., randomized quicksort). A Monte Carlo algorithm has bounded running time but may produce an incorrect result with some bounded probability.

Why is randomized quicksort preferred over deterministic quicksort?

Random pivot selection makes the expected running time O(n log n) regardless of input order, avoiding the O(n²) worst case that adversarial or already-sorted inputs cause in deterministic quicksort.

What is the time complexity of heap operations build-heap, insert, and extract-max?

Build-heap: O(n) (not O(n log n)). Insert: O(log n). Extract-max/min: O(log n).

What is the difference between a graph cycle detection approach in directed versus undirected graphs using DFS?

In a directed graph, a cycle exists if DFS finds a back edge to a vertex currently on the recursion stack (gray vertex). In an undirected graph, a cycle exists if DFS encounters an already-visited vertex that is not the immediate parent.

What is a topological sort and on what kind of graph is it defined?

A linear ordering of vertices of a Directed Acyclic Graph (DAG) such that for every directed edge (u,v), u appears before v. It can be produced via DFS finish times or Kahn's algorithm (repeatedly removing in-degree-zero vertices).

What is the Longest Common Subsequence (LCS) problem and its DP time complexity?

Given two sequences, LCS finds the longest subsequence common to both (not necessarily contiguous). The dynamic programming solution runs in O(m·n) time and space.

What does NP-hard mean, and how does it differ from NP-complete?

NP-hard means a problem is at least as hard as every problem in NP (every NP problem reduces to it), but it need not be in NP and need not be a decision problem. NP-complete = NP-hard AND in NP.