---

📘 Randomization and Dynamic Programming

(Basic Algorithm Design Techniques)

---

PART A: RANDOMIZATION

1️⃣ Introduction to Randomization

A randomized algorithm uses random numbers at some point during its execution to make decisions.

The behavior of such algorithms is not deterministic, meaning the same input may produce different execution paths.

Randomization helps avoid worst-case scenarios and improves average performance.

---

2️⃣ Why Use Randomized Algorithms?

• Avoids worst-case inputs
• Simple and elegant solutions
• Good average-case performance
• Useful when input distribution is unknown

---

3️⃣ Types of Randomized Algorithms

🔹 1. Las Vegas Algorithms

• Always produce correct result
• Running time is random

📌 Example:

• Randomized Quick Sort

---

🔹 2. Monte Carlo Algorithms

• Fixed running time
• Result may be incorrect with small probability

📌 Example:

• Randomized primality testing

---

4️⃣ Examples of Randomized Algorithms

🔹 Randomized Quick Sort

• Randomly selects pivot
• Avoids worst-case input

Expected Time Complexity:
[
O(n \log n)
]

---

🔹 Randomized Binary Search

• Randomly selects mid
• Useful for large datasets

---

5️⃣ Advantages of Randomization

✔ Avoids worst-case scenarios
✔ Simple implementation
✔ Efficient average-case performance

---

6️⃣ Disadvantages of Randomization

✖ Non-deterministic behavior
✖ Difficult to debug
✖ Requires random number generation

---

---

PART B: DYNAMIC PROGRAMMING

7️⃣ Introduction to Dynamic Programming (DP)

Dynamic Programming is an algorithm design technique used to solve problems by:

• Breaking them into overlapping sub-problems
• Solving each sub-problem only once
• Storing results to avoid recomputation

DP is an optimization of recursion.

---

8️⃣ Characteristics of Dynamic Programming

🔹 1. Optimal Substructure

Optimal solution contains optimal solutions of sub-problems.

🔹 2. Overlapping Sub-Problems

Same sub-problems are solved multiple times in recursion.

---

9️⃣ Approaches in Dynamic Programming

🔹 1. Top-Down (Memoization)

• Uses recursion
• Stores results in a table

🔹 2. Bottom-Up (Tabulation)

• Uses iteration
• Builds solution from smallest sub-problem

---

🔟 Examples of Dynamic Programming

🔹 Fibonacci Series (DP)

dp[0] = 0
dp[1] = 1
dp[n] = dp[n-1] + dp[n-2]

Time Complexity: O(n)
Space Complexity: O(n)

---

🔹 0/1 Knapsack Problem

• Choose items to maximize profit
• Weight constraint

Time Complexity: O(nW)

---

🔹 Longest Common Subsequence (LCS)

• Find longest subsequence common to two strings

Time Complexity: O(mn)

---

1️⃣1️⃣ Advantages of Dynamic Programming

✔ Guarantees optimal solution
✔ Efficient for complex problems
✔ Avoids repeated computation

---

1️⃣2️⃣ Disadvantages of Dynamic Programming

✖ Higher space usage
✖ Difficult to design
✖ Problem-specific

---

1️⃣3️⃣ Randomization vs Dynamic Programming

Feature	Randomization	Dynamic Programming
Nature	Probabilistic	Deterministic
Decision	Random	Optimal
Guarantee	Probabilistic	Guaranteed
Usage	Avoid worst case	Optimization problems

---

🔚 Conclusion

Randomization and Dynamic Programming are powerful algorithm design techniques used for different types of problems.

Randomization improves average performance, while Dynamic Programming guarantees optimal solutions.

---