📘 PAPER 4 – DESIGN & ANALYSIS OF ALGORITHMS ( UNIT 5 – RANDOMIZED ALGORITHMS & NP-COMPLETENESS) university of allahabad)

 

🔴 UNIT 5 – RANDOMIZED ALGORITHMS & NP-COMPLETENESS

---

🟦 PART A: RANDOMIZED ALGORITHMS

---

1️⃣ Randomized Algorithm

✅ Definition

A Randomized Algorithm uses random numbers to make decisions during execution.

👉 Output or running time may vary for the same input.

---

🔹 Types of Randomized Algorithms

1️⃣ Las Vegas Algorithm

✔ Always gives correct result
✔ Execution time varies

📌 Example: Randomized Quick Sort

---

2️⃣ Monte Carlo Algorithm

✔ Fast execution
❌ May give incorrect result (with small probability)

📌 Example: Primality testing

---

2️⃣ Randomized Quick Sort

Idea:

• Randomly select pivot

• Partition array

• Recursively sort

Time Complexity:

Case	Time
Best	O(n log n)
Average	O(n log n)
Worst	O(n²)

✔ Faster in practice than normal quicksort

---

3️⃣ Randomized Min-Cut Algorithm

Proposed by:

Karger’s Algorithm

Purpose:

Find minimum cut in an undirected graph.

---

Working:

1. Pick random edge

2. Contract vertices

3. Repeat until 2 vertices remain

4. Count crossing edges

---

Advantage:

✔ Simple
✔ Probabilistically correct

---

4️⃣ Randomized Algorithm for N-Queen

Idea:

• Place queens randomly

• If conflict → retry

• Continue until solution found

✔ Faster than backtracking for large N

---

🟦 PART B: APPROXIMATION ALGORITHMS

---

5️⃣ Approximation Algorithm

Definition:

Algorithm that gives near-optimal solution for NP-hard problems.

---

Approximation Ratio:

$$\frac{Solution\_Cost}{Optimal\_Cost}$$

---

6️⃣ Job Scheduling Problem

Objective:

Minimize completion time of jobs on machines.

Greedy Strategy:

• Sort jobs by processing time

• Assign shortest job first

---

7️⃣ Bin Packing Problem

Problem:

Pack objects into minimum number of bins.

Approximate Solution:

• First Fit

• Best Fit

---

8️⃣ Set Cover Problem

Goal:

Select minimum number of sets whose union covers all elements.

Solution:

✔ Greedy approximation

---

9️⃣ Max Cut Problem

Definition:

Divide graph into two sets such that:

• Maximum number of edges cross between them

✔ NP-Hard
✔ Approximation algorithms used

---

🟦 PART C: LOWER BOUND THEORY

---

🔟 Lower Bound

Definition:

Minimum number of operations required to solve a problem.

---

Types:

1. Comparison-based

2. Decision tree based

---

🔹 Decision Tree Method

Used to find:
✔ Lower bound of sorting
✔ Complexity analysis

---

Example:

Sorting requires at least:

$$Ω(n \log n)$$

---

🔹 Reduction Method

Definition:

If problem A can be reduced to problem B, and B is hard → A is also hard.

Used in:
✔ NP-completeness proofs

---

🟦 PART D: NP-COMPLETENESS

---

1️⃣ Class P

✔ Problems solvable in polynomial time
✔ Efficient algorithms exist

Example:

• Sorting

• Searching

---

2️⃣ Class NP

✔ Solution verifiable in polynomial time
✔ Not necessarily solvable fast

Example:

• Traveling Salesman

• Knapsack

---

3️⃣ NP-Hard

✔ At least as hard as NP problems
✔ May not be in NP

---

4️⃣ NP-Complete

✔ Belongs to NP
✔ Also NP-Hard

---

Famous NP-Complete Problems:

• Traveling Salesman Problem

• Knapsack

• SAT

• Graph Coloring

• Hamiltonian Cycle

---

5️⃣ P vs NP Problem

Question:

Is P = NP ?

Answer:

❌ Still unsolved (Millennium problem)

---

📌 EXAM IMPORTANT QUESTIONS (UNIT 5)

✔ Explain randomized algorithms
✔ Explain NP-complete problems
✔ Difference between P, NP, NP-hard
✔ Explain approximation algorithms
✔ Explain min-cut algorithm
✔ Decision tree method