Study Material

  🔴 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: Pick random edge Contract vertices Repeat until 2 vertices remain Count cro...

  🔴 UNIT 4 – DYNAMIC PROGRAMMING & BACKTRACKING 🟦 PART A: DYNAMIC PROGRAMMING 1️⃣ Dynamic Programming (DP) ✅ Definition Dynamic Programming is a technique used to solve problems by: ✔ Breaking them into subproblems ✔ Solving each subproblem only once ✔ Storing results for future use 🔹 Properties of DP Optimal Substructure Overlapping Subproblems 2️⃣ 0/1 Knapsack Problem Problem Statement: Given: Weight array w[] Profit array p[] Capacity W Goal: Maximize profit without exceeding capacity. DP Formula: DP[i][w] = max ( DP[i -1 ][w], DP[i -1 ][w - wi] + pi ) Time Complexity: O (nW) Difference: Fractional vs 0/1 Knapsack Feature Fractional 0/1 Item division Allowed Not allowed Approach Greedy Dynamic Optimal Yes Yes 3️⃣ Matrix Chain Multiplication Purpose: Find the most efficient way to multiply matrices. DP Formula: M[i][j] = min { M[i][k] + M[k+ 1 ][j] + pi -1 * pk * pj } Time Complexity: O (n³) 4️⃣ All-Pairs S...

  🔴 UNIT 3 – DIVIDE & CONQUER AND GREEDY METHODS 🔹 PART A: DIVIDE AND CONQUER 1️⃣ Divide and Conquer Technique ✅ Definition Divide and Conquer is an algorithm design technique that: Divides the problem into smaller subproblems Conquers them recursively Combines the solutions General Form: Divide → Conquer → Combine Examples: ✔ Merge Sort ✔ Quick Sort ✔ Binary Search ✔ Matrix Multiplication 2️⃣ Matrix Multiplication 🔹 Normal Method Time Complexity: O (n³) 🔹 Strassen’s Matrix Multiplication Reduces multiplication operations. Time Complexity: O (n^ 2.81 ) Advantage: ✔ Faster than normal method ✔ Used in large matrix computation 3️⃣ Convex Hull ✅ Definition Convex Hull is the smallest convex polygon that encloses all points. Algorithms: Graham’s Scan Jarvis March Applications: Image processing Pattern recognition GIS systems 🔹 PART B: GREEDY METHOD 4️⃣ Greedy Algorithm ✅ Definition Greedy algorith...

  🔴 UNIT 2 – ADVANCED DATA STRUCTURES 1️⃣ AVL TREE (Adelson–Velsky and Landis Tree) ✅ Definition An AVL Tree is a self-balancing Binary Search Tree (BST) where the height difference (balance factor) of left and right subtrees is at most 1 . ✅ Balance Factor (BF) B F = H e i g h t ( l e f t   s u b t r e e ) − H e i g h t ( r i g h t   s u b t r e e ) BF = Height(left\ subtree) - Height(right\ subtree) BF = He i g h t ( l e f t   s u b t ree ) − He i g h t ( r i g h t   s u b t ree ) Allowed values: -1 0 +1 ✅ Rotations in AVL Tree When balance factor becomes ±2 , rotations are performed. 🔹 Types of Rotations 1. LL Rotation (Left-Left) Occurs when: Insertion in left subtree of left child ✔ Single right rotation 2. RR Rotation (Right-Right) Occurs when: Insertion in right subtree of right child ✔ Single left rotation 3. LR Rotation (Left-Right) Occurs when: Left child has right-heavy subtree ✔ Left rotation + R...

cx  📘 PAPER 4 – DESIGN & ANALYSIS OF ALGORITHMS 🔴 UNIT 1 – INTRODUCTION & SORTING TECHNIQUES 1️⃣ Introduction to Algorithms ✅ What is an Algorithm? An algorithm is a finite set of well-defined steps used to solve a problem. ✅ Characteristics of Algorithm ✔ Input ✔ Output ✔ Finiteness ✔ Definiteness ✔ Effectiveness 2️⃣ Analysis of Algorithms Algorithm analysis means measuring performance in terms of: 🔹 Time Complexity Time taken by an algorithm to run. 🔹 Space Complexity Memory used by the algorithm. 3️⃣ Growth of Functions Used to compare algorithm efficiency. Common Growth Rates: Notation Name O(1) Constant O(log n) Logarithmic O(n) Linear O(n log n) Linear-log O(n²) Quadratic O(2ⁿ) Exponential 4️⃣ Asymptotic Notations 🔹 Big-O Notation – Worst Case O (n) 🔹 Omega (Ω) – Best Case Ω(n) 🔹 Theta (Θ) – Average Case Θ(n) 5️⃣ Recurrence Relations A recurrence relation defines a function in terms of itself. Example: T ( n ) = T ( n / ...