BEFORE YOU BEGIN

Start with the right foundations

Arrays, linked structures, recursion, logarithms and summations.

3 key concepts1 worked example3 revision checks

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.

Concept 1

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.

Concept 2

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.

Concept 3

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. 1

    After k doublings, i = 2^k.

  2. 2

    The final valid k is floor(log2 n).

  3. 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.