IndianTechnoEra: Discrete Mathematics For AIML - Chapter 9 Algorithms & Complexity

Chapter 9 — Algorithms & Complexity

This chapter explores algorithm design, analysis, and computational complexity, which are essential for implementing efficient ML pipelines and optimizing resource usage.

9.1 Algorithm Analysis: Time & Space Complexity

Understanding how algorithms perform in terms of time (execution steps) and space (memory usage) is crucial. AI/ML Context: Efficient data preprocessing, model training, and inference require low-complexity algorithms.

# Example: Linear search in Python
def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1
# Time complexity: O(n), Space complexity: O(1)

9.2 Big O, Big Theta, Big Omega Notation

Big O (O): Upper bound on running time.
Big Omega (Ω): Lower bound.
Big Theta (Θ): Tight bound. AI/ML Context: Helps choose efficient algorithms for training, feature selection, and large datasets.

# Example: Sorting complexities
# Bubble Sort: O(n^2) worst-case, Θ(n^2) average, Ω(n) best-case
# Merge Sort: O(n log n), Θ(n log n), Ω(n log n)

9.3 Common Algorithms

Important algorithm categories in ML and discrete structures:

• Sorting: QuickSort, MergeSort, HeapSort — used in feature ranking, preprocessing, and batch processing.
• Searching: Binary Search, Linear Search — used in dataset indexing and fast lookups.
• Graph Traversal: BFS, DFS — used in social networks, knowledge graphs, and search algorithms.

# BFS example in Python
from collections import deque

graph = {0: [1,2], 1: [2], 2: [0,3], 3: [3]}
def bfs(start):
    visited = set()
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            queue.extend(n for n in graph[node] if n not in visited)
    return visited
print(bfs(2))

9.4 P vs NP Problems & NP-Completeness

P Problems: solvable in polynomial time.
NP Problems: verifiable in polynomial time.
NP-Complete: hardest problems in NP; no known polynomial-time solutions. AI/ML Context: Understanding problem hardness guides approximate algorithms and heuristic approaches for combinatorial optimization, feature selection, and resource allocation.

9.5 ML Use Cases

• Optimizing feature selection algorithms (combinatorial optimization).
• Efficient search for hyperparameter tuning (grid search, randomized search).
• Graph algorithms in recommendation systems and social networks.
• Handling large-scale datasets in preprocessing and model training.

9.6 Practical Python Implementation

# Example: Sorting a dataset feature
import numpy as np

features = np.array([5,3,8,1,2])
sorted_features = np.sort(features)  # O(n log n)
print(sorted_features)

# Searching for an element
index = np.where(features == 8)[0][0]
print("Index of 8:", index)

9.7 Exercises

1. Implement BFS and DFS on a given graph and compare visited order.
2. Measure execution time for different sorting algorithms on large arrays.
3. Identify whether a small combinatorial problem is tractable (P) or likely NP-hard.

Hints / Solutions

1. Use deque for BFS queue and recursion or stack for DFS.
2. Use time.time() before and after sort to measure runtime.
3. Compare problem size vs known polynomial-time solutions; heuristic may be needed.

9.8 Further Reading & Videos

• Introduction to Algorithms (CLRS) — chapters on algorithm complexity
• MIT OpenCourseWare — Algorithms and Complexity
• Python: Time and Space Complexity analysis
• YouTube: Abdul Bari — Algorithm analysis and Big O explained

Next Chapter: Discrete Probability & Stochastic Models — building probabilistic reasoning for AI & ML on discrete structures.