Part 1: Course Introduction & Why Algorithms Matter
Welcome to Algorithms! 🚀
What We’ll Learn
Design algorithms that solve problems
Analyze their efficiency
Compare different approaches
Apply algorithmic thinking
Course Philosophy
“Perhaps the most important principle for the good algorithm designer is to refuse to be content.”
— Aho, Hopcroft, and Ullman
Our Mantra: Can we do better? 🤔
Why Study Algorithms?
1. Foundation for Computer Science 🏗️
Routing protocols → Shortest path algorithms
Cryptography → Number-theoretic algorithms
Graphics → Geometric algorithms
Databases → Search tree data structures
Biology → Dynamic programming for genome similarity
2. Driver of Innovation 💡
“Performance gains due to improvements in algorithms have vastly exceeded even the dramatic performance gains due to increased processor speed.”
— Report to the White House, 2010
Interactive Demo: The Power of Algorithms
import timeimport matplotlib.pyplot as pltimport numpy as np# Simulating algorithm performancedef naive_search(arr, target):"""O(n) linear search""" comparisons =0for i inrange(len(arr)): comparisons +=1if arr[i] == target:return comparisonsreturn comparisonsdef binary_search(arr, target):"""O(log n) binary search""" comparisons =0 left, right =0, len(arr) -1while left <= right: comparisons +=1 mid = (left + right) //2if arr[mid] == target:return comparisonselif arr[mid] < target: left = mid +1else: right = mid -1return comparisons# Visualizationsizes = [10, 100, 1000, 10000]linear_comps = []binary_comps = []for n in sizes: arr =list(range(n)) linear_comps.append(naive_search(arr, n-1)) binary_comps.append(binary_search(arr, n-1))plt.figure(figsize=(10, 6))plt.plot(sizes, linear_comps, 'r-', label='Linear Search O(n)', marker='o')plt.plot(sizes, binary_comps, 'b-', label='Binary Search O(log n)', marker='s')plt.xlabel('Array Size (n)')plt.ylabel('Number of Comparisons')plt.title('Algorithm Efficiency Comparison')plt.legend()plt.xscale('log')plt.yscale('log')plt.grid(True, alpha=0.3)plt.show()
Question: You have 1 million sorted numbers. How many comparisons does binary search need in the worst case?
Answer: About 20 comparisons! - \(\log_2(1,000,000) \approx 20\) - Linear search would need 1,000,000 comparisons!
Karatsuba: Only 3 multiplications! 1. \(P_1 = a \cdot c\) 2. \(P_2 = b \cdot d\) 3. \(P_3 = (a+b) \cdot (c+d)\)
Then: \(ad + bc = P_3 - P_1 - P_2\)
Live Coding: Karatsuba Implementation
def karatsuba(x, y):"""Karatsuba multiplication algorithm"""# Base caseif x <10or y <10:return x * y# Calculate size of numbers n =max(len(str(x)), len(str(y))) half = n //2# Split the numbers a = x // (10** half) b = x % (10** half) c = y // (10** half) d = y % (10** half)# Three recursive calls ac = karatsuba(a, c) bd = karatsuba(b, d) ad_plus_bc = karatsuba(a + b, c + d) - ac - bd# Combine resultsreturn ac * (10** (2* half)) + ad_plus_bc * (10** half) + bd# Test it!x =1234y =5678result = karatsuba(x, y)print(f"{x} × {y} = {result}")print(f"Verification: {x * y == result}")
1234 × 5678 = 7006652
Verification: True
Part 2: Algorithm Fundamentals with MergeSort
The Sorting Problem
Definition
Input: Array of n numbers in arbitrary order
Output: Same numbers, sorted from smallest to largest
graph TD A[5,4,1,8,7,2,6,3] --> B[5,4,1,8] A --> C[7,2,6,3] B --> D[5,4] B --> E[1,8] C --> F[7,2] C --> G[6,3] D --> H[1,4,5,8] E --> H F --> I[2,3,6,7] G --> I H --> J[1,2,3,4,5,6,7,8] I --> J
graph TD
A[5,4,1,8,7,2,6,3] --> B[5,4,1,8]
A --> C[7,2,6,3]
B --> D[5,4]
B --> E[1,8]
C --> F[7,2]
C --> G[6,3]
D --> H[1,4,5,8]
E --> H
F --> I[2,3,6,7]
G --> I
H --> J[1,2,3,4,5,6,7,8]
I --> J
Interactive MergeSort Visualization
def merge(left, right):"""Merge two sorted arrays""" result = [] i = j =0# Merge process with step tracking steps = []while i <len(left) and j <len(right):if left[i] <= right[j]: result.append(left[i]) steps.append(f"Compare {left[i]} ≤ {right[j]}: Take {left[i]} from left") i +=1else: result.append(right[j]) steps.append(f"Compare {left[i]} > {right[j]}: Take {right[j]} from right") j +=1# Add remaining elements result.extend(left[i:]) result.extend(right[j:])return result, stepsdef mergesort_visual(arr, depth=0):"""MergeSort with visualization""" indent =" "* depthprint(f"{indent}Sorting: {arr}")iflen(arr) <=1:return arr mid =len(arr) //2 left = mergesort_visual(arr[:mid], depth +1) right = mergesort_visual(arr[mid:], depth +1) result, steps = merge(left, right)print(f"{indent}Merging {left} + {right} = {result}")return result# Demotest_array = [5, 4, 1, 8, 7, 2, 6, 3]print("MergeSort Trace:")sorted_array = mergesort_visual(test_array)print(f"\nFinal result: {sorted_array}")
How do we compare algorithms across: - Different programming languages? - Different hardware? - Different compilers? - Different input sizes?
The Solution: Big-O Notation
Focus on growth rate, not exact counts!
Suppress: - Constant factors (system-dependent) - Lower-order terms (irrelevant for large n)
Big-O Intuition
Formal Definition of Big-O
Mathematical Definition
\(T(n) = O(f(n))\) if and only if there exist positive constants \(c\) and \(n_0\) such that:
\[T(n) \leq c \cdot f(n) \text{ for all } n \geq n_0\]
In Plain English
“\(T(n)\) is eventually bounded above by a constant multiple of \(f(n)\)”
Visual Interpretation
Interactive Big-O Practice
def analyze_code_complexity(code_type):"""Analyze different code patterns""" examples = {'constant': {'code': 'x = arr[0] + arr[n-1]','complexity': 'O(1)','explanation': 'Fixed number of operations' },'linear': {'code': 'for i in range(n):\n process(arr[i])','complexity': 'O(n)','explanation': 'Single loop through n elements' },'quadratic': {'code': 'for i in range(n):\n for j in range(n):\n process(arr[i], arr[j])','complexity': 'O(n²)','explanation': 'Nested loops, n × n iterations' },'logarithmic': {'code': 'while n > 1:\n n = n // 2\n process()','complexity': 'O(log n)','explanation': 'Halving n each iteration' } } example = examples.get(code_type, examples['linear'])print(f"Code Pattern:\n{example['code']}\n")print(f"Complexity: {example['complexity']}")print(f"Reason: {example['explanation']}")return example# Try different patternsprint("="*50)print("ANALYZING CODE COMPLEXITY")print("="*50)for pattern in ['constant', 'logarithmic', 'linear', 'quadratic']: analyze_code_complexity(pattern)print("-"*50)
==================================================
ANALYZING CODE COMPLEXITY
==================================================
Code Pattern:
x = arr[0] + arr[n-1]
Complexity: O(1)
Reason: Fixed number of operations
--------------------------------------------------
Code Pattern:
while n > 1:
n = n // 2
process()
Complexity: O(log n)
Reason: Halving n each iteration
--------------------------------------------------
Code Pattern:
for i in range(n):
process(arr[i])
Complexity: O(n)
Reason: Single loop through n elements
--------------------------------------------------
Code Pattern:
for i in range(n):
for j in range(n):
process(arr[i], arr[j])
Complexity: O(n²)
Reason: Nested loops, n × n iterations
--------------------------------------------------
Big-O Family: Ω and Θ
Big-O
Upper bound (≤) \[T(n) = O(f(n))\] “At most this fast”
Big-Omega (Ω)
Lower bound (≥) \[T(n) = \Omega(f(n))\] “At least this slow”
Big-Theta (Θ)
Tight bound (=) \[T(n) = \Theta(f(n))\] “Exactly this rate”
# Code Afor i inrange(n):for j inrange(i+1, n): process(i, j)# Code B i = nwhile i >0: process(i) i = i //3# Code Cfor i inrange(n): binary_search(arr, target)
Options: O(n²), O(n log n), O(log n)
Answers: - Code A: O(n²) - nested loops with ~n²/2 iterations - Code B: O(log n) - dividing by 3 each time - Code C: O(n log n) - n iterations × log n per search
Common Complexity Classes
Complexity
Name
Example Algorithm
1000 items
O(1)
Constant
Array access
1 op
O(log n)
Logarithmic
Binary search
~10 ops
O(n)
Linear
Linear search
1,000 ops
O(n log n)
Linearithmic
MergeSort
~10,000 ops
O(n²)
Quadratic
Selection sort
1,000,000 ops
O(2ⁿ)
Exponential
Subset generation
2¹⁰⁰⁰ ops 😱
Key Insight: For large n, even small improvements in complexity class yield massive speedups!
