Python Data Structures and Algorithms (DSA) Study Hub

Welcome to the Python DSA Study Hub. This repository is a public learning space designed to study and practice Data Structures and Algorithms from scratch using interactive Jupyter Notebooks. It serves as a comprehensive resource featuring theoretical explanations, step-by-step ASCII visualizations, complexity analyses, and blank implementation cells to test and run your code.

Repository Contents

The learning material is divided into two primary interactive notebooks:

1. Data Structures Notebook

The data_structures.ipynb notebook covers the core structures used to organize and store data. It is structured into two main parts:

• Linear Data Structures:

  • Arrays: Memory layouts, Row-Major vs Column-Major order, Dynamic Arrays, Jagged Arrays, and index mapping formulas.
  • Stacks: Visual representations, implementation models, Call Stack mechanics, Min Stack, Monotonic Stack, and Double Stack.
  • Queues: Circular Queues (Ring Buffers), Double-Ended Queues (Deques), Monotonic Queues, and Priority Queues.
  • Linked Lists: Singly Linked, Doubly Linked, Circular Linked Lists, Skip Lists, Unrolled Linked Lists, and Floyd's Cycle-Finding Algorithm.

• Non-Linear Data Structures:

  • Trees:
    • Binary Tree, Binary Search Tree (BST), AVL Tree (Self-Balancing BST), Red-Black Tree, and B-Tree / B+ Tree.
    • Binary Heap: Min-Heap and Max-Heap array mapping and sift operations.
    • Trie (Prefix Tree): Word insertion, search, and prefix matching.
    • Segment Tree: Construction, range queries, and point updates.
    • Fenwick Tree (Binary Indexed Tree): Least Significant Bit (LSB) indexing, prefix sum queries, and point updates.
  • Graphs: Directed vs Undirected, Weighted Graphs, DAGs, Bipartite Graphs, Adjacency Matrix, Adjacency List, Edge List, Incidence Matrix, and BFS/DFS Traversals.
  • Hash Tables: Hash function designs (division, multiplication, universal), collision resolution (Separate Chaining, Open Addressing linear/quadratic/double hashing), Load Factor, and resizing.
  • Disjoint Set Union (Union-Find): Path compression, Union by Rank, and connectivity.

2. Algorithms Notebook

The algorithms.ipynb notebook covers fundamental algorithmic paradigms and design strategies:

• Foundations of Algorithms: Asymptotic Analysis (Big O, Big Omega, Big Theta), common complexity classes, and solving recurrence relations via the Master Theorem.
• Sorting Algorithms: Bubble Sort, Selection Sort, Insertion Sort, Quick Sort (Lomuto and Hoare partitioning), Counting Sort, Radix Sort, Merge Sort, and Heap Sort.
• Searching Algorithms: Linear Search and Binary Search (iterative and recursive).
• Graph Algorithms:
  • Topological Sort: Kahn's BFS-based algorithm and DFS-based algorithm.
  • Strongly Connected Components: Kosaraju's Algorithm.
  • Shortest Path Algorithms: Dijkstra's Algorithm, Bellman-Ford Algorithm (with negative cycle detection), and Floyd-Warshall Algorithm (All-Pairs Shortest Path).
  • Minimum Spanning Tree (MST): Prim's Algorithm and Kruskal's Algorithm (using Union-Find).
  • Network Flow (Maximum Flow): Ford-Fulkerson Method and Edmonds-Karp Algorithm.
• Greedy Algorithms: Huffman Coding tree-building and prefix-free code generation.
• Mathematical Algorithms: Euclidean Algorithm (GCD) recursive and iterative.
• Dynamic Programming: Fibonacci Sequence (memoization, tabulation, space-optimization), Longest Common Subsequence (LCS), Longest Increasing Subsequence (LIS via Patience Sorting), Coin Change (Min Coins and Total Ways), Matrix Chain Multiplication, 0/1 Knapsack, and Travelling Salesman Problem (TSP via Held-Karp).
• Backtracking: N-Queens Problem, Subsets and Permutations Generation, and Sudoku Solver.
• String Matching Algorithms: Knuth-Morris-Pratt (KMP) Algorithm (LPS array precomputation) and Rabin-Karp Algorithm (Rolling Hash).

Design Philosophy

• Theoretical Explanations: Clear mathematical definitions and concept descriptions.
• ASCII Art Diagrams: Visual representations for memory allocations, pointer updates, and flow dynamics.
• Complexity Tables: Best, average, and worst-case time complexities and space complexities.
• Active Learning Format: Directly following the theory, there are requirements and empty code cells for you to write your implementation. There is no pre-written implementation code, encouraging hands-on coding practice.
• Hierarchical Header Structure: Document headers are designed to support folding in IDEs (like VS Code or JupyterLab), allowing you to collapse and expand individual topics seamlessly.

Getting Started

Prerequisites

• Python 3.10 or higher
• Jupyter Notebook or VS Code with Jupyter extension

Setup Instructions

1. Clone this repository to your local machine:

   git clone <your-repository-url>
   cd DSA

2. Create a virtual environment:

   python -m venv .venv

3. Activate the virtual environment:

   • Windows (Command Prompt):

     .venv\Scripts\activate.bat

   • Windows (PowerShell):

     .venv\Scripts\Activate.ps1

   • macOS/Linux:

     source .venv/bin/activate

4. Install Jupyter:

   pip install jupyter

5. Launch the notebook server:

   jupyter notebook

   Or open the folder in VS Code to run the notebooks using the interactive kernel.