SELECTED TOPICS

FULL EXAM-READY NOTES + CODE + SOLVED QUESTIONS

UNIT V – SELECTED TOPICS (08 Lectures)

FULL EXAM-READY NOTES + CODE + SOLVED QUESTIONS
(Score 90–100/100 Guaranteed!)

1. FAST FOURIER TRANSFORM (FFT) – 15 Marks

Most Asked Question
Compute DFT of sequence: x = [1, 2, 3, 4] using Radix-2 FFT
Show butterfly diagram and final result.

Butterfly Diagram (Draw This – 8 Marks!)

Input: 1   2   3   4
       |   |   |   |
   W^0  |   W^0 |
       1+3     2+4
         |       |
       W^0     W^1
         4       6
           \   /
            \ /
           10  -2j+2
           X(0) X(1) X(2) X(3)

Final Answer
X(0) = 10
X(1) = -2 + 2j
X(2) = -2
X(3) = -2 – 2j

C Code – Cooley-Tukey FFT

#include<stdio.h>
#include<math.h>
#define PI 3.14159265

void fft(double real[], double imag[], int n) {
    if(n <= 1) return;

    double even_r[n/2], even_i[n/2], odd_r[n/2], odd_i[n/2];
    for(int i=0; i<n/2; i++) {
        even_r[i] = real[2*i];   even_i[i] = imag[2*i];
        odd_r[i]  = real[2*i+1]; odd_i[i]  = imag[2*i+1];
    }

    fft(even_r, even_i, n/2);
    fft(odd_r,  odd_i,  n/2);

    for(int k=0; k<n/2; k++) {
        double angle = -2*PI*k/n;
        double wk_real = cos(angle);
        double wk_imag = sin(angle);
        double t_real = wk_real*odd_r[k] - wk_imag*odd_i[k];
        double t_imag = wk_real*odd_i[k] + wk_imag*odd_r[k];

        real[k]     = even_r[k] + t_real;
        imag[k]     = even_i[k] + t_imag;
        real[k+n/2] = even_r[k] - t_real;
        imag[k+n/2] = even_i[k] - t_imag;
    }
}

int main() {
    double real[] = {1,2,3,4};
    double imag[] = {0,0,0,0};
    int n = 4;

    fft(real, imag, n);
    printf("DFT using FFT:\n");
    for(int i=0; i<n; i++)
        printf("X(%d) = %.2f + %.2fi\n", i, real[i], imag[i]);
}

Output:

X(0) = 10.00 + 0.00i
X(1) = -2.00 + 2.00i
X(2) = -2.00 + 0.00i
X(3) = -2.00 - 2.00i

2. STRING MATCHING – KMP ALGORITHM (15 Marks)

Question:
Text: "ABABDABACDABABCABAB"
Pattern: "ABABCABAB"
Find all occurrences using KMP.

LPS Array (Draw This!)

Pattern	A	B	A	B	C	A	B	A	B
Index	0	1	2	3	4	5	6	7	8
LPS	0	0	1	2	0	1	2	3	4

Match at position = 10

C Code – KMP

#include<stdio.h>
#include<string.h>

void computeLPS(char pat[], int M, int lps[]) {
    int len = 0; lps[0] = 0;
    for(int i=1; i<M; i++) {
        if(pat[i] == pat[len])
            lps[i] = ++len;
        else {
            if(len != 0) { i--; len = lps[len-1]; }
            else lps[i] = 0;
        }
    }
}

void KMP(char text[], char pat[]) {
    int N = strlen(text), M = strlen(pat);
    int lps[M];
    computeLPS(pat, M, lps);

    int i=0, j=0;
    while(i < N) {
        if(pat[j] == text[i]) { i++; j++; }
        if(j == M) {
            printf("Pattern found at index %d\n", i-j);
            j = lps[j-1];
        }
        else if(i < N && pat[j] != text[i]) {
            if(j != 0) j = lps[j-1];
            else i++;
        }
    }
}

int main() {
    char text[] = "ABABDABACDABABCABAB";
    char pat[] = "ABABCABAB";
    KMP(text, pat);
}

Output: Pattern found at index 10

3. THEORY OF NP-COMPLETENESS (10 Marks)

Key Points to Write:
- P: Polynomial time solvable
- NP: Verifiable in polynomial time
- NP-Hard: At least as hard as hardest NP problem
- NP-Complete: NP + NP-Hard
- First NP-Complete: SAT (Cook’s Theorem)
- Reduction: 3-SAT → Vertex Cover → Clique → Hamiltonian Cycle

Cook’s Theorem: SAT is NP-Complete

Most Asked Reductions:
- 3-SAT ≤ₚ Vertex Cover
- Vertex Cover ≤ₚ Dominating Set
- Hamiltonian Cycle ≤ₚ TSP

4. APPROXIMATION ALGORITHMS (10 Marks)

Vertex Cover – 2-Approximation

// Greedy: Pick edge, add both vertices, remove all incident edges
// Ratio = 2 × OPT

TSP with Triangle Inequality – 2-Approx (Christofides)
1. MST
2. Minimum weight perfect matching on odd-degree vertices
3. Euler tour → shortcut → Hamiltonian cycle
Ratio = 1.5

5. RANDOMIZED ALGORITHMS (8 Marks)

Karger’s Min-Cut

// Randomly contract edges until 2 vertices remain
// Probability of finding min-cut ≥ 1/(n choose 2)
// Run O(n² log n) times → high probability

FINAL EXAM CHEAT SHEET (Draw in 5 mins!)

Topic	Key Result	Code/Diagram Needed?
FFT	O(n log n)	Butterfly diagram
KMP	O(n+m) preprocessing + search	LPS table
NP-Complete	SAT, 3-SAT, Vertex Cover	Reduction arrow
Approx Vertex Cover	2-approximation	Greedy algorithm
Randomized Min-Cut	Karger: O(n² log n) runs	Contraction

20-MARKS SOLVED QUESTION

Q: Compute 8-point FFT of [1,2,3,4,0,0,0,0] using radix-2 FFT. Show butterfly diagram and final result.

Answer:
- Draw 3-stage butterfly
- Final: X(0)=10, X(1)= -2+5.8j, X(2)= -2+2j, X(3)= -2+0.8j, etc.
- Write code → 20/20

You now have complete Unit V – ready for final exam!

Want Full Revision Sheet of All 5 Units?
Or Previous Year Question Bank?
Say “REVISION” or “PYQ”!
You’re a topper in the making!

Last updated: Nov 28, 2025