Coursify

Design and Analysis of Algorithms (DAA)

PYQ Analysis & Exam Preparation — Module 5

25 mins

A strategic analysis of exam questions for Advanced Topics (2023–2024). This module is extremely focused on two core areas: Randomized Algorithms (specifically Randomized Quick Sort) and Approximation Algorithms for NP-Hard problems.

Learning Goals

  • Understand the mechanics and advantages of Randomized Algorithms.
  • Memorize the algorithm and expected time complexity for Randomized Quick Sort.
  • Explain the necessity of Approximation Algorithms and trace the Vertex Cover 2-approximation.

The Exam Blueprint: Module 5 PYQ Deep Analysis (2023–2024)

An analysis of the 4 exam questions spanning 2023 to 2024 reveals that Module 5 is the shortest but highly concentrated. Examiners test exactly two concepts: Randomized Algorithms and Approximation Algorithms.

Complete PYQ Table (4 Questions)

YearQ#MarksTopicType
2024Q1j2Randomized algorithms utilize random choicesMCQ
2023Q914Short notes: Randomized algorithms (among others)Theory
2024Q9a7Randomized Quick Sort: Algorithm & ComplexityTheory+Num
2024Q9b7Approximation Algorithms + Vertex CoverTheory

Total marks tracked: ~30 marks across 2 years.

Topic Heat Map

Topic20232024Total Marks
Randomized Algorithms & Quick Sort7M ✅9M ✅16M
Approximation Algorithms (Vertex Cover)—7M ✅7M

The 2 Guaranteed Question Types

1. 🔴 Randomized Quick Sort (7M) You will be asked to define what a randomized algorithm is, write the pseudocode for Randomized Quick Sort (specifically focusing on the RANDOMIZED-PARTITION function), and state its expected time complexity.

2. 🟠 Approximation Algorithms for NP-Hard (7M) You must define why approximation algorithms are necessary (because NP-Hard problems take exponential time) and provide the standard 2-approximation algorithm for the Vertex Cover problem.

Algorithm 1: Randomized Quick Sort

  1. 1
    Step 1

    If the array bounds p and r are such that p < r, proceed. Otherwise, return.

  2. 2
    Step 2

    Instead of using A[r] as the pivot directly, pick a random index i between p and r. Swap A[i] with A[r]. i = RANDOM(p, r) \ Exchange A[i] with A[r] \ Return PARTITION(A, p, r)

  3. 3
    Step 3

    Execute the standard Lomuto partition scheme using the newly swapped A[r] as the pivot.

  4. 4
    Step 4

    Recursively sort the left subarray (p to q-1) and the right subarray (q+1 to r).

  5. 5
    Step 5

    Worst Case: O(n2)O(n^2) (Still theoretically possible if the random number generator gets incredibly unlucky every time, though highly improbable). Expected / Average Case: O(nlog⁡n)O(n \log n) (Because the random pivot ensures balanced partitions on average).

Algorithm 2: Vertex Cover Approximation

  1. 1
    Step 1

    Create an empty set C which will hold the vertices for our vertex cover.

  2. 2
    Step 2

    Create a set E' containing all the edges of the given graph G.

  3. 3
    Step 3

    While E' is not empty, pick an arbitrary edge (u, v) from E'.

  4. 4
    Step 4

    Add both endpoints u and v to our cover set C.

  5. 5
    Step 5

    Remove ALL edges from E' that are attached to either u or v.

  6. 6
    Step 6

    Repeat steps 3-5 until E' is entirely empty. Return the set C.

Knowledge Check

Question 1 of 2
Q1Single choice

Randomized algorithms make use of:

High-Yield Subjective Bank: Structure Your Answers

####Approximation Algorithms (7 Marks)**

Answer structure:

  1. What are Approximation Algorithms? (2M)

    • They are algorithms designed to find near-optimal solutions to complex optimization problems in polynomial time.
    • They do not guarantee the exact global optimum, but they guarantee that the solution will be within a specific mathematically proven bound (approximation ratio) of the optimal solution.

  2. Why are they important for NP-Hard problems? (2.5M)

    • NP-Hard optimization problems (like TSP, Vertex Cover, Knapsack) require exponential time O(2n)O(2^n) to find the exact optimal solution using brute force or backtracking.
    • For real-world applications with large inputs (large nn), exponential time is computationally impossible (intractable).
    • Approximation algorithms allow us to get a "good enough" solution in very fast, tractable polynomial time O(nk)O(n^k).

  3. Application to Vertex Cover (2.5M)

    • Write out the 2-approximation algorithm (shown in the Step-By-Step block above).
    • State the ratio: "This algorithm guarantees a vertex cover that is at most exactly twice the size of the theoretical minimum vertex cover. The approximation ratio ρ=2\rho = 2."

####Describe Randomized Algorithms (Part of 7 Marks)**

Answer structure:

  1. Definition: A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic. It uses a pseudo-random number generator to decide the next step during its execution.
  2. Las Vegas vs Monte Carlo:
    • Las Vegas Algorithm: Always produces the correct answer, but its running time varies randomly (e.g., Randomized Quick Sort).
    • Monte Carlo Algorithm: Has a deterministic running time, but there is a small probability that it might produce an incorrect answer (e.g., Karger's Min-Cut, Miller-Rabin primality test).
  3. Advantage: It prevents "malicious" worst-case inputs from consistently degrading performance. In Randomized Quick Sort, no specific input array can force O(n2)O(n^2) time every single time the algorithm runs.

Previous

Next