29/01/2025

OL Problem-Solving Algorithms Memory-Management

Single-word outline designed for rapid revision, structured to cover problem-solving approaches, algorithms, and memory management comprehensively

1. Problem-Solving Approaches

This section focuses on strategies/methods to design solutions, not specific algorithms.

  • Algorithms (as a concept)
    • Design (how to structure solutions)
    • Strategies
      • Divide-and-Conquer
      • Greedy
      • Backtracking
      • Dynamic-Programming
      • Brute-Force
    • Analysis (e.g., complexity, tradeoffs)

Problem-Solving Strategies

  • Abstraction
  • Decomposition
  • Pattern-Recognition
  • Debugging
  • Iteration
  • Recursion
  • Simulation

Algorithms

Fundamental Algorithms

  • Sorting
    • Bubble
    • Selection
    • Insertion
    • Merge
    • Quick
    • Heap
  • Searching
    • Linear
    • Binary
    • Hashing
  • Graph
    • BFS

2. Algorithms (Fundamental)

This section lists specific, classic algorithms grouped by purpose.

  • Sorting
    • Bubble, Selection, Insertion
    • Merge, Quick, Heap
  • Searching
    • Linear, Binary
    • Hashing
  • Graph Algorithms
    • BFS (Breadth-First Search)
    • DFS (Depth-First Search)
    • Dijkstra (Shortest Path)
    • A* (Pathfinding)
  • String Algorithms
    • Substring Search (e.g., KMP, Boyer-Moore)
    • Pattern Matching
      Algorithm Analysis
  • Complexity
    • Time
    • Space
  • Big-O
  • Omega
  • Theta

Efficiency

  • Optimization
  • Tradeoffs
  • Scalability

Extra

Graph Algorithms

  • Kruskal’s / Prim’s (Minimum Spanning Trees)
  • Bellman-Ford (Negative-weight shortest paths)
  • Topological Sorting

String Algorithms:

  • Rabin-Karp (Hashing for substring search)

Memory Management

Dynamic Memory

  • Allocation
    • Malloc
    • Calloc
    • Realloc
  • Deallocation
    • Free
  • Fragmentation
    • Internal
    • External

Pointers

  • Declaration
  • Dereferencing
  • Arithmetic
  • Null
  • Dangling
  • Wild

Data Manipulation

  • Arrays
  • Linked-Lists
  • Stacks
  • Queues
  • Trees
  • Graphs

Memory Errors

  • Leaks
  • Overflow
  • Corruption
  • Dangling-Pointers

Best Practices

  • Allocation-Strategies
  • Garbage-Collection
  • Smart-Pointers

Key Concepts

Data Structures

  • Static
  • Dynamic
  • Linear
  • Non-Linear

Efficiency Metrics

  • Time-Complexity
  • Space-Complexity
  • Cache-Locality

Tools

  • Debuggers
  • Profilers
  • Memory-Analyzers

Key Distinctions

Problem-Solving "Algorithms" Fundamental "Algorithms"
Focus: How to approach problem-solving (methods/strategies). Focus: What specific algorithms exist (e.g., Merge Sort).
Example: "Use a greedy strategy to solve this optimization problem." Example: "Implement Dijkstra’s algorithm to find the shortest path."

Algorithms → Sorting → Merge or *Memory → Pointers → Dangling

Not useful for exam

Related topics/chapters/subjects name
Programming Fundamentals
Data Structures & Algorithms

Problem-Solving Approaches

  • Algorithms (design, strategies like divide-and-conquer, greedy, etc.)
  • Problem-solving techniques (abstraction, decomposition, debugging).

Algorithms

  • Fundamental algorithms (sorting, searching).
  • Algorithm analysis (time/space complexity, Big-O).

Memory Management

  • Dynamic allocation (malloc, pointers).
  • Data manipulation (arrays, linked lists).

Programming Concepts

Programming & System Fundamentals

  1. Problem-Solving & Algorithms
    • Strategies (greedy, dynamic programming).
    • Sorting (merge, quick) and searching (binary, hashing).
  2. Algorithm Analysis
    • Complexity (Big-O, scalability).
  3. Memory Management
    • Dynamic allocation (malloc/free).
    • Pointers and data structures (arrays, linked lists).
    • Memory errors (leaks, dangling pointers).

Graph Algorithms

  1. Shortest Path Algorithms
    • Floyd-Warshall: All-pairs shortest paths (dynamic programming).
    • Bellman-Ford: Handles negative-weight edges.
    • A*: Heuristic-based pathfinding (AI/games).
  2. Minimum Spanning Tree (MST)
    • Kruskal’s Algorithm: Uses disjoint-set (Union-Find).
    • Prim’s Algorithm: Priority queue-based.
  3. Network Flow
    • Ford-Fulkerson: Max flow in networks.
    • Edmonds-Karp: BFS-based implementation of Ford-Fulkerson.
  4. Advanced Graph Concepts
    • Topological Sorting: For Directed Acyclic Graphs (DAGs) (e.g., task scheduling).
    • Tarjan’s Algorithm: Strongly Connected Components (SCCs).
    • Bipartite Matching: Hopcroft-Karp algorithm.

String Algorithms

  1. Substring Search
    • Knuth-Morris-Pratt (KMP): Efficient pattern matching with prefix tables.
    • Boyer-Moore: Skips characters using heuristic rules.
    • Rabin-Karp: Hashing-based substring search.
  2. Advanced String Processing
    • Suffix Trees/Arrays: Used in genomics (DNA sequence alignment).
    • Longest Common Subsequence (LCS): Dynamic programming.
    • Edit Distance (Levenshtein Distance): For spell-checking/NLP.

Dynamic Programming (DP)

  1. Classic Problems
    • 0/1 Knapsack: Resource allocation optimization.
    • Longest Increasing Subsequence (LIS).
    • Matrix Chain Multiplication: Optimal parenthesization.
    • Coin Change: Combinatorial optimization.
  2. Advanced DP
    • Floyd-Warshall (revisited as DP).
    • Bitmask DP: For subset problems (e.g., Traveling Salesman).

Number Theory & Cryptography

  1. Essential Algorithms
    • Euclidean Algorithm: GCD/LCM calculations.
    • Sieve of Eratosthenes: Prime number generation.
    • Modular Exponentiation: Fast power calculation (used in RSA).
    • Miller-Rabin Primality Test: Probabilistic prime checking.
  2. Cryptography Basics
    • RSA Algorithm: Public-key encryption.
    • Diffie-Hellman Key Exchange: Secure key sharing.

Computational Geometry

  1. Basics
    • Convex Hull: Graham’s Scan, Jarvis’s March.
    • Line Intersection: Using parametric equations.
    • Closest Pair of Points: Divide-and-conquer.
  2. Applications
    • Voronoi Diagrams/Delaunay Triangulation: Used in GIS, graphics.
    • Sweep Line Algorithm: For interval overlaps (e.g., calendar scheduling).

Machine Learning & Optimization

  1. Foundational Algorithms
    • k-Nearest Neighbors (k-NN): Classification/regression.
    • Linear Regression: Gradient descent optimization.
    • k-Means Clustering: Unsupervised learning.
  2. Optimization
    • Gradient Descent: Core of neural network training.
    • Simulated Annealing: For combinatorial optimization.

Advanced Data Structures

  1. Efficient Querying
    • Trie: Prefix-based string storage (autocomplete).
    • Segment Tree: Range queries/updates.
    • Fenwick Tree (BIT): Prefix sums/updates.
  2. Probabilistic Structures
    • Bloom Filter: Space-efficient membership testing.
    • Skip List: Probabilistic balanced search.

Memory & System Concepts

  1. Memory Management
    • Garbage Collection: Mark-and-Sweep, Reference Counting.
    • Smart Pointers (C++): unique_ptr, shared_ptr.
  2. Low-Level Manipulation
    • Memory Alignment: For performance optimization.
    • Cache-Aware Algorithms: B-trees, blocking for matrix multiplication.

Interdisciplinary Connections

  • Bioinformatics: Suffix arrays for genome sequencing.
  • Cryptography: Number theory for encryption.
  • AI/ML: Graph algorithms for neural networks (e.g., backpropagation).
  • Robotics: A* for path planning.
  • Finance: Dynamic programming for portfolio optimization.

Why These Matter

  • Interviews: Frequently tested in FAANG-style technical rounds.
  • Research: Basis for advanced topics (e.g., quantum algorithms).
  • Real-World Systems: Used in databases, compilers, OS kernels, and more.

These are foundational for coding interviews, advanced study, and real-world applications.

1. Graph Algorithms

Shortest Path

  • Dijkstra’s Algorithm
    • What: Finds shortest path in weighted graphs (non-negative edges).
    • Importance: GPS navigation, network routing.
    • Connections: AI (pathfinding), logistics.
  • Bellman-Ford
    • What: Handles negative-weight edges.
    • Importance: Financial arbitrage, fault-tolerant systems.
  • Floyd-Warshall
    • What: All-pairs shortest paths.
    • Importance: Social network analysis, traffic flow.

Minimum Spanning Tree (MST)

  • Kruskal’s Algorithm
    • What: Uses Union-Find (greedy approach).
    • Importance: Network design (e.g., power grids).
  • Prim’s Algorithm
    • What: Priority queue-based (greedy).
    • Importance: Cluster analysis, approximation algorithms.

Network Flow

  • Ford-Fulkerson
    • What: Max flow in networks.
    • Importance: Supply chain optimization, bipartite matching.
  • Edmonds-Karp
    • What: BFS-based implementation of Ford-Fulkerson.
    • Importance: Efficient flow computation.

Advanced

  • Topological Sorting
    • What: Orders nodes in a Directed Acyclic Graph (DAG).
    • Importance: Task scheduling (e.g., build systems).
  • Tarjan’s Algorithm
    • What: Finds Strongly Connected Components (SCCs).
    • Importance: Compiler optimizations, circuit design.

2. String Algorithms

Pattern Matching

  • Knuth-Morris-Pratt (KMP)
    • What: Efficient substring search using prefix tables.
    • Importance: Text editors (search/replace), DNA sequencing.
  • Boyer-Moore
    • What: Skips characters using heuristics.
    • Importance: High-performance text search (e.g., grep).
  • Rabin-Karp
    • What: Hashing-based substring search.
    • Importance: Plagiarism detection.

Advanced String Processing

  • Suffix Trees/Arrays
    • What: Compact representations for substring queries.
    • Importance: Genomics (e.g., BLAST algorithm).
  • Longest Common Subsequence (LCS)
    • What: Dynamic programming solution.
    • Importance: Version control (diff tools), bioinformatics.

3. Dynamic Programming (DP)

Classic Problems

  • 0/1 Knapsack
    • What: Maximize value without exceeding weight.
    • Importance: Resource allocation, finance.
  • Longest Increasing Subsequence (LIS)
    • What: Finds the longest subsequence in order.
    • Importance: Bioinformatics (protein folding).
  • Matrix Chain Multiplication
    • What: Optimal parenthesization for minimal operations.
    • Importance: Compiler design (expression parsing).

Advanced DP

  • Bitmask DP
    • What: Represents subsets as bits (e.g., Traveling Salesman Problem).
    • Importance: Combinatorial optimization.

4. Number Theory & Cryptography

Essential Algorithms

  • Euclidean Algorithm
    • What: Computes GCD/LCM.
    • Importance: Cryptography (RSA), simplifying fractions.
  • Modular Exponentiation
    • What: Computes (a^b \mod m) efficiently.
    • Importance: Public-key encryption (RSA).

Cryptography

  • RSA Algorithm
    • What: Public-key encryption using prime factorization.
    • Importance: Secure data transmission (HTTPS, SSH).

5. Computational Geometry

Basics

  • Convex Hull
    • What: Jarvis’s March (greedy) or Graham’s Scan.
    • Importance: Collision detection (games), robotics.
  • Closest Pair of Points
    • What: Divide-and-conquer approach.
    • Importance: GIS, pattern recognition.

6. Memory Management

Key Concepts

  • Garbage Collection
    • What: Automatic memory reclamation (e.g., Mark-and-Sweep).
    • Importance: Java, Python memory management.
  • Smart Pointers
    • What: unique_ptr, shared_ptr (C++).
    • Importance: Preventing memory leaks in systems programming.

7. Machine Learning & Optimization

Core Algorithms

  • k-Means Clustering
    • What: Unsupervised learning for grouping data.
    • Importance: Customer segmentation, image compression.
  • Gradient Descent
    • What: Optimizes loss functions iteratively.
    • Importance: Training neural networks.

Interdisciplinary Connections

Algorithm Field Application
A* Robotics/AI Pathfinding for autonomous drones.
Suffix Arrays Bioinformatics Genome sequence alignment (BLAST).
Ford-Fulkerson Operations Research Maximizing flow in transportation networks.
Bloom Filter Distributed Systems Efficient cache lookup (e.g., databases).

Why Master These?

  • Interviews: Top companies test these (e.g., FAANG).
  • Research: Basis for cutting-edge topics (e.g., quantum algorithms).
  • Real-World Impact: Used in systems like Google Maps (Dijkstra), Git (diff tools), and HTTPS (RSA).

Next Steps

  1. Implement: Code 1-2 algorithms from each category.
  2. Visualize: Use tools like VisuAlgo to see how they work.
  3. Apply: Solve problems on LeetCode, HackerRank, or Codeforces.
Manoj Arora