Algorithms
“Master asymptotic analysis, Master Theorem, divide-and-conquer recurrences, greedy matroid optimality, dynamic programming memoization, graph traversals, shortest paths, and NP-completeness reductions.”
A rigorous, mathematically formal study notebook covering asymptotic growth hierarchies, recurrence trees, comparison sorting lower bounds, linear-time selection, Huffman coding, minimum spanning trees, 0/1 Knapsack, matrix chain multiplication, graph traversals, Dijkstra, Bellman-Ford, Floyd-Warshall, and Cook-Levin reduction chains for semester examinations and top-percentile GATE CS/IT & DA performance.
Structured Notes & Exam Lens
A · B.Tech Structured Study Sequence
5 Sections · Full CurriculumAsymptotic Notations & Recurrences
Formal mathematical definitions of Big-O, Omega, Theta, Little-o, Little-omega, limit quotients, dominance hierarchies, recurrence trees, and standard/extended Master Theorem cases.
Formal definitions of O, Omega, Theta, o, omega, limit tests, Stirling's approximation, and dominance ranking.
Comparing f(n) with n^{log_b a}, extended Master cases, substitution proofs, and change of variables.
Sorting, Selection & Priority Queues
Merge Sort inversion counting, Lomuto vs Hoare partitions, randomized quicksort expected bounds, deterministic median-of-medians linear selection, decision tree lower bounds, non-comparison sorting, and binary heap mathematics.
Inversion counting, Hoare vs Lomuto partitions, randomized quicksort expected O(n log n), and BFPRT Median-of-Medians.
Omega(n log n) decision tree bound, Counting/Radix/Bucket sort, linear-time Build-Heap, and Heap Sort.
Greedy Strategies & Dynamic Programming
Greedy choice property, exchange arguments, Huffman coding, minimum spanning trees (Kruskal with DSU, Prim), 0/1 Knapsack pseudo-polynomial bounds, LCS, LIS, and Matrix Chain Multiplication parenthesizations.
Optimal substructure vs greedy-choice property, activity selection, and Huffman prefix codes.
Cut Property, Cycle Property, Kruskal with DSU, Prim with priority queues, and uniqueness theorems.
Overlapping subproblems, 0/1 Knapsack pseudo-polynomial complexity, LCS table reconstruction, and LIS in O(n log n).
Optimal parenthesization, Catalan number state space, O(n^3) table formulation, and DP on DAGs.
Graph Traversals & Shortest Paths
Adjacency representations, BFS level frontiers, DFS discovery/finish timestamps, edge classification (tree, back, forward, cross), Topological Sort, Kosaraju/Tarjan SCCs, Dijkstra with heaps, Bellman-Ford negative cycle detection, Floyd-Warshall, and Johnson's algorithm.
BFS/DFS edge classification, discovery/finish timestamps, Kahn's algorithm, and Kosaraju/Tarjan SCCs.
Non-negative edge Dijkstra, negative edge relaxation, negative cycle detection, and all-pairs dynamic programming.
Computational Complexity & NP-Completeness
Decision problems, complexity classes P, NP, co-NP, NP-Hard, NP-Complete, polynomial certificates, Cook-Levin theorem, and classic polynomial-time reduction chains.
Deterministic vs non-deterministic polynomial time, polynomial certificates, Cook-Levin theorem, and reduction chains.
B · GATE 2027 Syllabus Scope
Official syllabus scope and related lesson coverage; topics outside the syllabus are marked as enrichment.
- •Asymptotic analysis: Big-O, Omega, Theta, Little-o, Little-omega notations, order of growth hierarchy
- •Recurrence relations: Substitution method, recursion trees, Master Theorem (standard and extended cases)
- •Divide-and-Conquer: Merge Sort, Quick Sort (partition schemes, randomized expected time), linear-time selection (QuickSelect, Median-of-Medians)
- •Sorting bounds and priority queues: Comparison sorting lower bound Omega(n log n), Counting Sort, Radix Sort, Bucket Sort, binary heaps, linear-time Build-Heap, Heap Sort
- •Greedy algorithms: Greedy choice property, optimal substructure, Fractional Knapsack, Activity/Interval Selection, Huffman prefix codes
- •Minimum Spanning Trees: Cut Property, Cycle Property, Kruskal with Disjoint Set Union (DSU), Prim's algorithm, uniqueness conditions
- •Dynamic programming: Overlapping subproblems, 0/1 Knapsack (pseudo-polynomial time), Longest Common Subsequence (LCS), Longest Increasing Subsequence (LIS)
- •Advanced dynamic programming: Matrix Chain Multiplication (Catalan number bounds), DP on DAGs, Held-Karp TSP
- •Graph traversals and connectivity: Adjacency representations, BFS, DFS edge classification (tree, back, forward, cross), Topological Sort (Kahn's and DFS), Strongly Connected Components (Kosaraju, Tarjan)
- •Shortest paths: BFS for unweighted graphs, DAG topological relaxation, Dijkstra with heaps, Bellman-Ford negative cycle detection, Floyd-Warshall APSP, Johnson's algorithm
- •Computational complexity: Classes P, NP, co-NP, NP-Hard, NP-Complete, polynomial-time reductions, Cook-Levin theorem, classic NP-complete reductions
Interactive Labs & Verified PYQs
Revision & Rapid Review Sheets
Authoritative Textbooks & Video Lectures
All notes in this notebook cross-reference standard academic literature. We do not pretend student notes substitute for classical texts — they guide you through them.
Curated lectures from verified educators (Gate Smashers, Neso Academy, Knowledge Gate, and MIT OCW) selected specifically for difficult concept visualizations.
These notes are open and maintained together.
Found a factual mistake? Have a clearer explanation or mental model? Created a useful diagram or worked out a tricky GATE question? Help make this notebook better for every student who opens it next.