Lesson

Graphs and Recurrences

Graph traversal explores vertices and edges. Breadth-first search uses a queue to explore level by level; depth-first search uses a stack (often the call stack) to go deep before backtracking.

Practice

Q1

Which data structure does breadth-first search use?

Show hint

It explores in waves — first in, first out.

Q2

Which data structure does depth-first search use?

Show hint

It dives deep, backtracking last.

Divide-and-conquer algorithms have running times described by recurrences. The recurrence $T(n) = 2T(n/2) + n$ — the shape of merge sort — solves to $O(n \\log n)$ by the Master theorem.

Quiz

Q1

The recurrence $T(n) = 2T(n/2) + n$ solves to:

Show hint

This is the merge-sort recurrence.

Q2

How many edges does the complete graph $K_4$ have?

Show hint

Every pair of the 4 vertices is joined.

Q3

How many edges does a tree with $6$ nodes have?

Show hint

A tree with $n$ nodes has $n - 1$ edges.