Data Structures and Algorithms (DSA) Topics and Important Algorithms

---

Data Structures

1. Arrays

• Basics: Insert, Delete, Update
• Sliding Window Technique
• Two Pointer Technique
• Kadane’s Algorithm (Max Subarray Sum)
• Prefix Sum and Difference Array

2. Strings

• String Matching Algorithms:
  • Naive Method
  • KMP Algorithm
  • Rabin-Karp Algorithm
• Palindrome Check
• Longest Palindromic Substring
• Z Algorithm
• Trie Data Structure (Prefix Tree)

3. Linked List

• Singly Linked List
• Doubly Linked List
• Circular Linked List
• Reverse a Linked List (Iterative and Recursive)
• Detect Cycle in a Linked List (Floyd’s Cycle Detection)
• Merge Two Sorted Linked Lists
• Intersection of Two Linked Lists

4. Stacks and Queues

• Stack:
  • Infix to Postfix/Prefix Conversion
  • Next Greater/Smaller Element
  • Balanced Parentheses Check
• Queue:
  • Circular Queue
  • Deque (Double-Ended Queue)
  • Priority Queue

5. Trees

• Binary Tree:
  • Traversals: Inorder, Preorder, Postorder (Recursive and Iterative)
  • Height of Tree
  • Diameter of Tree
  • Lowest Common Ancestor
• Binary Search Tree:
  • Insertion, Deletion
  • Validate BST
  • Kth Smallest/Largest Element
• Advanced Trees:
  • AVL Tree
  • Segment Tree
  • Fenwick Tree (Binary Indexed Tree)
  • Trie

6. Graphs

• Representation (Adjacency Matrix/List)
• Breadth-First Search (BFS)
• Depth-First Search (DFS)
• Shortest Path Algorithms:
  • Dijkstra’s Algorithm
  • Bellman-Ford Algorithm
  • Floyd-Warshall Algorithm
• Minimum Spanning Tree:
  • Kruskal’s Algorithm
  • Prim’s Algorithm
• Topological Sorting
• Strongly Connected Components (Tarjan’s Algorithm/Kosaraju’s Algorithm)

7. Hashing

• Hash Table
• Hash Maps (Chaining, Open Addressing)
• Collision Resolution Techniques
• Frequency Counting Problems

8. Heaps

• Min Heap and Max Heap
• Heapify Operation
• Kth Largest/Smallest Element
• Median in a Stream
• Heap Sort

9. Recursion and Backtracking

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

10. Dynamic Programming (DP)

• Knapsack Problems (0/1 and Unbounded)
• Longest Common Subsequence (LCS)
• Longest Increasing Subsequence (LIS)
• Matrix Chain Multiplication
• Subset Sum Problem
• Coin Change Problem
• DP on Trees (Diameter, Path Sum)
• DP on Graphs

11. Greedy Algorithms

• Activity Selection Problem
• Huffman Encoding
• Job Sequencing Problem
• Fractional Knapsack Problem

12. Divide and Conquer

• Merge Sort
• Quick Sort
• Binary Search (and its variants)
• Maximum Subarray Problem (Divide and Conquer version)

---

Important Algorithms

1. Sorting Algorithms

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

2. Searching Algorithms

• Binary Search and Variants (First/Last Occurrence, Peak Element)
• Ternary Search
• Exponential Search

3. Mathematics

• Sieve of Eratosthenes (Prime Numbers)
• Euclidean Algorithm (GCD)
• Modular Exponentiation
• Matrix Exponentiation
• Number Theory (LCM, Modular Arithmetic)
• Combinatorics (nCr Calculation)

4. Bit Manipulation

• Basic Operations (AND, OR, XOR, Left/Right Shifts)
• Count Set Bits (Brian Kernighan’s Algorithm)
• Find the Single Number
• Subset Generation Using Bits
• Fast Exponentiation

5. Sliding Window

• Maximum/Minimum in a Sliding Window
• Longest Substring Without Repeating Characters
• Longest Subarray with Sum K

6. Advanced Algorithms

• Disjoint Set Union (DSU)/Union-Find
• Floyd’s Cycle Detection Algorithm
• KMP Algorithm for Pattern Matching
• Rabin-Karp Algorithm
• Fast Fourier Transform (FFT)

---