Data Structures & Algorithms
Arrays, Linked Lists, Trees, Graphs, Dynamic Programming & Time Complexity Analysis
This is the Data Structures & Algorithms syllabus taught for GATE Computer Science & IT. Each topic opens as a full chapter — theory, worked examples and the traps that paper actually uses.
Topics in Data Structures & Algorithms
- Arrays and StringsContiguous array storage, string manipulation, prefix sums and in place techniques.
- AVL TreesHeight-balanced binary search trees: balance factor, rotations, insert, delete and when an AVL beats a plain BST.
- B-TreesMulti-way search trees of order m: node occupancy, search, insert-with-split, delete-with-borrow-or-merge, and why disk indexes use them.
- Binary SearchBinary search on sorted data and on answer spaces for optimization problems.
- Bit ManipulationBitwise operations and tricks for masks, counting bits and set operations.
- Branch and BoundState-space search with live nodes, bounding functions, 0/1 knapsack and the travelling-salesman decision to prune.
- Time and Space ComplexityAsymptotic analysis with Big O notation for time and space, including recurrence solving.
- Convex HullThe smallest convex polygon containing a point set: Graham scan (polar sort plus left-turn stack), the CCW test, and the divide-and-conquer merge by common tangents.
- Strassen Matrix MultiplicationDivide-and-conquer matrix multiply: why eight half-size products still cost $n^3$, Strassen's seven products, the $\Theta(n^{\log_2 7})$ recurrence, and when the extra additions…
- DP for the Travelling SalesmanHeld–Karp optimisation TSP: state (S, j) is the cheapest path from city 1 through exactly the cities in S ending at j, in $O(n^2 2^n)$ — the shortest tour, not the NPC decision…
- Dynamic ProgrammingSolving problems with overlapping subproblems using memoization and tabulation.
- Advanced Graph AlgorithmsShortest path, minimum spanning tree and topological sort algorithms on weighted graphs.
- Graph Colouring by Backtrackingm-colouring as a search: assign each vertex a colour in 1..m, abandon a partial colouring the moment a neighbour clash appears. Distinct from the chromatic-number decision…
- Greedy AlgorithmsMaking locally optimal choices to reach a global optimum for suitable problems.
- Hashing and Hash MapsHash tables, collision handling and using maps and sets for constant time lookups.
- Heaps and Priority QueuesBinary heaps and priority queues for efficient access to minimum or maximum elements.
- Job Sequencing with DeadlinesOne machine, unit-time jobs, each with a deadline and a profit: sort by profit and place each job in the latest free slot that still meets its deadline.
- Linked ListsSingly and doubly linked lists, pointer manipulation, reversal and cycle detection.
- P, NP and NP-CompletenessDecision versus optimisation, the classes P, NP, NP-hard and NP-complete, polynomial reductions, and Cook's theorem.
- NP-Complete Graph ProblemsClique, chromatic-number and TSP as decision problems, the complement reduction between clique and independent set, and what NP-completeness licenses.
- NP-Hard SchedulingIdentical-processor makespan (2 machines ≡ PARTITION) and job-shop (named machines, per-job routes). Problem statements, one reduction you can finish by hand, and LPT as a…
- Optimal Binary Search TreesChoose BST shape to minimise expected search cost: the $O(n^3)$ DP $e[i,j] = w[i,j] + \min_r\,(e[i,r-1]+e[r+1,j])$, filled by increasing span on a three-key instance.
- Recursion and BacktrackingRecursive problem solving and backtracking to explore permutations, subsets and combinations.
- Searching and SortingComparison sorts like merge and quick sort plus linear and non comparison sorts.
- Stacks and QueuesLIFO stacks and FIFO queues with applications like expression parsing and monotonic stacks.
- Trees and GraphsBinary trees, binary search trees, traversals and graph representations with BFS and DFS.
- Two Pointers and Sliding WindowTwo pointer traversal and sliding window techniques for subarray and substring problems.
Practise Data Structures & Algorithms
Reading every chapter below is free and needs no account. Practice, mocks and progress live in the app.
Continue with Google — freeNo card, no trial. Works offline once installed.