Ontological Layer: High-Level Problem Solving

Algorithmic Thinking

Strategies for Complexity and Optimization

The Architecture of Strategy

Knowing how to sort an array or traverse a graph is not enough; one must know how to approach problems that have never been solved before. This realm shifts focus from specific data structures to general paradigms of thought. We learn to split problems recursively (Divide & Conquer), seize immediate local benefits (Greedy), trade memory for time by reusing past answers (Dynamic Programming), and systematically explore constrained universes while abandoning failed paths (Backtracking).

COMPLEX PROBLEM → DECOMPOSE (D&C) vs LOCAL CHOICE (GREEDY) → OVERLAPPING SUBPROBLEMS REUSE (DP) vs SYSTEMATIC SEARCH (BACKTRACK) → OPTIMAL SOLUTION

The 14 Strategy Nodes

Ontological Mapping: Paradigms of Computation

GROUP 01

Divide & Conquer

Problem decomposition
Independent subproblems
Recursive solution (Conquer)
Combine partial results

GROUP 01 (CONT)

Recurrence Idea

Mathematical cost modeling
Base cases
Cost of dividing + combining
Merge Sort / Quick Sort connection

GROUP 02

Greedy Choice

Selecting local optimum
No looking back (Commitment)
Checking feasibility
Hope for global optimum

GROUP 02 (CONT)

Correctness Intuition

Local vs Global objective
Exchange arguments for proof
When greedy fails (e.g., Knapsack 0/1)
MST (Prim/Kruskal) connection

GROUP 02 (CONT)

Activity Selection

Classic greedy application
Sorting by finish time
Selecting non-overlapping intervals
Maximizing task count

GROUP 03

Overlapping Subproblems

Recursion re-evaluates same states
Exponential waste of time
Identifying redundancy
The core motivation for DP

GROUP 03 (CONT)

Optimal Substructure

Global optimum contains local optima
State definition (What represents a subproblem?)
Recurrence relation formulation
Shortest path connection

GROUP 03 (CONT)

Memoization

Top-down recursive approach
Check cache before computing
Store result after computing
"Remember what is already solved"

GROUP 03 (CONT)

Tabulation

Bottom-up iterative approach
Solve smallest subproblems first
Fill a table systematically
Often more space-efficient (State reduction)

GROUP 04

Search Space Exploration

Candidate solution building
Decision sequences (Trees)
Depth-First Search connection
Exhaustive vs Intelligent search

GROUP 04 (CONT)

Constraints & Pruning

Feasibility checks on partial states
Rejecting invalid paths early
Pruning the search tree
Massive reduction in computation

GROUP 04 (CONT)

Undo Choice (Backtrack)

Choose → Explore → Reject
Undo state modifications
Return to previous decision point
Recursive backtracking implementation

GROUP 04 (CONT)

N-Queens

Classic backtracking application
Row-by-row placement
Column and Diagonal constraint checks
Finding one or all valid arrangements

FINAL PROTOCOL

08 — Strategy Synthesis Laboratory

1. IDENTIFY OVERLAPS -> USE DP

2. LOCAL CHOICE SAFE? -> USE GREEDY

3. MUST SEARCH ALL? -> USE BACKTRACK

[1] ANALYZE STRUCTURE [2] SELECT PARADIGM [3] WRITE RECURRENCE [4] PRUNE PATHS [5] OPTIMIZE SPACE

These four paradigms represent the pinnacle of algorithmic design. Once you know *how* to approach a complex problem, the next logical question is deciding whether your chosen approach is actually efficient. This brings us directly to Realm 09: Mathematics of Efficiency (Big O Notation).

SIMULATION RUNNING