UGC NET Computer Science Data Structures and Algorithms Flashcards

24 sample cards from the Data Structures and Algorithms deck

Sampled from the end of the deck, so these are different cards from the ones shown on the syllabus page.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

What this deck covers

Data Structures and Algorithms flashcards FAQ