OL Problem-Solving Algorithms Memory-Management

Manoj Arora

2 years ago

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

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

Graph Algorithms

Shortest Path Algorithms
- Floyd-Warshall: All-pairs shortest paths (dynamic programming).
- Bellman-Ford: Handles negative-weight edges.
- A*: Heuristic-based pathfinding (AI/games).
Minimum Spanning Tree (MST)
- Kruskal’s Algorithm: Uses disjoint-set (Union-Find).
- Prim’s Algorithm: Priority queue-based.
Network Flow
- Ford-Fulkerson: Max flow in networks.
- Edmonds-Karp: BFS-based implementation of Ford-Fulkerson.
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

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.
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)

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

Number Theory & Cryptography

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.
Cryptography Basics
- RSA Algorithm: Public-key encryption.
- Diffie-Hellman Key Exchange: Secure key sharing.

Computational Geometry

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

Machine Learning & Optimization

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

Advanced Data Structures

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

Memory & System Concepts

Memory Management
- Garbage Collection: Mark-and-Sweep, Reference Counting.
- Smart Pointers (C++): unique_ptr, shared_ptr.
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

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