UNIT 1: Introduction to Algorithms

1. Algorithm Basics
• Definition: An algorithm is a finite set of unambiguous instructions designed to solve a specific problem.
• Key Property: Finiteness (it must eventually terminate).
• Representation: Algorithms are commonly visualized using Flowcharts (graphical representation) or Pseudocode.

2. Performance Analysis
• Core Metrics: Algorithm performance is evaluated based on Time Complexity (CPU execution time) and Space Complexity (the amount of memory needed to run to completion).
• Worst-Case: Analyzes the maximum time needed to execute the algorithm for a given input size. It provides a guaranteed upper limit on execution time.
• Order of Growth: Measures how the execution time increases as the input size (n) increases.
• Fastest to slowest (most to least efficient): O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n)

3. Asymptotic Notations
Used to describe the runtime complexity of algorithms mathematically:
• Big-O (O): Represents the Upper Bound (Worst-case scenario).
• Big-Omega (Ω): Represents the Lower Bound (Best-case scenario).
• Big-Theta (Θ): Represents a Tight Bound (Average/Exact growth rate).

4. Recursion and Recurrences
• Recursion: When a function calls itself directly or indirectly to solve a smaller instance of the same problem.
• Recurrence Relation: A mathematical equation that defines a sequence based on a rule using preceding terms (e.g., T(n) = 2T(n/2) + n).
• Methods to Solve Recurrences:
    - Substitution Method: Guessing the bound and proving it via mathematical induction.
    - Recursion Tree Method: Drawing a tree where the total time is the sum of the costs at all levels.
    - Master Theorem: Used specifically to solve recurrences in the form: T(n) = aT(n/b) + f(n).
    - Changing Variable: A technique to transform a complex recurrence into a simpler, recognizable form.
• Note on Heap Sort: It is implemented using a Binary Tree (specifically a complete binary tree/heap data structure).

UNIT 2: Divide and Conquer

1. Core Concept
This strategy involves three steps and is naturally implemented using recursion because the subproblems are smaller, identical instances of the original problem.
• Divide: Split the problem into smaller subproblems (This step usually takes O(1) time).
• Conquer: Solve the subproblems recursively.
• Combine: Merge the solutions of the subproblems to get the final answer.

2. Key Algorithms
• Binary Search:
    - Prerequisite: The array must be sorted.
    - Mechanism: Divides the search space in half at each step.
    - Worst-case Time Complexity: O(log n).
• Merge Sort:
    - Mechanism: Continuously divides the list in half until individual elements are reached, then merges them back together in order.
    - Recurrence Relation: T(n) = 2T(n/2) + O(n).
    - Time Complexity: O(n log n) in all cases (Best, Average, Worst).
    - Space Complexity: O(n) (requires extra memory for merging).
• Quick Sort:
    - Mechanism: Selects a pivot and partitions the array around it.
    - Pivot Guarantee: After a partition, the pivot element is placed in its final, correct sorted position.
    - Worst-Case Scenario: Occurs when the array is already sorted or reverse sorted (if the last/first element is used as a pivot), resulting in O(n^2) time complexity.
• Strassen’s Matrix Multiplication:
    - An optimization over standard matrix multiplication.
    - It reduces the time complexity by minimizing the number of scalar multiplications.
    - It requires only 7 multiplications for 2x2 submatrices (compared to 8 in the standard method).

UNIT 3: Backtracking & Branch and Bound

1. Backtracking
• Concept: Explores all possible paths to find solutions. It heavily relies on Depth-First Search (DFS) tree traversal.
• State Space Tree: A conceptual tree representing all possible states of a problem.
• Live Node: A node that has been generated but its children are not yet fully explored.
• Dead Node: A node that has no children left to generate, or it violates constraints and is abandoned.
• Bounding Function / Pruning: Used to stop exploring a path that cannot possibly lead to a valid solution, saving time.
• Specific Backtracking Problems:
    - N-Queens Problem: Place N queens on an NxN board so no two queens threaten each other (cannot share the same row, column, or diagonal). (e.g., 4-Queens uses 4 queens).
    - Hamiltonian Cycle: Find a path in a graph that visits every vertex exactly once and returns to the starting vertex.
    - Sum of Subsets: Find all subsets of a given set whose elements sum up to a specific target value.
    - Graph Coloring: Assign colors to vertices such that no two adjacent vertices have the same color.

2. Branch and Bound
• Concept: Used specifically for Optimization Problems (finding the absolute minimum or maximum/best solution).
• Traversal: Usually relies on Breadth-First Search (BFS) or Least-Cost Search.
• The "Bound": An estimated limit on the optimal solution cost, used to prune branches that are guaranteed to be worse than the best solution found so far.
• Specific Branch & Bound Problems:
    - Traveling Salesperson Problem (TSP): Find the shortest possible route that visits every city exactly once and returns to the origin.
    - 15-Puzzle Problem.

3. Key Differences: Backtracking vs. Branch and Bound
• Problem Type: Backtracking focuses on Decision / Finding all valid solutions. Branch & Bound focuses on Optimization (Min/Max best solution).
• Search Method: Backtracking uses Depth-First Search (DFS). Branch & Bound uses Breadth-First Search (BFS) / Least-Cost.
• Goal: Backtracking finds feasible solution(s). Branch & Bound finds the optimal solution.