---
title: "Algorithms & Data Structures"
description: "40 topics in Computing, in the order they build on each other."
canonical: https://lightmysky.com/learn/computing/areas/algorithms-and-data-structures
source: https://lightmysky.com/learn/computing/areas/algorithms-and-data-structures.md
retrieved: 2026-09-02
---

> **Agent view.** This is the Markdown twin of the page, for tools and assistants.
> When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md
> API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md
> Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt
> Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json
> Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`.

# Algorithms & Data Structures

40 topics in Computing, in the order they build on each other.

Page: https://lightmysky.com/learn/computing/areas/algorithms-and-data-structures

- [Counting Operations to Compare Algorithms](https://lightmysky.com/learn/computing/counting-operations-to-compare-algorithms-mt_JkN961niFG): Working out how many comparisons or swaps a method performs on an input of a given size, and writing that count as a formula in n. Two algorithms can then be compared without running either one.
- [Big-O Notation and Orders of Growth](https://lightmysky.com/learn/computing/big-o-notation-and-orders-of-growth-mt_mkqgxhJ509): Describing how the work an algorithm does grows with the size of its input, keeping only the term that dominates and dropping constants. It gives O(1), O(log n), O(n), O(n log n) and O(n squared) as a way to compare methods at any scale.
- [Quadratic Sorts: Bubble and Insertion](https://lightmysky.com/learn/computing/quadratic-sorts-bubble-and-insertion-mt_cBUIBa15jQ): Two sorting methods that work by comparing neighbouring values, one bubbling the largest to the end each pass and one placing each value into an already sorted front. Both do work proportional to n squared, which is where big-O first bites.
- [Stacks: Last In, First Out](https://lightmysky.com/learn/computing/stacks-last-in-first-out-mt_Evw7zeJE6Q): A collection where the only value within reach is the one added most recently. Push puts a value on top, pop takes it off, and that single restriction is what makes undo, back buttons and bracket checking straightforward.
- [Queues: First In, First Out](https://lightmysky.com/learn/computing/queues-first-in-first-out-mt_4U1bT0JW4g): A collection where values leave in the order they arrived: enqueue at the back, dequeue at the front. The circular queue keeps the front from drifting off the end of the storage.
- [Linked Lists and Nodes That Point](https://lightmysky.com/learn/computing/linked-lists-and-nodes-that-point-mt_HvY7_-M2Zj): Storing a sequence as nodes that each hold a value and a reference to the next node. Inserting in the middle costs two pointer changes, but reaching the five hundredth item means walking there one node at a time.
- [Hash Tables and Near-Constant Lookup](https://lightmysky.com/learn/computing/hash-tables-and-near-constant-lookup-mt_7v94MJEdmJ): Turning a key into a slot number with a hash function, so a value is reached by calculation instead of by searching. Two keys can land in the same slot, and the table needs a rule for what happens when they do.
- [Recursion and the Call Stack](https://lightmysky.com/learn/computing/recursion-and-the-call-stack-mt_VGjfeF3F2e): A function that calls itself on a smaller version of the same problem, with a base case that stops the descent. Every call that has not returned yet waits on the call stack, which is why deep recursion runs out of room.
- [Merge Sort and Divide and Conquer](https://lightmysky.com/learn/computing/merge-sort-and-divide-and-conquer-mt_OAutL4c7_l): Sorting by splitting the data in half, sorting each half the same way, then merging two sorted halves in one pass. The splitting gives log n levels and each level costs n, which is where O(n log n) comes from.
- [Trees and Binary Search Trees](https://lightmysky.com/learn/computing/trees-and-binary-search-trees-mt_7PGHiAY54b): A structure of nodes with one root and no cycles, and the binary search tree rule that keeps smaller values left and larger values right. Walking the tree left, node, right returns the values in sorted order.
- [Graphs and How to Store Them](https://lightmysky.com/learn/computing/graphs-and-how-to-store-them-mt_tSO-F1sTuu): Nodes joined by edges, with the edges possibly directed and possibly carrying a weight. The same graph can be held as an adjacency matrix or as an adjacency list, and the choice decides which questions are cheap to ask.
- [Breadth-First and Depth-First Search](https://lightmysky.com/learn/computing/breadth-first-and-depth-first-search-mt_q8IEzoBhzy): Two ways to visit every node reachable from a start point: one takes a queue and spreads out level by level, the other takes a stack and follows one path as far as it goes. The choice of structure is the whole difference between them.
- [Dijkstra's Shortest Path](https://lightmysky.com/learn/computing/dijkstras-shortest-path-mt_GvUzbY92qL): Finding the cheapest route through a weighted graph by always settling the nearest unsettled node next and relaxing the distances to its neighbours. Fewest hops and cheapest cost stop being the same answer once edges carry weights.
- [Loop Invariants and Proving an Algorithm Correct](https://lightmysky.com/learn/computing/loop-invariants-and-proving-an-algorithm-correct-mt_fWnstju2ns): A loop invariant is a statement that holds before a loop starts, survives every pass, and gives the wanted result once the loop stops. Stating one turns the claim that code seems to work into an argument that it works on every input.
- [Asymptotic Notation Made Precise](https://lightmysky.com/learn/computing/asymptotic-notation-made-precise-mt_B0Z6Syy8Ve): The definition behind big-O: f(n) is O(g(n)) when some constant multiple of g stays above f from some input size onward. Big-Omega bounds from below and big-Theta bounds from both sides, so a claim about growth becomes something a student can argue for rather than assert.
- [Recurrence Relations and the Master Theorem](https://lightmysky.com/learn/computing/recurrence-relations-and-the-master-theorem-mt_aOvLPV7rR8): A recursive algorithm's cost is written as an equation that refers to itself, such as T(n) = 2T(n/2) + n. Solving it by expansion, by a recursion tree, or by the master theorem gives the running time without tracing a single call.
- [Divide and Conquer as a Design Method](https://lightmysky.com/learn/computing/divide-and-conquer-as-a-design-method-mt_YITRNb-HTE): Split the input, solve the pieces the same way, and spend the remaining effort combining. Seen as a method rather than as one sorting trick, it produces fast multiplication, closest-pair search, and selection without sorting.
- [Randomised Quicksort and Expected Running Time](https://lightmysky.com/learn/computing/randomised-quicksort-and-expected-running-time-mt_fcKF7zfzpX): Quicksort partitions around a pivot, and its worst case is quadratic. Choosing the pivot at random makes the bad case a matter of luck rather than of input, and the expected running time is n log n whatever the adversary supplies.
- [The Comparison-Sorting Lower Bound](https://lightmysky.com/learn/computing/the-comparison-sorting-lower-bound-mt_7AfUsPV-jW): Any sort that only compares pairs of elements is a decision tree with n factorial leaves, so its height is at least n log n. This is a statement about every possible algorithm, not about the ones anybody has written.
- [Heaps and Priority Queues](https://lightmysky.com/learn/computing/heaps-and-priority-queues-mt_W-ofiMiXWs): A binary heap keeps the smallest item at the root using an array and a simple shape rule, so insert and extract both cost log n. It gives a sort that meets the comparison bound and, more usefully, a queue ordered by importance rather than by arrival.
- [Amortised Analysis](https://lightmysky.com/learn/computing/amortised-analysis-mt_1zLrl5RKGr): Some operations are occasionally expensive and usually cheap, so the worst case of one call overstates the cost of a run of calls. Amortised analysis charges the rare expensive step to the many cheap ones and reports the average per operation over any sequence.
- [Greedy Choice and the Exchange Argument](https://lightmysky.com/learn/computing/greedy-choice-and-the-exchange-argument-mt_9Fj28VDAV-): A greedy method takes the locally best option and never reconsiders. It is right only when a proof says so, and the usual proof takes any optimal solution and swaps its first choice for the greedy one without making it worse.
- [Union-Find and Minimum Spanning Trees](https://lightmysky.com/learn/computing/union-find-and-minimum-spanning-trees-mt_zOJei4yCtr): Kruskal's method sorts the edges and adds any that joins two separate pieces, which needs a structure that answers whether two vertices are already connected. Union-find answers it in almost constant time using a forest with path compression.
- [Dynamic Programming: Optimal Substructure and Overlapping Subproblems](https://lightmysky.com/learn/computing/dynamic-programming-optimal-substructure-and-overlapping-subproblems-mt__hWkCDnzNY): When a problem's best answer is built from best answers to smaller versions, and the same smaller versions keep reappearing, storing each answer once turns an exponential recursion into a polynomial one. The two conditions are what decide whether the method applies.
- [Dynamic Programming on Two Sequences](https://lightmysky.com/learn/computing/dynamic-programming-on-two-sequences-mt_uNUgHcKKQN): Longest common subsequence and edit distance both fill a grid where each cell asks one question about the last character of each string. The table gives the answer, and walking back through it gives the alignment that produced it.
- [Dynamic Programming with a Capacity: Knapsack](https://lightmysky.com/learn/computing/dynamic-programming-with-a-capacity-knapsack-mt_T5pbU_DpdC): The knapsack table is indexed by item and by remaining capacity, which makes its size depend on the numbers in the input rather than on how many there are. That is why the method is called pseudo-polynomial and why doubling the weights doubles the work.
- [Shortest Paths with Negative Weights and Between All Pairs](https://lightmysky.com/learn/computing/shortest-paths-with-negative-weights-and-between-all-pairs-mt_e8szFezaxO): Dijkstra's greedy choice fails once an edge can reduce a cost, so Bellman-Ford relaxes every edge n minus one times instead, and reports a negative cycle if anything still improves. Floyd-Warshall answers every pair at once by asking which intermediate vertices are allowed.
- [Network Flow and the Max-Flow Min-Cut Theorem](https://lightmysky.com/learn/computing/network-flow-and-the-max-flow-min-cut-theorem-mt_momRV9lK1n): Flow pushes as much as possible from a source to a sink without exceeding any edge's capacity. Augmenting paths in a residual graph find the maximum, and the theorem says that maximum equals the cheapest set of edges whose removal disconnects the two.
- [Finite State Machines and What They Recognise](https://lightmysky.com/learn/computing/finite-state-machines-and-what-they-recognise-mt_gIk7tQ229w): A machine with a fixed set of states that moves between them as it reads one input symbol at a time, drawn as a state transition diagram or written as a table. It has no memory beyond the state it is in, which fixes what it can and cannot recognise.
- [Turing Machines and the Universal Machine](https://lightmysky.com/learn/computing/turing-machines-and-the-universal-machine-mt_vS_QC1tCSM): A machine with a fixed set of states plus an unlimited tape it can read, write and move along. Adding the tape is enough to compute anything any computer can, and one such machine can read another's description and run it.
- [The Halting Problem: A Task No Program Can Do](https://lightmysky.com/learn/computing/the-halting-problem-a-task-no-program-can-do-mt_KeuKGHFWqr): There is no program that can take any program and its input and always say correctly whether it will finish. The proof feeds the checker its own description, and the contradiction is where computability stops.
- [Reductions: Solving One Problem by Turning It into Another](https://lightmysky.com/learn/computing/reductions-solving-one-problem-by-turning-it-into-another-mt_PAwby3ZyAr): A reduction converts every instance of one problem into an instance of another, so a solver for the second answers the first. Read forwards it reuses an algorithm, and read backwards it transfers hardness from a problem nobody can solve quickly.
- [P, NP and What NP-Complete Means](https://lightmysky.com/learn/computing/p-np-and-what-np-complete-means-mt_wwmNVG_VnB): P holds the problems solvable in polynomial time and NP the ones whose proposed answers can be checked that fast. NP-complete problems are the hardest in NP: every other NP problem reduces to them, so a fast method for one would be a fast method for all.
- [Living with NP-Hardness: Approximation and Heuristics](https://lightmysky.com/learn/computing/living-with-np-hardness-approximation-and-heuristics-mt_tZ82ty6h2u): Hardness rules out an exact fast method for every input, not a useful answer. An approximation algorithm carries a proved ratio to the optimum, while a heuristic carries no promise and has to be judged by measurement.
- [Randomised Algorithms and the Probabilistic Method](https://lightmysky.com/learn/computing/randomised-algorithms-and-the-probabilistic-method-mt_4ShN_WlT0-): An algorithm allowed to flip coins can be simpler and faster than any deterministic one known, at the price of a guarantee about expectation rather than about every run. The same idea proves objects exist by showing a random one works with positive probability.
- [Concentration Bounds and a High-Probability Guarantee](https://lightmysky.com/learn/computing/concentration-bounds-and-a-high-probability-guarantee-mt_WIltjK12oW): An expectation says nothing about how often the answer lands far from it. Markov, Chebyshev and the Chernoff bound each buy a sharper statement for a stronger assumption, and they are what turn an average-case claim into one that holds on nearly every run.
- [Approximation Ratios and How One Is Proved](https://lightmysky.com/learn/computing/approximation-ratios-and-how-one-is-proved-mt_8pmBztDkFD): An approximation algorithm comes with a proved bound on how far its answer can sit from the best one, and the proof almost never mentions the optimum directly. It bounds the optimum from one side with something computable, then bounds the algorithm against that.
- [Linear Programming, Duality and Rounding](https://lightmysky.com/learn/computing/linear-programming-duality-and-rounding-mt_rsj6G8iydV): Relaxing integer decisions to fractions gives a problem that can be solved, and its optimum bounds the integer one. Duality supplies the certificate that a solution is optimal, and rounding turns the fractional answer back into a real one at a cost that can be bounded.
- [Complexity Beyond NP: Space, Randomness and the Hierarchy](https://lightmysky.com/learn/computing/complexity-beyond-np-space-randomness-and-the-hierarchy-mt_ADfgl9UGpO): NP is one class among many. Alternating quantifiers give the polynomial hierarchy, bounded space gives classes with surprising collapses, and allowing randomness gives classes widely believed to add nothing. Most of the relations between them are conjectures with consequences.
- [SAT Solvers and What Makes Search Practical](https://lightmysky.com/learn/computing/sat-solvers-and-what-makes-search-practical-mt_d46m2LD443): Satisfiability is the canonical hard problem, and yet solvers decide industrial instances with millions of clauses. They search, and when they fail they learn a clause explaining the failure, which prunes the region that produced it. The worst case is unchanged; practice is not.