Fundamental Data Structures and Algorithms 🧑‍💻

This is a collaborative repo containing all the fundamental data structures and algorithms. The goal is to create an environment to learn and experiment with all the essential data structures and algorithms.

---

Overview

The following is a list of all the essential data structures and algorithms making up a comprehensive base for software engineering, data-intensive applications, and computer science problem-solving.

If you want to contribute to this repository, the list can be seen as a to-do list!

Data Structures

1. Arrays and Lists

• Dynamic Arrays
• Linked Lists (Singly, Doubly, Circular)

2. Stacks and Queues

• Stack (using arrays and linked lists)
• Queue (using arrays and linked lists)
• Deque (Double-Ended Queue)
• Priority Queue (implemented with Heaps)

3. Hashing and Hash Tables

• Hash Maps / Dictionaries
• Collision Resolution Techniques (Chaining, Open Addressing)

4. Trees

• Binary Trees
• Binary Search Trees (BST)
• Balanced Trees (AVL Tree, Red-Black Tree)
• Segment Trees and Fenwick Trees (for range queries)
• Interval Trees
• Trie (Prefix Tree)
• Suffix Trees and Suffix Arrays

5. Heaps

• Min-Heap and Max-Heap
• Binary Heap
• Fibonacci Heap
• Pairing Heap

6. Graphs

• Representation: Adjacency Matrix, Adjacency List
• Types: Directed, Undirected, Weighted, Unweighted
• Specialized Graphs (DAGs, Trees as Graphs)

7. Advanced Data Structures

• Disjoint Set (Union-Find)
• Bloom Filters
• Skip Lists
• B-Trees and B+ Trees
• K-D Trees and Quadtrees (for spatial data)
• LRU Cache (with Doubly Linked List and Hash Map)

---

Algorithms

1. Sorting Algorithms

• Bubble Sort, Selection Sort, Insertion Sort
• Merge Sort, Quick Sort, Heap Sort
• Counting Sort, Radix Sort, Bucket Sort

2. Searching Algorithms

• Linear Search
• Binary Search (and Binary Search Variants)
• Interpolation Search
• Exponential Search

3. Graph Algorithms

• Depth-First Search (DFS), Breadth-First Search (BFS)
• Shortest Path Algorithms (Dijkstra’s, Bellman-Ford)
• *A Search Algorithm**
• Floyd-Warshall (All-Pairs Shortest Path)
• Minimum Spanning Tree (Kruskal’s, Prim’s)
• Topological Sorting (for Directed Acyclic Graphs)
• Strongly Connected Components (Kosaraju’s, Tarjan’s)
• Network Flow (Ford-Fulkerson, Edmonds-Karp)

4. Dynamic Programming

• Knapsack Problem (0/1 Knapsack, Unbounded Knapsack)
• Longest Common Subsequence (LCS)
• Longest Increasing Subsequence (LIS)
• Matrix Chain Multiplication
• Coin Change Problem
• Edit Distance (Levenshtein Distance)

5. Greedy Algorithms

• Activity Selection Problem
• Fractional Knapsack Problem
• Huffman Coding
• Minimum Number of Coins

6. Mathematical Algorithms

• Prime Number Algorithms (Sieve of Eratosthenes)
• GCD (Euclidean Algorithm)
• Fast Exponentiation
• Modular Arithmetic and Modular Exponentiation
• Combinatorics (Permutations, Combinations)
• Integer Factorization

7. Backtracking and Recursion

• Permutations and Combinations
• N-Queens Problem
• Sudoku Solver
• Rat in a Maze Problem
• Subset Sum Problem

8. String Algorithms

• Pattern Searching (KMP, Rabin-Karp)
• Longest Common Prefix
• Z Algorithm
• Manacher’s Algorithm (for Palindromic Substrings)

9. Advanced Algorithms

• Divide and Conquer (for complex recursive problems)
• Bit Manipulation Techniques
• Randomized Algorithms (e.g., Quickselect)
• Monte Carlo and Las Vegas Algorithms (Randomized Primality Testing)
• Approximation Algorithms (for NP-hard problems)

---

Specialized Topics

1. Computational Geometry

• Convex Hull (Graham’s Scan, Jarvis March)
• Line Intersection
• Closest Pair of Points

2. Data Compression Algorithms

• Run-Length Encoding
• LZW Compression
• Huffman Coding

3. Machine Learning-related Structures and Algorithms

• K-nearest neighbors (with KD-Trees or Ball Trees)
• Clustering Algorithms (K-Means, DBSCAN)
• PCA and Singular Value Decomposition (SVD)