Algorithm Design Basics: Models, Analysis & Paradigms

Core Concepts

1. What is an Algorithm?

An algorithm is a finite, unambiguous sequence of steps to solve a problem or perform a computation. It must:

• Have a clear input/output.
• Be deterministic (no randomness in logic).
• Terminate after finite steps.
• Be effective (each step must be doable by a machine).

Example:

flowchart TD
    A["Start"] --> B["Check if array is sorted?"]
    B -->|"Yes"| C["Set low=0, high=n-1"]
    B -->|"No"| D["Error: Not sorted"]
    C --> E["mid = (low+high)/2"]
    E --> F["Is arr[mid] == target?"]
    F -->|"Yes"| G["Return mid"]
    F -->|"No"| H["If target < arr[mid], high=mid-1\nElse, low=mid+1"]
    H --> E

2. RAM Model (Random Access Machine)

The RAM model abstracts a computer’s CPU as:

• Memory: Infinite array of words (each word holds a fixed-size value).
• Registers: Finite set of fast-access storage (e.g., PC, ACC).
• Operations:
  • Load/Store: Move data between memory/registers.
  • Arithmetic/Logical: +, -, AND, OR.
  • Branching: Conditional jumps (if/else).

Why it matters: Used to analyze time/space complexity (e.g., "Binary search runs in $O(\log n)$ time on RAM").

Algorithm Analysis

1. Asymptotic Notation

Example: Binary Search Trace

def binary_search(arr, target):
    low, high = 0, len(arr)-1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target: return mid
        elif arr[mid] < target: low = mid + 1
        else: high = mid - 1
    return -1

Trace for arr = [1,3,5,7,9], target = 5:

2. Problem Classification

Why NP-Completeness matters:

• P vs NP: No known algorithm solves NP-Complete problems in polynomial time (e.g., cracking passwords via brute force).
• Approximation: For NP-Hard problems (e.g., TSP), we use heuristics (e.g., Nearest Neighbor) to get "good enough" solutions.

Algorithm Design Paradigms

1. Greedy Algorithms

Definition: Make locally optimal choices at each step, hoping for a global optimum. When to use: Problems with optimal substructure and greedy choice property (e.g., MST, Fractional Knapsack).

Example: Fractional Knapsack (Nepali Context) Problem: Maximize value in a knapsack with weight limit W. Data:

Solution:

1. Sort items by value/weight ratio (highest first):
   • C: 20/3 ≈ 6.67
   • A: 12/2 = 6
   • B: 10/1 = 10
2. Take items until knapsack is full:
   • Take B (1kg, ₹10), remaining capacity = 2kg.
   • Take A (2kg, ₹12), total value = ₹22.

Visualization:

pie
    title Fractional Knapsack Allocation (W=3kg)
    "Item B (1kg)" : 10
    "Item A (2kg)" : 12
    "Unused" : 0

Code:

def fractional_knapsack(items, W):
    items.sort(key=lambda x: x[1]/x[0], reverse=True)
    total_value = 0
    for value, weight in items:
        if W <= 0: break
        take = min(weight, W)
        total_value += take * (value/weight)
        W -= take
    return total_value

2. Divide and Conquer

Definition: Break a problem into smaller subproblems, solve recursively, and combine results. Key Steps:

1. Divide: Split input into smaller parts.
2. Conquer: Solve subproblems recursively.
3. Combine: Merge solutions.

Example: Merge Sort Trace for arr = [38, 27, 43, 3, 9, 82, 10]:

flowchart LR
    A["MergeSort([38,27,43,3,9,82,10])"] --> B["Divide: [38,27,43] | [3,9,82,10]"]
    B --> C["MergeSort([38,27,43])"] --> D["Divide: [38,27] | [43]"]
    D --> E["MergeSort([38,27])"] --> F["Divide: [38] | [27]"]
    F --> G["Base: [38]"] --> H["Base: [27]"]
    H --> I["Merge: [27,38]"]
    D --> J["Base: [43]"]
    I --> J --> K["Merge: [27,38,43]"]
    B --> L["MergeSort([3,9,82,10])"] --> M["Divide: [3,9] | [82,10]"]
    M --> N["MergeSort([3,9])"] --> O["Base: [3]"] --> P["Base: [9]"]
    P --> Q["Merge: [3,9]"]
    M --> R["MergeSort([82,10])"] --> S["Base: [82]"] --> T["Base: [10]"]
    T --> U["Merge: [10,82]"]
    Q --> U --> V["Merge: [3,9,10,82]"]
    K --> V --> W["Final Merge: [3,9,10,27,38,43,82]"]

Time Complexity: $T(n)=2T(n/2)+O(n)$ → $O(n\log n)$.

In the Real World

1. eSewa (Nepal):

   • Greedy Algorithm: When processing multiple bill payments, eSewa uses a priority queue (greedy) to handle high-value transactions first, minimizing processing time for urgent payments.

2. Ncell’s Network Routing:

   • Divide and Conquer: Ncell’s routers use Dijkstra’s algorithm (divide-and-conquer) to find the shortest path for data packets, ensuring minimal latency.

3. Khalti’s Fraud Detection:

   • NP-Hard Approximation: Khalti’s system flags suspicious transactions using rule-based heuristics (approximation for NP-Hard fraud detection), balancing speed and accuracy.

Exam Tip

1. Binary Search:

   • Always prove correctness (invariant: target is in arr[low..high]).
   • Time Complexity: $O(\log n)$ (halving the search space each step).

2. Greedy vs DP:

   • Greedy works if the problem has optimal substructure + greedy choice property (e.g., MST, Fractional Knapsack).
   • DP is needed for problems like 0/1 Knapsack (where greedy fails).

3. RAM Model:

   • Assume unit-cost operations (e.g., arr[i] = x takes 1 step).
   • Space: Count memory cells used (e.g., recursion stack in QuickSort).

4. P vs NP:

   • P: Problems with polynomial-time solutions (e.g., sorting).
   • NP: Problems where solutions can be verified quickly (e.g., Hamiltonian Cycle).
   • Approximation: For NP-Hard problems, justify your heuristic (e.g., "Nearest Neighbor gives a 2-approximation for TSP").

Visual Summary:

mindmap
  root((Algorithm Design))
    Core Concepts
      Algorithm Definition
      RAM Model
    Analysis
      Asymptotic Notation
      Time/Space Complexity
    Paradigms
      Greedy
        Example: Fractional Knapsack
      Divide & Conquer
        Example: Merge Sort
    Real-World
      eSewa: Priority Queues
      Ncell: Dijkstra's Routing