Algorithm
Checkpoints
- Breadth-First Search Basis Breadth-first search explores a graph layer by layer from a chosen source, visiting all vertices at distance k before any at distance k+1. This checkpoint develops BFS using a queue, proves it computes shortest-path distances in unweighted graphs, and analyses its O(V+E) running time.
- Binary Search Basis Binary search locates a value in a sorted array in O(log n) time by repeatedly halving the search interval. This checkpoint develops the algorithm, walks through its invariant, and shows how subtle off-by-one mistakes in the boundary update destroy correctness.
- Depth-First Search Basis Depth-first search explores a graph by going as deep as possible from each vertex before backtracking. This checkpoint develops both recursive and explicit-stack formulations, traces the discovery and finishing times that drive applications like cycle detection and topological sort, and analyses its O(V+E) running time.
- Introduction to Algorithms Basis An algorithm is a finite, unambiguous procedure that transforms input to output. This checkpoint sets out what makes a procedure an algorithm, why correctness and efficiency are the two questions you must always ask about one, and previews the families of algorithms that follow.
- Asymptotic Notations Basis Big-O, big-Ω, and big-Θ are the language used to talk about how a function grows as its input gets large. This checkpoint defines each notation precisely, contrasts upper, lower, and tight bounds, and shows how they let you compare algorithms without worrying about hardware or constants.
- Time Complexity Basis Time complexity counts how the running time of an algorithm scales with the size of its input. This checkpoint walks through how to count elementary operations, how to express the result with asymptotic notation, and how to read off the dominant cost from common control-flow patterns.