📘 Complete Syllabus for DSA
Module 1: Foundations
1. Introduction to DSA
○ Importance of DSA in problem solving & interviews
○ Complexity analysis
■ Time complexity, Space complexity
■ Big-O, Big-Ω, Big-Θ
■ Best, Worst, Average cases
2. Mathematical Foundations
○ Logarithms & Exponentials
○ Recurrences & Master Theorem
○ Modular Arithmetic & Prime numbers
○ GCD, LCM, Euclid’s Algorithm
○ Fast Exponentiation
3. Programming Basics
○ Recursion (simple to advanced problems)
○ Iterative vs Recursive trade-offs
○ Bitwise operations & tricks
Module 2: Arrays & Strings
1. Arrays
○ Traversal, Insertion, Deletion
○ Prefix Sum, Sliding Window
○ Two Pointers
○ Kadane’s Algorithm (max subarray)
○ Searching (Linear, Binary Search & variants)
2. Strings
○ Basic operations (reverse, palindrome, anagram)
○ Pattern Matching:
■ Naive, KMP, Rabin-Karp
○ Z-algorithm, Prefix Function (π array)
○ String hashing
○ Tries (Prefix trees)
Module 3: Linked Lists
1. Singly Linked List
○ Insertion, Deletion
○ Reversal (iterative & recursive)
○ Middle, Cycle detection (Floyd’s algorithm)
2. Doubly & Circular Linked List
3. Advanced Problems
○ Merge two sorted lists
○ Detect & remove loop
○ LRU Cache (using DLL + HashMap)
Module 4: Stacks & Queues
1. Stacks
○ Implementation (array, linked list)
○ Applications:
■ Balanced Parentheses
■ Infix → Postfix
■ Next Greater Element
■ Min Stack
2. Queues
○ Normal Queue
○ Circular Queue
○ Deque
○ Priority Queue (Heap based)
3. Monotonic Stack / Queue
○ Sliding Window Maximum
○ Stock Span Problem
Module 5: Trees
1. Binary Trees
○ Traversals (Inorder, Preorder, Postorder, Level order)
○ Height, Diameter
○ Lowest Common Ancestor (LCA)
2. Binary Search Tree (BST)
○ Search, Insert, Delete
○ Validate BST
○ Balanced BST (AVL/Red-Black Tree overview)
3. Advanced Trees
○ Segment Tree (Range queries, Lazy Propagation)
○ Fenwick Tree (Binary Indexed Tree)
○ Tries (with strings/bitmasks)
Module 6: Heaps & Hashing
1. Heaps
○ Min Heap, Max Heap
○ Heap Sort
○ K largest/smallest problems
○ Median in Data Stream
2. Hashing
○ Hash Functions, Collisions
○ HashMaps & HashSets
○ Applications:
■ Subarray sum problems
■ Count distinct elements
■ Longest Consecutive Sequence
Module 7: Graphs
1. Graph Representation
○ Adjacency List, Matrix
○ BFS, DFS (iterative & recursive)
2. Shortest Path Algorithms
○ Dijkstra’s Algorithm
○ Bellman-Ford
○ Floyd-Warshall
3. Minimum Spanning Tree
○ Prim’s Algorithm
○ Kruskal’s Algorithm (Disjoint Set Union - DSU)
4. Advanced Graphs
○ Topological Sort (Kahn’s, DFS)
○ Strongly Connected Components (Kosaraju, Tarjan)
○ Bipartite Check
○ Bridges & Articulation Points
Module 8: Advanced Topics
1. Dynamic Programming (DP)
○ 1D DP: Fibonacci, Climbing Stairs
○ 2D DP: LCS, LIS, Matrix Chain Multiplication
○ DP on Grids: Minimum Path Sum, Unique Paths
○ Knapsack Variants
○ DP on Strings: Edit Distance
○ DP on Trees / Bitmask DP
2. Greedy Algorithms
○ Interval Scheduling
○ Activity Selection
○ Huffman Coding
3. Backtracking
○ N-Queens
○ Sudoku Solver
○ Rat in a Maze
○ Subset / Combination Generation
4. Advanced Data Structures
○ Disjoint Set Union (Union-Find)
○ Sparse Table (Range Queries)
○ Suffix Array / Suffix Tree (overview)
○ Treaps / Segment Trees with Lazy Propagation
Module 9: Problem-Solving & Competitive
Programming
1. Problem Patterns
○ Sliding Window, Two Pointers
○ Meet in the Middle
○ Binary Search on Answer
○ Prefix Sum + Hashing Tricks
2. Optimization Techniques
○ Bitmasking
○ Modular Arithmetic in Problems
○ Matrix Exponentiation
3. Practice Platforms
○ LeetCode, Codeforces, AtCoder, GFG, HackerRank
