GATE CSE Algorithms and Data Structures notes
Separate the algorithm, its assumptions and the cost model. Practise tracing before estimating asymptotic complexity.
BEFORE YOU BEGIN
Start with the right foundations
Arrays, linked structures, recursion, logarithms and summations.
Original introductory notes with source references. The example is a teaching exercise, rather than an official worked solution to a GATE question. Use the full syllabus to track coverage.
01 · UNDERSTAND
Key concepts
Use these ideas to reason through a question before choosing a formula or an answer.
Asymptotic cost
O gives an upper bound, Ω a lower bound and Θ a tight asymptotic bound. State whether the question asks for worst, average or best case. Nested loops are not always quadratic: the iteration count depends on their limits.
Graph algorithms
BFS gives shortest paths measured in edges in an unweighted graph. Dijkstra requires nonnegative edge weights. A minimum spanning tree minimizes total connecting weight and need not give shortest paths from a source.
Dynamic programming
Define the state, recurrence, base cases and evaluation order. The cost usually follows from the number of reachable states multiplied by the work per state, with memoization or a table preventing repeated evaluation.
02 · WORK THROUGH IT
A worked teaching example
Attempt the problem first, then trace each step and compare your reasoning.
The problem
How many times does the body run when i takes values 1, 2, 4, ... while i ≤ n, and each iteration performs constant work? Assume integer n ≥ 1.
Step-by-step reasoning
- 1
After k doublings, i = 2^k.
- 2
The final valid k is floor(log2 n).
- 3
Count k = 0 through floor(log2 n), inclusive.
Check your result
Compare your calculation and assumptions.
The body runs floor(log2 n) + 1 times; running time is Θ(log n).
03 · SPOT THE TRAPS
Common mistakes
- Using Dijkstra on graphs with negative edges.
- Ignoring the initial iteration when counting doublings.
- Reporting auxiliary recursion-stack memory as zero.
04 · CHECK YOUR UNDERSTANDING
Revision checklist
- Trace a small input.
- State edge-weight and input-size assumptions.
- Count time and auxiliary space separately.
Explain each point without the notes, then check it with an unfamiliar question. Print or save these notes as a PDF for your revision session.
05 · APPLY IT
Put these ideas into practice
Attempt related previous year questions and record the reasoning behind any mistakes.
Algorithms
84 archived questions
Programming and Data Structures
106 archived questions
Plan your next revision session
Explore topic history or move to another note.
READ FURTHER
Study references
Use the original references for a fuller explanation and more worked problems.