Skip to content

Latest commit

 

History

History
272 lines (204 loc) · 6.16 KB

syllabus.md

File metadata and controls

272 lines (204 loc) · 6.16 KB

Comprehensive DSA & Algorithms Guide

This guide covers the essential topics you should know for Technical Interviews and Competitive Programming (CP). It's structured to help you focus on mastering important data structures, algorithms, and problem-solving techniques.

1. Data Structures

Basic Data Structures

  • Arrays
  • Strings
  • Linked Lists (Singly, Doubly)
  • Stacks
  • Queues (Regular, Deque, Priority Queue)
  • Heaps (Min-Heap, Max-Heap)
  • Hashing (HashMap, HashSet)
  • Disjoint Set Union (Union-Find)

Advanced Data Structures

  • Trees (Binary Tree, Binary Search Tree, AVL Tree, Segment Tree, Fenwick Tree)
  • Trie
  • Graph (Adjacency List, Adjacency Matrix)
  • Heap (Priority Queue)
  • Suffix Tree
  • AVL Tree / Red-Black Tree

Special Data Structures

  • Matrix (Sparse Matrix)
  • Graph Representations (Adjacency List, Adjacency Matrix)
  • B+ Tree
  • Fenwick Tree (Binary Indexed Tree - BIT)

2. Algorithms

Sorting & Searching

Sorting Algorithms

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

Searching Algorithms

  • Binary Search
  • Linear Search
  • Ternary Search
  • Exponential Search

Dynamic Programming (DP)

Basic Concepts

  • Memoization
  • Tabulation
  • State Transition, Recursion
  • Knapsack Problem (0/1, Unbounded, Fractional)

Important DP Problems

  • Longest Common Subsequence (LCS)
  • Longest Increasing Subsequence (LIS)
  • Coin Change Problem
  • Matrix Chain Multiplication
  • Rod Cutting
  • Subset Sum Problem

Greedy Algorithms

Key Greedy Algorithms

  • Activity Selection
  • Fractional Knapsack
  • Huffman Encoding
  • Job Sequencing Problem
  • Prim’s Algorithm (MST)
  • Kruskal’s Algorithm (MST)

Graph Algorithms

Basic Graph Algorithms

  • Breadth-First Search (BFS)
  • Depth-First Search (DFS)
  • Dijkstra’s Algorithm (Shortest Path)
  • Bellman-Ford Algorithm
  • Floyd-Warshall Algorithm (All-Pairs Shortest Path)

Advanced Graph Algorithms

  • Topological Sort
  • Strongly Connected Components (Kosaraju's Algorithm, Tarjan’s Algorithm)
  • Kruskal’s Algorithm (Minimum Spanning Tree)
  • Prim’s Algorithm (Minimum Spanning Tree)
  • Articulation Points and Bridges

Backtracking

Key Backtracking Problems

  • N-Queens Problem
  • Sudoku Solver
  • Subset Sum Problem
  • Permutations and Combinations

Divide and Conquer

Important Algorithms

  • Merge Sort
  • Quick Sort
  • Binary Search
  • Closest Pair of Points
  • Strassen’s Matrix Multiplication

String Algorithms

Key Algorithms

  • Knuth-Morris-Pratt (KMP) Algorithm (Pattern Matching)
  • Rabin-Karp Algorithm (Pattern Matching)
  • Manacher’s Algorithm (Longest Palindromic Substring)
  • Z-Algorithm (Pattern Matching)
  • Suffix Arrays

3. Advanced Topics

Mathematical Algorithms

Number Theory

  • Sieve of Eratosthenes
  • Prime Factorization
  • GCD and LCM (Euclidean Algorithm)
  • Fast Exponentiation
  • Modular Arithmetic
  • Chinese Remainder Theorem

Combinatorics

  • Permutations and Combinations
  • Binomial Coefficient
  • Catalan Numbers

Geometry

Important Concepts

  • Convex Hull (Graham Scan, Jarvis March)
  • Line Intersection
  • Point in Polygon Problem
  • Polygon Area Calculation
  • Sweep Line Algorithms

Bit Manipulation

Key Operations

  • Bitwise AND, OR, XOR
  • Counting Set Bits (Brian Kernighan's Algorithm)
  • Power of Two (Fast Check)
  • Finding the Single Non-Repeating Element

Segment Tree

Basic Concepts

  • Range Query and Update
  • Lazy Propagation

Applications

  • Range Sum Query
  • Range Minimum/Maximum Query
  • Interval Addition

4. Problem-Solving Patterns

1. Sliding Window

  • Used to solve problems involving subarrays or substrings.
    • Example: Longest Substring Without Repeating Characters

2. Two Pointer Technique

  • Used for sorted arrays/linked lists to solve problems efficiently.
    • Example: Finding pairs in sorted arrays, trapping rainwater

3. Divide and Conquer

  • Break a problem into smaller sub-problems, solve them independently.
    • Example: Merge Sort, Quick Sort, Binary Search

4. Greedy Method

  • Make locally optimal choices hoping for a global optimum.
    • Example: Activity Selection, Fractional Knapsack

5. Binary Search on Answer

  • Search for an optimal solution in a range.
    • Example: Finding smallest/largest value satisfying a condition

6. Backtracking

  • Explore all possible solutions, undoing decisions if needed.
    • Example: N-Queens Problem, Sudoku Solver

7. Hashing

  • Use hash tables for efficient storage and lookup.
    • Example: Finding duplicates, subset sum problems

8. Dynamic Programming

  • Solve overlapping sub-problems optimally.
    • Example: Longest Common Subsequence, Coin Change Problem

9. Prefix Sum / Difference Array

  • Efficiently answer range queries after preprocessing.
    • Example: Range sum queries, range updates

5. Key Techniques

  • Difference Array
  • Fenwick Tree (Binary Indexed Tree)
  • Segment Tree with Lazy Propagation
  • Union-Find (Disjoint Set Union)
  • Mo’s Algorithm (for Range Queries)
  • Bitwise Operations (AND, OR, XOR, etc.)
  • Topological Sorting
  • Convex Hull
  • Sieve of Eratosthenes
  • Knuth-Morris-Pratt Algorithm

6. Other Important Concepts

Graph Theory

  • Graph Representations: Adjacency List, Adjacency Matrix
  • Graph Traversal: BFS, DFS
  • Cycle Detection
  • Shortest Path Algorithms: Dijkstra, Bellman-Ford, Floyd-Warshall
  • Minimum Spanning Tree: Kruskal, Prim

Data Structures

  • Heaps / Priority Queue
  • Trie
  • Graph Traversal (DFS, BFS)
  • Disjoint Set Union (Union-Find)

Computational Geometry

  • Convex Hull
  • Line Sweep Algorithm
  • Segment Intersection

Greedy Algorithms

  • Activity Selection Problem
  • Fractional Knapsack
  • Huffman Encoding

Conclusion

Mastering the topics and algorithms listed above will prepare you for both interviews and competitive programming. Understanding the principles behind each algorithm and technique will help you apply them efficiently to solve a variety of problems.