ADS

Algorithms & Data Structures. The module that asks two questions about every piece of code you will ever write: how long does it take when the input gets big, and which structure should the data live in so that the operations you need are cheap.

It starts with the measuring instrument — counting primitive operations, discarding constants, and classifying what remains with the O-notation — and with recursion as the second way (next to iteration) of expressing a repeated computation. From there it walks the standard catalogue: the linear structures (lists, stacks, queues, deques, iterators), trees and their traversals, priority queues and heaps, sets/maps and hash tables, then the search trees (BST, AVL, Splay) where the balance discipline is what keeps the logarithmic promise. The sorting block covers merge-sort and quick-sort, the comparison-sort lower bound of $O(n \log n)$ and how radix-sort slips past it by not comparing at all. The last third is graphs: representations, spanning trees, depth-first and breadth-first traversal, directed acyclic graphs and topological sorting, and finally weighted graphs and shortest-path trees.

Throughout, the pattern is the same: a data structure is a bargain — it makes some operations cheap by making others expensive, and knowing the bargain is knowing when to use it.