137 docs tagged with "computer-science"

Dijkstra's algorithm finds the shortest path to every vertex by always expanding the closest

Everything below this point in the knowledge base is about what the machine can do. This section is

Some structures cannot be made cheap on every single call, but can be made cheap *on average over any

Application protocols define the actual content and semantics of messages exchanged over a network

An array is a block of contiguous memory holding equally-sized elements. That one property gives it

Assembly language is a human-readable, (mostly) one-to-one text representation of machine code — the

Compare-and-swap, load-linked/store-conditional, and what an atomic instruction costs in cache-line ownership.

Backtracking searches a space of candidate solutions by building them one choice at a time, and

A binary search tree is $O(\log n)$ only while it stays short, and nothing in the plain

Big-O describes an upper bound on growth. Saying an algorithm is $O(n^2)$ claims that beyond some

Binary search compares the target against the middle element of a sorted array and discards half

Every binary search so far has searched an array: a sorted sequence of values sitting in memory,

Computers store everything as fixed-width sequences of bits (0/1). Binary is how the

A graph is bipartite when its vertices split into two groups such that every edge runs between

Bit-manipulation techniques are small, well-known patterns for testing, setting, and transforming

Bubble sort repeatedly walks the array comparing adjacent pairs and swapping them when they are out

A CPU, RAM, storage, and peripherals are separate physical chips — a bus is the shared electrical

How several caches holding the same line stay consistent, and why two unrelated variables in one line can destroy performance.

When one function calls another, both sides need to agree on where the arguments go, where the

Text is stored as bits too — a character encoding is the mapping between abstract characters

In almost every situation the correct answer is call your language's built-in sort. Those

"How many ways" questions tempt a direct answer: generate every arrangement, every selection, every

In practice you meet perhaps eight growth classes. Recognising which one a piece of code falls into —

Measuring an algorithm by timing it tells you about your laptop, your compiler, your input, and the

This page is a reference, not a tutorial — each numbered page in this section explains the reasoning

A computer network lets independent machines exchange data despite being built by different vendors,

A structured, top-down path through how computers actually work: from a single instruction executing

Threads within a process share memory, which makes communication cheap but introduces a real hazard:

Every comparison sort on this page's siblings is bound below by $Ω(n \log n)$ — a fact proved by a

The CPU (Central Processing Unit) is the component that actually executes a program: it repeatedly

A CPU cache is a small amount of fast SRAM that sits between the core and main memory, holding

A cycle is a path that leaves a vertex and, by following edges, returns to it. That definition reads

Every value a computer manipulates — an integer, a character, a color, an instruction — is ultimately

A data structure is a decision about which operations you want to be cheap. There is no structure

This page is a reference, not a tutorial — each page in this section explains the reasoning behind the

A database management system (DBMS) exists to store data reliably, query it efficiently, and let

A stack grows and shrinks at one end; a queue adds

Divide and conquer breaks a problem into independent subproblems of the same kind, solves those

DNS is the Internet's naming system — it translates human-readable names like example.com into the

Dynamic programming applies when a problem has overlapping subproblems — the same sub-computation

A CPU executing a stream of instructions needs a way to stop doing that and run something else.

Both of these are binary search wearing a different hat. Exponential search still finds a target in a

Every algorithm on the earlier pages of this folder assumes the whole array fits in memory, so any two

A singly-linked list, or anything shaped like one — a permutation's i -> p[i] mapping, a

A raw storage device — HDD or SSD — just exposes a flat array of addressable blocks; it has no

Floating point is a way to represent a huge range of real numbers — from 1e-300 to 1e300 — in

The greatest common divisor looks like a problem for factoring both numbers and comparing their

Once a problem is expressed as a graph, a small set of algorithms

This page is a reference, not a tutorial — see Graph Algorithms Overview for a first

A graph is a set of vertices and a set of edges connecting them. That is nearly no structure

A greedy algorithm makes the choice that looks best right now and never reconsiders it. When that

A hard disk drive stores data as magnetized regions on spinning platters, read and written by a

A hash table turns a key into an array index by running it through a hash function, then reads or

A priority queue answers one question: what is the most important item right now? A binary

Heapsort is selection sort with a better way of selecting. Selection sort scans

A computer is a stack of abstraction layers. Each layer hides the complexity of the one below

HTTP is the request/response protocol underlying the Web and most modern APIs: a client sends a

Peripherals are slow compared to a CPU: a disk read can take milliseconds, which is millions of CPU

Without an index, finding a row that matches a condition means reading every row in the table — a

Insertion sort builds the sorted result one element at a time, taking the next element and sliding it

An Instruction Set Architecture is the set of instructions a CPU can execute, plus the rules for

A fixed-width integer has a fixed number of bits, so it can only represent a finite range of

Processes are deliberately isolated from each other — that's the whole point of giving each one its

The hardware between a device asserting a line and a CPU taking an interrupt: PIC, APIC, MSI, and Arm's GIC.

A calendar full of meetings, a set of (start, end) ranges to merge, a question like "how many

The naive substring scan tries the pattern at every text position and, on a mismatch, throws away

Linear search examines each element in turn until it finds what it is looking for or runs out. It is

A linked list stores each element in its own node, together with a pointer to the next one. Nothing

A cache with unlimited capacity is just a hash table. The interesting problem

Every algorithm folder so far has assumed arithmetic just works: a hash function combines numbers,

No single memory technology is simultaneously fast, large, and cheap. Computers instead use a

The OS gives every process the illusion of a large, private, contiguous address space, even though

Why a multiprocessor does not execute your loads and stores in the order you wrote them, and what a fence actually buys.

Mergesort splits the array in half, sorts each half recursively, and merges the two sorted halves

Given a connected, undirected, weighted graph, a spanning tree picks exactly V - 1 edges that keep

"For each element, find the nearest element to the right that is bigger" looks like it needs a nested

Making a single CPU core faster (higher clock speed, deeper pipelines, wider superscalar execution)

The obvious way to find a pattern of length m inside a text of length n is to try it at every

A flow network is a directed graph where every edge has a capacity, one vertex is a source pumping

Once a database is replicated across multiple machines to survive failures and scale reads, it

When "main memory" stops being one thing: node distance, local versus remote latency, and what interleaving trades away.

The physical storage medium (platters, NAND cells) is only half the story — data still has to travel

An operating system's job is to let multiple programs safely share one machine's hardware — CPU,

Every kernel design question people argue about — "is Linux old-fashioned," "why does Windows put

Most complexity analysis on this site asks how fast a known algorithm runs. This page asks a

Pipelining overlaps the fetch-decode-execute stages of multiple instructions so that, once the

Summing a range of an array costs time proportional to the range. Do it once and nobody notices; do it

Testing whether a single number n is prime is a small, self-contained problem: try dividing it by

An operating system has to run code it does not trust — a downloaded binary, a browser tab, a

Every structure so far in this section answers its question exactly, at the cost of storing enough

The named algorithms in the earlier sections are instances of a smaller number of recurring

This page is a reference, not a tutorial — see Problem-Solving Patterns Overview for a

A process is the OS's unit of isolation: a running program with its own private address space,

Finding the k-th smallest element does not require sorting the whole array. Sorting throws away no

Quicksort picks an element as the pivot, rearranges the array so that everything smaller sits to

"RAM" isn't one technology — it's a family. The RAM that makes up multi-gigabyte main memory

A deterministic algorithm has exactly one worst case, and if that worst case is realistic — an

Disassembly is the practical skill this whole section builds toward: given compiled machine code —

A recursive algorithm's cost is itself defined recursively — mergesort's cost on n elements is twice its

Dynamic Programming names the idea — overlapping subproblems plus

The relational model, introduced by Edgar F. Codd in 1970, represents all data as relations

There are almost always more runnable threads than CPU cores. The scheduler is the kernel

Every algorithm in this folder answers the same question — "is this value present, and where" — but

Prefix sums answer range-sum

Selection sort divides the array into a sorted prefix and an unsorted remainder. Each round it scans

Below the level of PCIe and USB, most chip-to-chip communication on a circuit board — a sensor

"Shortest" means fewest edges on an unweighted graph and lowest total weight on a weighted one, and

Sorting is the most-studied problem in the field, and not because arranging things in order is

This page is a reference, not a tutorial — each algorithm's own page derives the bound it gets here.

Time complexity answers "how does the work grow?"; space complexity asks the same question about

A solid-state drive has no moving parts — it stores bits as trapped electrical charge in NAND

Stacks and queues are not new storage — they are restrictions on storage. Both hold a sequence,

Storage is the persistent tier of the memory hierarchy: unlike RAM, it retains data with the

Every algorithm in this folder assumes a cost model for three operations that look free and are

A string is an array — but three things about it break the assumptions the rest of this section

In a directed graph, two vertices are strongly connected if each can reach the other — a path

Every algorithm earlier in this folder answers one question: does this one pattern occur in this

A simple pipeline gets throughput to about one instruction per cycle. Modern high-performance CPUs

Every wire diagram of a computer hides the same question: how do the CPU, RAM, and peripherals

The data link layer is responsible for moving frames between devices on the same local network

Every instruction a CPU runs goes through the same basic loop: fetch it from memory, decode what it

The network layer's job is addressing and forwarding across different networks — the piece that

Two competing layer models are used to describe networking: the OSI model (7 layers, designed by

The cache that makes virtual memory affordable: TLB structure, page-walk caches, address-space tags, and shootdown cost.

The transport layer is where "get some bytes from A to B" becomes either a reliable, ordered

TLS (Transport Layer Security) is what turns HTTP into HTTPS — and secures plenty of other

"Find the k largest" looks like a sorting problem, and sorting solves it — but sorting also computes

A topological sort orders the vertices of a directed acyclic graph so every edge points forward —

A transaction groups multiple reads/writes into a single logical unit of work. ACID —

Breadth-first and depth-first search both visit every vertex reachable from a start point, in

A tree is a set of nodes where each node has one parent (except the root) and no cycles. That single

A hash set answers "is this exact string in the set?" and nothing else. It cannot answer "what strings

Both patterns replace a nested loop with a single pass by maintaining two indices that only ever move

Some problems never ask what is in a group. They ask only whether two things have ended up in the

USB (Universal Serial Bus) is the dominant peripheral connection standard for everything from mice

Every process behaves as if it owns the entire address space and as if its memory is one large,

Every x86-64 instruction operates on a small set of named storage locations — registers — and/or