Data Structures and Algorithms

This is Unit Three of Computer Science, Part Two: algorithms and complexity. The part opens with a fact that reframes the whole subject. Every algorithmic problem has a brute answer — inputs are finite, so an exhaustive search always exists. Which means the question is never whether a problem can be solved. The question is what it costs, and how that cost grows. So the middle of this part is about measurement — counting steps, naming orders of growth, and being precise about what those names describe. Three error entries, and they guard three different confusions. Forgetting that a model did deliberate violence to reality. Reading a growth order as a stopwatch. And the most common misreading in the whole field, about what the letters N and P actually stand for. And the capstone earns its place: one route request from a phone, traced through every idea the unit numbered. By the end you will be able to do five things. One: say why a brute answer always exists, and what that makes the real question. Two: say what a model does, and the error of forgetting it. Three: say what an order of growth describes and what it does not. Four: say why greedy methods usually miss the best answer. Five: say what NP means, and why the obvious reading is wrong.

Three entries. Why solvability is never the issue, what happens to a real problem before any algorithm touches it — and an error entry about the step people forget once they are working inside the model.

Why solvability is not the issue.

CS 0118 Algorithmic Problem-Solving

Every algorithmic problem has a brute answer, because inputs are finite and exhaustive search therefore exists. So the interesting question is never whether — it is at what cost.

What happens first.

CS 0120 The Problem Model

A simplified representation emphasising the details somebody judged relevant and discarding the rest. Everything the algorithm does afterwards happens inside that judgment.

And the error.

CS 0121 "The Model Is the World"

Treating the model as the reality it simplified mistakes the frame for the picture. Every model did deliberate violence to the world — usefully, and on purpose — and forgetting that is where confident wrong answers come from.

Three entries on measurement. Two resources, a method for counting that ignores how fast the machine is, and the observation that one algorithm carries several different numbers depending on what it is handed.

Two resources.

CS 0123 Time and Space Complexity

How long an algorithm takes as the problem grows, and how much memory it needs. Two separate costs, and improving one often worsens the other.

How cost is counted.

CS 0125 Counting Steps

Counting steps, with each basic operation — a lookup, an addition, a comparison — counting as one. The count is deliberately independent of how fast any particular machine is.

Several counts.

CS 0126 Best Case and Worst Case

One algorithm has a best case where the input cooperates and a worst case where it resists. Each is a separate claim, and quoting one without saying which is incomplete.

Three entries on what actually gets compared. Not how long something takes, but how the cost grows as the problem gets bigger — and an error entry about the difference, which is the one people find hardest to keep hold of.

The prediction.

CS 0127 The Order of Growth

A geometric prediction of cost as size increases — constant staying flat, linear rising steadily, and others climbing far faster. The shape is what matters.

The notation.

CS 0128 Big O Notation

Notation naming an order of growth, with a cost belonging to a class when their ratio stays bounded as inputs grow. It names the shape rather than the size.

And the error.

CS 0129 "Big O Is a Stopwatch"

It describes growth rather than elapsed time. Hardware a thousand times faster runs a linear algorithm sooner and its growth order is unchanged — which is exactly why the notation is useful.

Six entries covering four ways of building an algorithm, and the honest limit attached to the fourth. One of these families is fast, appealing, and usually wrong — and the entry says so plainly.

The first family.

CS 0135 Divide and Conquer

Break a problem into smaller versions of itself, solve each recursively, and combine the answers. The recursion from Unit Two, applied as a strategy.

The second.

CS 0136 Brute Force

Generate every candidate solution in the space and keep the best. It always works, which is what makes the next entry matter.

And why that is not enough.

CS 0137 The Combinatorial Explosion

The solution space grows exponentially as the problem grows — each added element multiplies the possibilities rather than adding to them. Always working and being usable are different things.

The third family.

CS 0138 The Greedy Method

Build one solution by repeatedly taking whatever looks best right now. Fast, simple, and requiring no lookahead at all.

And its limit.

CS 0139 "Greedy Finds the Best"

Most greedy algorithms find a solution rather than the best one — an early win can block a better total later. Only specially structured problems make greed provably safe.

The fourth.

CS 0140 The Reduction

Transform the problem into a different one that has already been solved, run that solution, and translate the answer back. Solving by relocation rather than by attack.

Six entries applying the measurement machinery. Two searches with their costs stated, three sorts, and one technique that changes the problem of finding something rather than making the search faster.

The first search.

CS 0143 Sequential Search, Measured

Checking each element in turn for the target, with cost growing in step with the collection. Doubling the collection doubles the work.

The second.

CS 0144 Binary Search, Measured

Halving the interval each step, with cost growing very slowly. But only on a sorted list with direct access by position — halving depends on both conditions, and losing either loses the guarantee.

A sort, worked.

CS 0145 Merge Sort, Run to the Floor

Divide the list into halves until every piece holds one element — sorted by definition — then merge the pieces back in order. The dividing does the work.

A second sort.

CS 0147 Quicksort

Partition around a chosen element, smaller to one side and larger to the other, then sort each side the same way. The choice of that element is what decides the cost.

A third.

CS 0148 Heapsort

Add every element to a heap using comparison as priority, then remove the top repeatedly. Part One's structure doing the job it was shaped for.

And the different move.

CS 0149 Hashing

Assigning each object a computed integer index — an address rather than a location to search for. It changes finding from a search into a calculation.

Four entries on the most general structure from Part One. Two ways of walking one — which are the same two strategies from the search unit of the AI course, met again — and two classic problems.

The first traversal.

CS 0150 Depth-First Search

Explore each neighbour recursively as far as the path goes before backing up. Diving rather than sweeping.

The second.

CS 0151 Breadth-First Search

Visit every neighbour before any neighbour's neighbour, working outward in levels. Sweeping rather than diving — and the two have the guarantees and costs described elsewhere in the catalog.

The first problem.

CS 0152 The Minimum Spanning Tree

The lowest-cost way to connect all the vertices — one of the specially structured problems where a greedy approach is provably safe.

The second.

CS 0153 The Shortest Path

The lowest-cost route between two particular vertices, which also has an efficient solution. This is the formal shape of asking for directions.

Two entries stating the assumptions underneath every cost claim in the unit. Every measurement so far assumed something about the machine, and this names what was assumed.

The assumptions.

CS 0158 The Model of Computation

The set of rules taken for granted about the underlying machine — classically one thread performing one operation at a time. Every cost claim in this unit rests on it.

The abstract machine.

CS 0159 The Turing Machine

An abstract model in three parts — a memory bank, an instruction table, and a state. Simple enough to reason about formally, and sufficient for the theory that follows.

Four entries closing the theory, and one error entry correcting what is probably the most widespread misreading in the field — a misreading that comes from the letters themselves.

The first class.

CS 0161 The Class P

Every problem with an algorithm whose runtime is a polynomial expression. This is the tractable side — problems that can actually be solved at scale.

The second.

CS 0162 The Class NP

Every problem solvable in polynomial time by a nondeterministic algorithm — equivalently, one where a proposed answer can be checked quickly.

And the misreading.

CS 0163 "NP Means Not Polynomial"

It does not mean not-polynomial. Every problem in the first class is also in the second, because a deterministic solution needs no nondeterminism to help it. The letters mislead.

The hardest of them.

CS 0164 NP-Completeness

A problem qualifies when it sits in the second class and every problem in that class reduces to it. Solving one efficiently would solve all of them.

One capstone, and it is the best-constructed one in this course. A single route request from a phone, followed through every idea the unit numbered — model, structures, algorithms, costs, and the boundary of what is tractable.

The capstone. Two pins, one route.

CS 0169 From Pin to Pin

A real question becomes a model, the model selects structures, the structures feed algorithms, and the whole computation stays on the tractable side — with an intractable problem sitting one question away on the same map.

Five things you can now do, and Unit Three is complete. You can say why a brute answer always exists — inputs are finite — and that the real question is therefore cost rather than possibility. You can say what a model does to a problem, and that forgetting the violence it did is where confident wrong answers begin. You can say what an order of growth describes and what it does not — the shape of the cost curve, never elapsed time on a particular machine. You can say why greedy methods usually miss the best answer, since an early win can block a better total, and only special structures make greed safe. And you can say what NP means and why the letters mislead: every tractable problem is inside it, so it cannot mean not-polynomial.