Computer Science

Computer science studies computation, algorithms, and the representation and processing of information. Begin with programming and data representation, then study data structures, algorithms, and their costs. Move into hardware, operating systems, databases, and networks before security and specialized applications.

Programming and Data Representation

Build from programs and data representation to language paradigms.

Programming Paradigms and Languages

A program represents data and specifies operations on it. Begin with the roles of variables, control flow, and functions, then compare the ways programming paradigms organize those operations. Language names are examples of these design choices; data structures and algorithms come next.

• Programming Paradigms and Functions

  • Imperative — step-by-step instructions changing program state; C, Pascal.

  • Object-oriented (OOP) — organizes code around objects with encapsulation, inheritance, polymorphism; key languages: Java, C++, Python, C#.

  • Functional — treats computation as evaluation of mathematical functions; avoids mutable state; first-class and higher-order functions; Haskell (purely functional), Lisp, Erlang, Clojure; functional features in Python, Scala, Kotlin. Languages such as Haskell are associated with this paradigm, and monads are a common feature used to manage effects within it.

  • Declarative — describes what to compute, not how; SQL is the canonical example; Prolog (logic programming).

  • Logic programming — programs are logical clauses; computation is inference; Prolog is the canonical language; uses unification and backtracking search; applied in AI, natural language processing, constraint solving.

  • First-class functions and higher-order functions — in functional languages, functions are values that can be passed to/returned from other functions; map, filter, reduce (fold) are canonical higher-order functions.

  • Lambda calculus in PL — anonymous functions (lambdas/closures) in modern languages derive from Church’s lambda calculus; closures capture their lexical environment; key to functional programming in Python, JavaScript, Haskell, Scala.

  • Closure — a function that captures variables from its enclosing lexical scope; allows functions to be returned as values while retaining access to outer-scope bindings; central to functional programming and JavaScript.

  • Currying — transforming a function of multiple arguments into a chain of single-argument functions; f(x, y) becomes f(x)(y); named after Haskell Curry; fundamental in Haskell and functional languages. It is especially associated with lambda calculus and languages like Haskell.

  • Monad — design pattern in functional programming (especially Haskell) for chaining computations with context (e.g., handling failure, I/O, state) while maintaining purity; a monad must satisfy left-identity, right-identity, and associativity laws.

  • Programming paradigms

    • Declarative programming — Declarative programming is a paradigm in which a program describes what should be computed rather than how to compute it. Examples include logic programming such as Prolog and description-oriented languages like HTML.

    • functional languages — Functional languages are programming languages built around expressions, recursion, and lambda calculus rather than mutable variables and side effects. They include Lisp, Scheme, Haskell, and OCaml, and they often emphasize referential transparency and lazy or strict evaluation.

    • functional programming — Functional programming is the paradigm that treats programs as mathematical expressions and emphasizes referential transparency, recursion, and the avoidance of side effects. It is associated with the lambda calculus and with languages such as Haskell, Scheme, Lisp, and ML.

      • closures — In programming, a closure is a function bundled with the lexical environment in which it was created or called. Closures preserve free variables and are central to languages with first-class functions, including the Lisp family.

      • referential transparency — Referential transparency is the programming property that lets an expression be replaced by its value without changing program behavior. It is associated with pure functional languages such as Haskell and Scheme, where side effects are absent or carefully controlled.

      • side effects — In functional programming, side effects are changes to external state or observable output beyond returning a value. Pure functions avoid them, which is why languages like Haskell isolate such actions in the IO monad.

    • functional programming languages — Functional programming languages emphasize pure functions, recursion, and the avoidance of side effects. They are often linked to lambda calculus and to the Curry-Howard correspondence, and Haskell is a standard example.
      • Haskell — Haskell is a strongly typed, purely functional programming language known for lazy evaluation, monads, and type classes. It was influenced by Miranda and is closely associated with the Glasgow compiler ecosystem.
    • purely functional programming — Purely functional programming is a paradigm in which programs are built from functions and avoid side effects. Haskell is the best-known language associated with this style, and monads are a common tool in it.
  • higher-order functions
    • map — A map is a chart or diagram that represents space, such as the world or a country. In computing, map is also a higher-order function that applies a function to each item in a list or array.
  • Fixed-point combinators
    • Y Combinator — Y Combinator is a startup accelerator that funds early-stage companies and runs Hacker News. It also names the fixed-point combinator in functional programming, often taught in Haskell or lambda calculus.
  • logic and computation
    • Haskell Brooks Curry — Haskell Brooks Curry was a logician whose name is attached to currying, the transformation of a multi-argument function into nested single-argument functions. With W. A. Howard, he also names the Curry-Howard correspondence between proofs and programs.
• Types, Names, and Memory

  • Static vs dynamic typing — static: types checked at compile time (Java, C, Rust); dynamic: types checked at runtime (Python, JavaScript, Ruby).

  • Strong vs weak typing — strong typing prevents implicit type coercion (Python, Java); weak typing allows it (C, JavaScript).

  • Type systems — static typing: types checked at compile time, catches errors early (Java, C, Rust, Haskell); dynamic typing: types checked at runtime (Python, JavaScript, Ruby); gradual typing: optional type annotations (TypeScript, mypy for Python).
    • type — Type is the property that classifies values in programming languages, whether inferred statically or assigned dynamically at runtime. Python’s flexible version is often described as duck typing, while systems such as Hindley-Milner infer types automatically.

  • Type inference — compiler/interpreter deduces types without explicit annotations; Hindley-Milner algorithm (ML, Haskell); distinct from dynamic typing, which checks types at runtime.

  • Pointer / reference — a variable holding a memory address; direct memory manipulation in C/C++; a source of bugs (null pointer, dangling pointer, buffer overflow).

  • Pass by value vs pass by reference — pass by value copies the argument; pass by reference passes the memory address, allowing mutation.

  • Garbage collection — automatic memory management; used in Java, Python, Go; GC algorithms: mark-and-sweep, reference counting, generational GC; contrasts with manual memory management (C/C++) and ownership systems (Rust). Common implementation approaches include mark-and-sweep, reference counting, generational collection, Cheney’s copying algorithm, and JVM stop-the-world implementations.

    • generational garbage collection — Generational garbage collection groups objects by age so that recently allocated objects can be collected differently from older ones. It uses the observation that most objects die young, and common schemes include stop-and-copy and mark-and-sweep within different generations.

    • mark-and-sweep — Mark-and-sweep is a classic garbage-collection strategy that first marks reachable objects and then frees the unmarked ones. It is associated with Dijkstra’s tri-color refinement and is used to reclaim memory unreachable from the program.

    • stop-the-world — Stop-the-world garbage collection halts all application threads while memory is swept and objects are reclaimed. It is the opposite of incremental or concurrent collection methods that try to reduce pause time.

  • Garbage collection algorithms — mark-and-sweep: trace reachable objects, collect the rest; reference counting: count references, free at zero (problem: cycles; Python uses cycle detector); generational GC: most objects die young, promote long-lived objects to older generations (JVM, CPython).

  • Call stack and stack frame — each function call pushes a frame containing local variables, parameters, and return address; stack grows downward on x86; stack overflow occurs when recursion is too deep; heap is used for dynamically allocated objects.

  • Memory management: stack vs heap — stack holds local variables and call frames (fast, automatic, fixed size per frame); heap holds dynamically allocated objects (flexible size, managed by GC or manual free); stack overflow from deep recursion; heap fragmentation from dynamic allocation.

  • Ownership and borrowing (Rust) — Rust’s memory safety model: each value has exactly one owner; references (borrows) must not outlive the owner; prevents dangling pointers and data races without garbage collection; enforced at compile time by the borrow checker.

  • variables

    • global variable — A global variable is one that is defined so it can be accessed throughout a program rather than only inside a single function. Because it remains available while the program runs, it is not something that can simply be removed by garbage collection in the usual sense.

    • global variables — Global variables are variables whose scope extends throughout an entire program rather than being confined to local scope. They are often criticized in programming because they can make code harder to manage and reason about.

  • information hiding
    • opaque — Opaque means unable to transmit light so that objects behind it cannot be seen clearly. The word also appears in computer science for interfaces that hide implementation details.
  • generics
    • template — A template is a generic definition that can be reused across types, especially in programming languages that support parameterized functions or classes. It lets a single abstract framework handle different data types without rewriting the whole function or class for each case.
  • programming language type systems
    • typing — Typing is the programming-language process of assigning, checking, or inferring data types. Quizbowl clues often mention Hindley–Milner inference, duck typing, static typing, and type safety.
  • programming language types
    • data types — In computer science, data types classify values and constrain what operations are valid on them. They include examples such as int, float, char, bool, integers, booleans, and strings, and underlie distinctions between primitive and composite types, static and dynamic typing, polymorphism, type inference, duck typing, casting, and algebraic type systems in languages such as C, Java, Python, and Haskell.

      • Boolean data — Boolean data is information with only two possible values, true and false. It is named for George Boole and underlies logical operations such as conjunction and disjunction as well as many programming control structures.

      • char — In programming, char is the data type used to store a single character, often implemented as a one-byte integer type. In some contexts it refers to a 16-bit Unicode character, but the basic idea is a single character value.

      • composite types
        • struct — In programming, a struct is a conglomerate data type made up of elements that may each have different types. Related move names ending in “-struct” are also referenced by the evidence, but the programming definition is the clearest match.

      • float — A float is a 32-bit floating-point data type used to represent numbers with fractional parts in programming. In finance, float can also mean capital held to meet immediate liabilities, such as insurance reserves.

      • int — In programming, int is the primitive integer type used for whole numbers in languages such as C++ and Java. It stores values without decimals and is commonly used in arrays and basic arithmetic.

      • integers

        • signed binary integer — Signed binary integers are the basic whole-number data type in many programming languages. They are commonly stored in two’s complement form and contrasted with floating-point numbers.

        • signed integer — Signed integers are whole-number data types that use two’s-complement representation in many programming languages. They support addition and subtraction by modulo arithmetic and include common sizes such as short and long.

      • string — A string is a data type that stores an ordered sequence of symbols, usually text. The word also names the one-dimensional objects in string theory, along with the physical cords used in cat’s cradle and similar string games.

      • structs — In C, structs are compound data types that bundle named members under one type. They are often used to imitate objects and classes in object-oriented programming.
• Control Flow, Execution, and Language Implementation

  • Interpreted vs compiled — compiled languages (C, C++) translate to machine code ahead of time; interpreted languages (Python, Ruby) run via a runtime interpreter; JVM languages (Java, Kotlin) compile to bytecode, then JIT-compile.

  • Compiler pipeline — lexical analysis (tokenizing) → parsing (AST construction) → semantic analysis (type checking) → optimization → code generation; LLVM is a widely-used compiler infrastructure.

  • Interpreter vs compiler — interpreters execute source directly (Python CPython, early BASIC); compilers translate to machine code or bytecode ahead of time; JIT (just-in-time) compilation compiles at runtime (JVM HotSpot, V8 JavaScript engine, PyPy).

  • Recursion vs iteration — recursion is cleaner for tree/graph traversal but uses O(depth) stack space; iterative solutions use explicit stacks; tail-call optimization (TCO) converts tail recursion to iteration; Scheme mandates TCO, Python explicitly does not.

  • Abstract syntax tree (AST) — tree representation of the syntactic structure of source code produced during parsing; nodes represent constructs (expressions, statements); used in compilers, linters, and code analysis tools.

  • Event loop — JavaScript’s concurrency model; single-threaded; I/O callbacks queued in the event loop while the call stack is empty; Node.js uses libuv for async I/O; microtask queue (Promises) drains before macrotasks (setTimeout).

  • Concurrency vs parallelism — concurrency: multiple tasks make progress by interleaving (single core); parallelism: tasks execute simultaneously on multiple cores; Go’s goroutines are concurrent; SIMD/GPU kernels are parallel.

  • Amdahl’s law — speedup from parallelizing a program is limited by the serial fraction s: Speedup ≤ 1/(s + (1-s)/p) where p is processor count; diminishing returns; Gene Amdahl (1967). It describes the limit on speedup gained by improving only part of a computation, and is a standard result in parallel computing showing diminishing returns from optimizing just the parallelizable portion of a system.

  • control flow

    • goto — A goto is the programming command that transfers control to a labeled point in code. It was famously criticized by Edsger Dijkstra as harmful because overuse encourages spaghetti code.

    • switch-case — In C++, switch is the branching construct corresponding to Pascal’s case statement. It is used for choosing among multiple labeled branches in a program.

    • Loops — Loops are control structures that repeat a block of code while a condition holds, with common forms including for, while, and do-while loops. They can be optimized by unrolling, interrupted with break, and advanced with continue, and they are central to basic iteration in many programming languages.

      • infinite loop — An infinite loop is a programming loop whose terminating condition is never met, so the instructions repeat endlessly. It may be intentional in server software, but more often it is a bug that can freeze older systems or monopolize resources.

      • loop — A loop is a programming construct that repeats statements, commonly appearing as for, while, or do-while forms. The word also names a circuit loop in physics, where Kirchhoff’s loop rule says the total voltage change around the loop is zero.

      • while loop — A while loop is a control structure that repeats a block of code as long as its condition remains true. It is a basic programming construct associated with indefinite iteration and, when misused, can create infinite loops.

  • control flow instructions
    • Jump — A jump is a control-flow transfer instruction in computing that sends execution to a different point in a program. The word also names the up-tempo blues style jump blues and Count Basie’s “One O’Clock Jump.”
  • control flow statements
    • conditional statements — Conditional statements choose between code paths based on whether a Boolean test is true, as in if-then-else structures and switch statements. In logic and philosophy they also appear as conditionals, with material, strict, and indicative forms used in arguments about implication and validity.
  • programming control structures
    • for loop — A for loop is a count-controlled programming construct that repeats code for a known number of iterations. It is also commonly used to iterate over items in a collection, unlike a while loop that tests a condition before each pass.
  • Programming examples
    • Hello, World! — “Hello, world” is the standard first output used to test a new programming language or development environment. It is the classic introductory string printed in examples from Python to other languages.
  • programming language keywords

    • static — This adjective describes nonmoving fluids, friction at rest, and the buildup of charge that can spark as static electricity. In C++, it also marks class methods or variables tied to a class rather than an instance.

    • Exception handling

      • catch — Catch can mean the amount of fish captured, a ball or projectile successfully received, or a trap in a legal deal. In programming, catch is the reserved word that handles exceptions after a try block.
  • programming language operators
    • modulus operator
      • percent sign — The percent sign is the symbol used in Java for the modulus operator. It also appears in C printf format strings, where it introduces format specifiers for printed output.
  • programming language syntax

    • Caret — A caret is the symbol ^, used in computing, vector commands, and regular expressions. It can denote exclusive OR, specify relative coordinates, negate a character class, or anchor the start of a string.

    • Comment — A comment is text embedded in code for human readers rather than the compiler. Languages mark comments in different ways, such as REM in BASIC, # in Python and Perl, and /* … */ in C.

    • comments — Comments are bits of source-code text meant for humans rather than the compiler or interpreter. They are often marked with symbols such as # in Python or // in Java, and are a common target of jokes about self-documenting code.

    • scope resolution
      • double colon — A double colon is the duplicated punctuation mark written ::. It functions as the scope resolution operator in languages such as C++ and Ruby and can also indicate type ascription or a method reference.
    • semicolon — The semicolon is the punctuation mark that separates closely related clauses and is required at the end of many statements in C-like programming languages. It also appears in contexts such as CSV files, emoticons, and several programming syntaxes.
  • programming symbols
    • asterisk — The asterisk is the symbol commonly used for multiplication, pointers, wildcards, and block comments in programming. In regular expressions it can also become the Kleene star, marking repetition or, in some contexts, a special operator.
  • programming language semantics
    • evaluation — Evaluation is the process of applying a function or expression to its arguments and simplifying the result, as in call-by-value or call-by-reference. In programming languages, variants include eager, lazy, partial, and out-of-order evaluation.
  • assemblers
    • assembler — An assembler is a program that translates assembly language into machine code understood by hardware. It is a basic tool in compilation and low-level programming, converting symbolic instructions into native machine language.
  • compiler optimization
    • loop unrolling — Loop unrolling is a compiler optimization that reduces branch and loop-control overhead by replicating the body of a loop. It can improve performance by replacing repeated control flow with longer straight-line instruction sequences.
  • Compiler theory
    • lexical analysis — Lexical analysis is the first stage of a compiler, in which a stream of characters is broken into tokens. It is also called lexing or scanning and is often paired with parsing in language processing.
      • lexer — A lexer is a compiler component that tokenizes source text into a stream of tokens before parsing begins. It is often implemented with a finite automaton, with special handling for irregular cases such as comments.
  • compilers — Compilers are programs that translate source code into lower-level machine code or object code, usually through stages such as lexical analysis, parsing, semantic analysis, optimization, and code generation. They are contrasted with interpreters and are a core topic in programming-language implementation. Notable examples include gcc and clang; Grace Hopper’s early work and the self-hosting Lisp compiler are also associated with the topic.
    • compilation — Compilation is the process of translating source code into machine-executable form, usually by way of an intermediate representation and later stages such as instruction selection and register allocation. It is often optimized with techniques like constant folding, loop unrolling, and inlining, and programs such as gcc, clang, and javac perform it.

      • just-in-time compilation — Just-in-time compilation is code generation that happens after a program has started running, so the compiler can use runtime information. It is used by Java and the JVM to turn bytecode into machine code.

      • linking — Linking is the process of combining object files and libraries to produce a final executable. In grammar, the word can also refer to the copula or linking verb, though the computing sense is the main clue here.

    • compiler — A compiler is a program that translates source code into lower-level output such as assembly, bytecode, or machine code. It typically performs lexical analysis, parsing, optimization, and code generation, and may also support bootstrapping or just-in-time compilation. Compilers are contrasted with interpreted languages. The Dragon Book is the classic reference on compiler construction.

    • compiling — Compiling is the process of translating source code into machine code, typically after preprocessing and before assembling and linking. It includes tasks such as register allocation, instruction selection, and inlining, and the JVM can perform it just in time for native execution.

    • linker — A linker is the program that combines one or more object files and libraries into a single executable. It is invoked after compilation or assembly to produce the final runnable program.

    • parsing — Parsing is the computer-science process of turning a string of symbols or source code into a structured representation according to a formal grammar. Common clue terms include shift-reduce, Earley’s algorithm, the CYK algorithm, and parsers built by tools like Yacc and Bison.
      • parsers — Parsers are programs that analyze tokenized input and determine its grammatical structure. They are used in compilation, often generated by tools like Yacc or Bison, and may use top-down or bottom-up strategies such as LL, Earley, or CKY.
        • Parser — A parser is the program or component that performs syntactic analysis on tokens according to a grammar. It usually receives lexer output and builds a tree or structured representation of the input.
    • preprocessors
      • preprocessor — A preprocessor is a program that runs before compilation to expand macros, handle directives, and transform source text. Common tasks include concatenating source lines, replacing comments with whitespace, and processing directives such as define and include.
    • static single assignment form — Static single assignment form is an intermediate representation in which each variable is assigned exactly once. Compilers use it to simplify optimization, including versions of code transformation built from control-flow graphs and dominance frontiers.
  • Executable file format
    • executables — Executables are files containing machine instructions that can be run by a computer. Examples include formats such as ELF and Mach-O, which are produced by compilers and may use shared libraries through dynamic linking.
  • program entry points
    • main function — In C and C++, main is the program entry point and typically returns an integer status code; a return value of zero usually indicates successful termination. In Java, main is the first method run when a program begins execution and is typically declared public static void, serving the same entry-point role.
  • Programming language implementation
    • Interpreters — Interpreters are programs that execute source code directly rather than compiling it first. They are often contrasted with compilers and are associated with systems like the Java virtual machine and early BASIC interpreters.
  • exception handling
    • Exceptions — Runtime error conditions in programming that interrupt normal control flow. They are typically thrown and caught by try-catch or try-finally logic, and may be handled, ignored, or propagated; many languages describe them as being thrown. A null pointer exception is a classic example, and they are often distinguished from more severe errors.
      • Run-time error — A run-time error is an error that occurs while a program is executing rather than when it is compiled. Division by zero is a classic example.
    • try — In programming languages such as Java and C++, try marks the protected block of code that is followed by catch for exception handling. In rugby, a try is the act of grounding the ball in the opponent’s in-goal area.
  • Program execution
    • call stack — The call stack is the last-in, first-out memory structure used for active function calls and local variables. It is a common target of buffer overflows and return-oriented attacks, and defenses include canaries, shadow stacks, and return-to-libc countermeasures.
      • stack overflow — A stack overflow happens when too many nested function calls or too much recursion exhausts the call stack. In computing, it is closely associated with stack frames, segmentation faults, and the programming Q&A site Stack Overflow.
  • Event-driven programming
    • events — In Alain Badiou’s philosophy, events are eruptions that break with a situation and generate new truths. The term also appears in semantics and computer science, where events are handled by listeners or handlers in event-driven programming.
  • parallel computing — Parallel computing is a way of dividing a task into smaller parts that run simultaneously, often across multiple processors or clusters. Quizbowl clues often point to MapReduce, Hadoop, OpenMP, PRAM, GPUs, and Amdahl’s law when asking about it.

    • MapReduce — MapReduce is a parallel computing paradigm that splits data into key-value pairs, processes them across worker nodes, and then aggregates the results. It is associated with Apache Hadoop and inspired later systems such as Spark.

    • n-cube networks
      • n-cube — An n-cube, also called a hypercube, is a parallel-computing network topology with 2^n processor nodes. In this topology each node is connected to n others, one along each dimension.

    • parallel processing — Parallel processing is a computing method in which multiple processors or cores work on tasks at the same time. It is used to split a program’s workload across available hardware, as in supercomputer applications like Deep Blue.

    • PRAM — PRAM, or the parallel random-access machine model, is an abstraction for parallel algorithms with many processors sharing memory. Its variants include CRCW and EREW, and Brent’s theorem is used to analyze computations on it.

    • vector processing — Vector processing is the style of computation that operates on whole arrays of data at once rather than on individual scalars. It is associated with supercomputers such as the Cray C90.

Key Languages (Brief)

• C — low-level, compiled, manual memory; basis for UNIX and most operating system kernels; Dennis Ritchie (Bell Labs, early 1970s). Designed at Bell Labs by Dennis Ritchie around 1972 to rewrite Unix; noted for portability and systems-level low-level access. It was documented in K&R and became the predecessor of C++, with later descendants including Objective-C and C#.

• Java — “write once, run anywhere” via JVM bytecode; strong static typing, garbage collected; James Gosling (Sun, 1995). It later became dominant in enterprise and Android app development, and was originally developed under the name Oak; it was once prominently bundled with Netscape Navigator for multimedia web development.

  • Object — In Java, Object is the root superclass from which all classes ultimately inherit methods such as toString and hashCode.

  • synchronized — In Java, synchronized is the keyword used to mark a method or code block that must obtain a lock before it runs. It is central to coordinating access among threads and preventing race conditions.

• Python — dynamic, interpreted, emphasis on readability; Guido van Rossum (1991); dominant in data science, scripting, and ML. It was designed by Guido van Rossum in 1991 and later became dominant in data science, machine learning, and scripting; van Rossum was known as the language’s “Benevolent Dictator For Life” (BDFL) until 2018. It is a high-level programming language with readable syntax, indentation-based blocks, and dynamic typing, and it supports data structures such as lists, tuples, and dictionaries, along with features like list comprehensions and the range function.

• JavaScript — prototype-based, event-driven; the language of web browsers; Brendan Eich (Netscape, 10 days, 1995); Node.js brings it server-side. It was originally called Mocha, then LiveScript, and is the scripting language of the web used with HTML and CSS for interactive pages, dynamic content, DOM manipulation, and modern single-page applications; major engines include V8 (Google) and SpiderMonkey (Mozilla), and it uses the .js file extension.

• Rust — memory-safe without garbage collection via ownership/borrow checker; Mozilla Research (Graydon Hoare), 1.0 in 2015. It uses traits for generic abstractions.

• Lisp — one of the oldest high-level languages (John McCarthy, 1958); homoiconicity (code is data); dialects include Common Lisp, Scheme, Clojure. It was designed by John McCarthy at MIT in the late 1950s, is based on lambda calculus, and became foundational in artificial intelligence research. It is often described as the second oldest high-level language still in widespread use, and it introduced or popularized garbage collection, higher-order functions, and dynamic typing; it is also known for S-expressions and list processing.

  • S-expressions — S-expressions are the list-and-atom notation associated with Lisp and related languages. They support homoiconicity because programs and data share the same basic structure, making them useful for evaluation and self-modifying code.

  • Scheme — Scheme is the minimalist Lisp dialect developed at MIT by Guy Steele and Gerald Sussman. It is known for the Lambda Papers, hygienic macros, and a naming style in which predicates end in question marks and mutating procedures end in exclamation points.

• C++ — extends C with OOP and templates; Bjarne Stroustrup (1979).

• C programming
  • bit fields
    • bitfield — A bitfield is a C-language structure feature used to pack integers into smaller memory locations than the compiler would normally allocate. Bitfields are declared with a colon syntax and are heavily implementation dependent.
• C++ libraries
  • Boost — Boost is a widely used C++ library of peer-reviewed components, including implementations of algorithms such as Boyer-Moore. Its type-traits and enable-if style utilities were influential enough to feed into the C++11 TR1 effort.
• Android
  • Dalvik — Dalvik was Google’s Android runtime environment and virtual machine for running apps. It became notable in a dispute over whether Google had copied Java intellectual property.
• Java applets
  • applets — Applets are miniature applications, especially Java programs that run within a web page. They became a familiar feature of early browser-based software and were often associated with simple embedded tools or demos.
    • applet — An applet is a small program, especially one that runs inside a web browser. In Java, applets were designed to load with web pages and execute in the browser’s environment.
• Java main method
  • public static void — In Java, public static void is the standard trio of modifiers that precede the main method. They mark the method as accessible outside the class, belonging to the class rather than an instance, and returning no value.
• JavaScript runtimes
  • node — Node is the server-side JavaScript runtime built on Google’s V8 engine and usually paired with npm for package management. It is named for a generic network node and is widely associated with left-pad and other npm ecosystem controversies.
• C++
  • Bjarne Stroustrup — Bjarne Stroustrup developed C++ while working at Bell Labs in the early 1980s. C++ extends C with object-oriented programming features.

Related Concepts and Applications

• Programming
  • assertions
    • assert — In programming, assert is a keyword used to check that a condition is true during debugging or testing. Test frameworks such as JUnit use forms like assertEquals and assertTrue to verify expected behavior.
  • character data
    • characters — In programming, characters are the basic textual units represented by functions like Python’s ord and stored in strings.
      • Schala — Schala is a character from the Chrono series, best known as the princess of Zeal and the sister of Magus. Her story connects to Lavos, the Mammon Machine, and later transformations involving Kid and the Time Devourer.
  • conditional statement
    • conditional — A conditional statement in programming executes a block only when its test is true, as in if-then-else or switch constructs. The same adjective also describes probability or expectation given that another event has occurred.
  • control flow
    • break — Break is a common English word that can mean a pause, a split, a circuit interruption, or the first shot in pool. It also names the programming command used to exit a loop early.
  • data structures
    • structure — In programming, a structure is a composite data type that groups multiple fields under one name. The same word also names the clustering program STRUCTURE, used to assign individuals to genetic populations.
  • input/output
    • write — To write is to store or enter data, whether in memory, to a file, or through output operations in programming. The same verb also appears in literary clues, as in poems by Elizabeth Bishop and Pablo Neruda.

  • iterators — Iterators are abstract traversal objects used to move through elements in a collection or container. In languages like Java, they typically provide methods such as next and hasNext, and they generalize pointer-like access to linear data structures.

  • macros
    • macro — A macro is a stored sequence of commands that expands into a longer set of instructions, often used to automate repetitive tasks in software such as word processors and spreadsheets. In programming, macros are substituted at compile time, and macro viruses exploit the same automation features in office applications.
  • Process diagrams
    • flowchart — A flowchart is a diagram that represents the steps in a process or solution to a problem. It uses standardized shapes such as rectangles, diamonds, and circles to show actions and decisions.
  • runtime — In programming, runtime is the third major class of error, distinct from syntax and logic errors, that arises when a program is given bad data. It also names the time required for an algorithm to execute, which analysis often bounds using Big O notation.
• programming languages — Programming languages are formal systems for writing instructions to computers, including C, Java, Python, and assembly. Clues often involve typing, syntax, compilers, functional and object-oriented paradigms, and the Curry-Howard correspondence.

  • Ada — A programming language named for Ada Lovelace, designed for large-scale, reliable software. It was developed for the U.S. Department of Defense and emphasizes strong typing, runtime checking, generic units, exception handling, modules, tasks, parallel and concurrent programming. Ada 95 later added object-oriented features.

  • assembly language — Assembly language is a low-level programming language that maps closely to machine code, usually with one instruction per statement. It uses mnemonic opcodes such as MOV and JMP, and programmers often need to handle register allocation and other bare-metal details.

    • assembly — Assembly is a low-level programming language written in mnemonic instructions close to machine code. In bioinformatics, assembly is also the process of joining short sequencing reads into longer sequences, often using de Bruijn graphs or other overlap methods.

    • instructions
      • NOP — A NOP, or no operation, is an assembly-language instruction that does nothing except consume clock cycles. It is often inserted for alignment, timing, hazard avoidance, or branch-delay-slot handling.
    • x86 assembly language — This is the Intel assembly language used for IA-32 systems and often written with AT&T syntax. It is a low-level language with instructions corresponding closely to machine code.

  • assembly languages — Assembly languages are low-level programming languages that use mnemonic instructions closely mapped to machine code. They allow direct register manipulation and are commonly identified by x86 or similar instruction sets.

  • COMMA operator — This programming operator is commonly used in C-style for-loops to combine expressions into one statement. The first expression is evaluated and discarded, then the second is evaluated for its value.

  • declarations
    • Declaration — A declaration is the act of naming a variable or function and specifying its type before use. In statically typed languages, this is the step that introduces an identifier and its type, often with scope determined by where it appears.
  • educational programming languages
    • Logo — Logo is an educational programming language descended from Lisp and famous for turtle graphics. It is associated with simple movement commands such as moving forward and lifting the pen, and it was designed to teach mathematical ideas through coding.

  • Eiffel — Eiffel is the name of an object-oriented programming language created by Bertrand Meyer. It is known for design by contract and heavy use of assertions to enforce the relationship between routines and callers.

  • Function arguments
    • argument — An argument is the value or values passed into a function, often written in parentheses after the function name. In functional programming, currying reduces a function’s arity by transforming it to take one argument at a time.

  • functional programming language — A functional programming language is one that emphasizes functions, recursion, and minimizing side effects. Lisp, Scheme, and Haskell are standard examples, with Haskell often treated as the purest form.

  • goto statement — The goto statement is a control-flow instruction that jumps directly to a labeled line or target elsewhere in a program. It was common in early languages such as BASIC and Pascal and became controversial because unrestricted use could make code hard to follow.

  • interpreter — An interpreter is a program that translates source code as it runs, rather than compiling the whole program in advance. Because it executes code line by line or in small pieces, it is often slower than compiled code.

  • Kotlin — Kotlin is a JetBrains programming language that interoperates fully with Java and is widely used for Android development. It is known for features such as the Elvis operator and for supporting modern JVM application development.

  • lazy evaluation — Lazy evaluation is the strategy of delaying computation until a value is actually needed. It is especially associated with functional languages such as Haskell and with the construction of infinite data structures.

  • lean — Lean is a term for systems or products designed to minimize waste, defects, and excess inventory. It also names a dependently typed programming language used for theorem proving, and appears in phrases like Lean startup and Lean manufacturing.

  • list comprehensions — List comprehensions are a compact syntax for building lists from expressions and iteration clauses. They are common in Python and related functional-language idioms, where they resemble set-builder notation.

  • logic programming languages
    • Prolog — Prolog is a logic programming language developed in the early 1970s for symbolic deduction. Programs are written as facts and Horn clauses, and queries are entered with the familiar ?- prompt.

  • MATLAB — MATLAB is MathWorks’s engineering and numerical-computation language and modeling environment, originally designed by Cleve Moler in the 1970s and later developed by MathWorks. It is widely used for scientific and applied mathematics problems, is known for matrix manipulation and the Simulink modeling environment, and features such as the ode45 solver and live scripts; GNU Octave is a free alternative.

  • null — Null is the value or symbol for nothing, emptiness, or absence of a value. It appears in programming languages and statistics as a special placeholder, missing value, or empty set concept.

  • object-oriented programming languages — Object-oriented programming languages organize programs around objects that combine state and behavior, with features such as encapsulation, inheritance, and polymorphism. Examples include Java, C++, Eiffel, and Smalltalk, and they often support dynamic dispatch through method calls on objects.
    • Access modifiers
      • protected — In object-oriented programming, protected is an access level that allows a class member to be used by derived classes but not by unrelated classes. It is a middle ground between public and private access, and is used in languages such as C++ and Java.

    • C++ (“C plus plus”) — C++ is the object-oriented programming language developed at Bell Labs by Bjarne Stroustrup as an extension of C. It is known for explicit memory management, the most vexing parse, and smart pointers in the standard template library ecosystem. Its name comes from the increment operator, and it is the language that Carbon aims to succeed.

    • classes — Classes are the basic building blocks of object-oriented programming, defining objects through constructors, methods, and attributes. They can support inheritance and encapsulation, and show up in languages such as Java, Python, C++, Haskell, and R.
      • class — A class is a category or type, whether in object-oriented programming, taxonomy, or social stratification. In programming, the keyword class defines an object template, while in sociology the term can refer to groups such as the bourgeoisie and proletariat or to socioeconomic status.

    • constructor — A constructor is the special object-oriented method used to create and initialize an object. It usually shares the class name in languages like C++, while Java uses the keyword new to invoke it indirectly. If a class does not define one explicitly, a default constructor may be generated by the compiler.

    • Encapsulation — Encapsulation is the object-oriented programming principle of hiding a class’s internal data and restricting access through a controlled interface. It supports modularity, refactoring, and the separation of public methods from private state.

    • inheritance — Inheritance in object-oriented programming lets a derived class acquire the methods and data of a base class. It is one of the core OOP principles alongside encapsulation and polymorphism, and it underlies subclassing and the “is-a” relationship.

    • Interface — An interface in programming is a set of methods a class promises to implement without providing the implementation itself. In Java, it defines a type that classes can adopt while remaining distinct from concrete classes.

    • methods — In programming, methods are procedures or functions attached to classes and objects. In philosophy of science, methods can also mean the different ways of inquiring discussed in Peirce’s The Fixation of Belief.

    • Objective-C — Objective-C is an object-oriented programming language built on top of C. It became closely associated with NeXT and later with Macintosh software development.

    • objects — Objects are the basic entities manipulated by object-oriented programming, where classes create instances through constructors and languages like Java and C++ are designed around them. The term also appears in psychology, where object permanence describes the understanding that things continue to exist when out of sight. Clues may also connect them to encapsulation, inheritance, and polymorphism.

    • operator overloading — Operator overloading is the object-oriented programming technique of redefining standard operators so they work with user-defined types. In C++, it can apply to things like the stream insertion operator or the unary plus-plus operator.

    • Smalltalk — Smalltalk is an object-oriented programming language developed at Xerox by Alan Kay and others. It is especially associated with message passing between objects and is often described as the first true object-oriented language.

    • virtual functions
      • virtual function — A virtual function is a member function whose final implementation is chosen at run time based on the object’s actual class. In object-oriented programming, declaring a function virtual enables dynamic dispatch and polymorphism.

  • Overloading — Overloading is a programming practice in which the same function name or operator can have different meanings depending on its parameters or operand types. In object-oriented languages, it lets one symbol handle several related forms of input.

  • Pascal — Pascal is a programming language designed by Niklaus Wirth for teaching structured programming. The same name also refers to the SI unit of pressure, equal to one newton per square meter, named for Blaise Pascal.

  • Pointers — Pointers are variables that store memory addresses in languages like C and C++. They are manipulated with the asterisk for dereferencing and can become wild, dangling, or null when misused or uninitialized; after deallocation they may dangle, and related ideas include hazard pointers for safe concurrent memory access.
    • dangling pointer
      • dangling pointers — Dangling pointers are memory references that still exist after the memory they point to has been freed. They can cause crashes or other memory-safety bugs when dereferenced.

    • null pointers — Null pointers are pointer values that refer to no valid object or data. Their misuse can cause crashes or segmentation faults, and Tony Hoare later called them his “billion-dollar mistake.”

    • pointer — A pointer is a variable that stores a memory address and refers to another object or location in memory. Pointers are used in linked lists, dynamic allocation, and low-level languages like C and C++.

    • pointer variable — A pointer variable is a variable whose value refers to another location in memory. It is a basic concept in languages such as C, C++, Pascal, and assembly-level programming.
  • polymorphism — Polymorphism is the ability of one function or concept to take many forms, whether in biology, materials science, or computer science. In programming, it appears through overloading, overriding, generics, and dynamic dispatch across different data types, and in object-oriented programming it is the ability of different forms to respond appropriately to the same method. In biology, it can describe a gene with multiple common alleles in a population.
    • subtype polymorphism — Subtype polymorphism is an object-oriented programming concept in which the same operation can behave differently depending on the object’s actual type. It underlies features such as interfaces and method dispatch in languages like Java.

  • private — Private is the lowest enlisted military rank and is the basis for the cartoon soldier SNAFU in World War II instructional films. The word also describes class members in Java and the idea of something known only within a single subject’s perspective.

  • return — In programming languages such as C, C++, and Pascal, return is the statement that ends a function and can send a value back to the caller. In Pokémon, Return is also the Normal-type move whose power depends on friendship or loyalty.

  • scripting languages

    • Perl — Larry Wall’s string-processing scripting language, often expanded as Practical Extraction and Reporting Language. It became widely associated with text processing, text parsing, and web CGI scripting, and is known for the slogan “There’s more than one way to do it” and the O’Reilly camel book.

    • scripting language — A scripting language is a high-level language often run through an interpreter rather than compiled. Such languages are commonly used to automate tasks, with examples including Python, Perl, PHP, and Ruby.

  • source code — Source code is the text a programmer writes in a programming language before it is compiled or interpreted. It can be stored in version control, run through eval in dynamic languages, and even appear in XSS vectors or quines.

  • super — The prefix super appears in several science terms including superconductivity, superfluidity, and supersymmetry. It also marks the near-frictionless behaviors studied in superlubricity and the extreme chemical state of superacids. Outside science, super is also the keyword used in Java to call a parent class method. The packet’s clues use it as a general prefix clue rather than a single technical definition.

  • syntactic sugar — Syntactic sugar is programming-language syntax that changes how code looks rather than what it can do. It is used for readability and convenience, as with shorthand forms like compound assignment.

  • virtual — Virtual is the adjective for memory, machines, particles, and images that are not physically real but behave as if they are. It also appears in programming as virtual methods and inheritance, and in physics in terms like virtual particles and virtual work.

  • Visual Basic — Visual Basic is Microsoft’s easy-to-learn programming language, famous for its drag-and-drop GUI tools and simple syntax. It spawned variants such as VBA and VB.NET and was widely used for Windows applications and scripting.

  • void — Void is a common title word in games, programming, and astronomy, where it can name a function return type, a large empty region between filaments, or a surreal puzzle and shooter title. The clue set points to the word’s broad sense of emptiness and its use in titles like Void Stranger and Post Void.
• Computer languages
  • markup languages — Markup languages are text-annotation systems that mix semantic and formatting tags. They are often contrasted with WYSIWYG systems, and examples include XML, YAML, and Markdown.

    • Markdown — Markdown is a lightweight text format for writing plain-text documents that render as formatted HTML. It is widely used in README files and on sites like GitHub and Reddit, with CommonMark as a standardizing implementation.

    • Standard Generalized Markup Language — Standard Generalized Markup Language, or SGML, is an older markup language from which HTML was later derived. It is a generalized system for defining document structures rather than a single fixed formatting standard.

• memory management

  • Garbage collector — A garbage collector is the job Troy Maxson has in Fences, where he complains about racial barriers in that work. In programming, garbage collection automatically reclaims unreachable objects to reduce memory leaks without explicit destructor calls.

  • reference counting — Reference counting is a memory-management technique that tracks how many pointers refer to an object. When the count drops to zero, the object can be deallocated automatically in garbage collection schemes that use it.

• Programming language theory
  • arity — Arity is the number of arguments or inputs a function or operator takes. In functional programming and logic, currying and Skolemization both make use of this concept.
• Programming concepts
  • immutable — Immutable objects cannot have their state changed after creation. They are valued in programming because they are thread-safe and often require no defensive copying.

File Formats and Serialization

• data encoding
  • QR codes — QR codes are two-dimensional barcodes with three finder squares, Reed-Solomon error correction, and numbered versions that scale in size. They were developed by Denso Wave and became especially common in Chinese mobile payments.
• File formats
  • Document formats
    • PDF — PDF, or Portable Document Format, is Adobe’s widely used file format for document sharing and printing. It grew from Adobe technology associated with PostScript and became broadly accessible after browser plugins and dedicated readers made it easier to view online.
  • image file formats
    • image files — Image files store visual data in formats such as PNG, JPEG, GIF, SVG, and XCF. Some are raster-based and use pixels, while others like SVG are vector formats defined with XML. They are often compressed or dithered to manage size and color depth, and they can also be used for steganography by hiding data in their bytes or headers. Generation loss is a common issue for repeated JPEG saves.
  • PDF — PDF, short for Portable Document Format, is Adobe’s document format derived from PostScript and first editable in Acrobat. The same abbreviation can also mean probability density function in mathematics, where it denotes the derivative of a cumulative distribution function.
• image compression
  • JPEG — JPEG is a lossy standard for compressing still images, commonly used for photographs. It was developed by the Joint Photographic Experts Group and typically works by converting RGB data to YCbCr, processing 8-by-8 blocks with a discrete cosine transform, applying quantization, and then reversing the transform for storage. JPEG files begin with the SOI marker FFD8 and commonly carry EXIF metadata.
• Image file formats
  • Graphics Interchange Format — GIF is a bitmap image format widely used for short animations and looping image files, often for short animated clips and reaction images. Its standard compression scheme uses the Lempel-Ziv-Welch algorithm. The format originated as the Graphics Interchange Format and became associated with early online graphics use, CompuServe, and later licensing disputes involving Unisys. Its pronunciation became a long-running internet joke, especially after Steve Wilhite publicly insisted on a soft G.
• Multimedia container formats
  • Ogg — Ogg is a digital container format from Xiph.Org used for multimedia files. It is associated with codecs such as Vorbis, FLAC, and Speex.

Digital Logic and Circuits

• Boolean minimization algorithms
  • Quine-McCluskey algorithm — A tabular Boolean minimization procedure that finds prime implicants and essential prime implicants, serving as a more programmable alternative to Karnaugh maps, especially for functions with many variables.
• Digital circuits
  • clocking
    • clock signal — A clock signal is the periodic timing signal that synchronizes digital circuits and flip-flops. Its frequency is often measured in gigahertz and is tied to CPU power consumption and timing skew.

  • flip-flop — A flip-flop is a bistable digital circuit that stores one bit and changes state on a clock edge or trigger. Variants include SR, D, T, and JK types, and they are used in shift registers and other sequential logic.

  • shift register — A shift register is a chain of flip-flops that moves stored bits one position per clock cycle. It can convert between serial and parallel data and is used as a simple digital memory element.
• digital logic

  • Flip-flop — A flip-flop is a bistable electronic circuit used to store information in digital systems. Its name also refers to a common type of beach footwear, and toggle is an accepted alternate term.

  • SR latch — An SR latch is a bistable sequential circuit built from cross-coupled NOR or NAND gates. It stores a set or reset state and keeps complementary Q and Q-bar outputs stable through feedback until the inputs change.

  • AND gate — An AND gate is a basic digital logic gate that outputs true only when all of its inputs are true. It corresponds to logical conjunction and is a standard building block in circuit design.

  • Karnaugh maps — Karnaugh maps are Gray-code truth tables used to simplify Boolean expressions by grouping adjacent cells. They are also called Veitch diagrams and are a standard manual aid for minimizing logic-gate designs.

  • logic gates — Logic gates are the basic switching elements of Boolean and digital circuits, carrying out operations such as AND, OR, NAND, and XOR on input bits. In quantum computing, their analogues are reversible unitary operations, and universal sets of gates can be combined to implement any truth table.

    • NAND — NAND means “not both,” the logical connective that is false only when both inputs are true. It is the negation of conjunction, often described as the complement of “and,” and is a fundamental logic gate in digital circuits. NAND gates can be cross-coupled to build flip-flops.

    • NAND gates — NAND gates are logic gates that output low only when all inputs are high. They are functionally complete and are represented by the conjunction symbol with a negation, often called the Sheffer stroke.

    • NOR — NOR is a logical operator that returns true only when both inputs are false. Its gate is functionally complete, so it can be used to build other logic gates and SR flip-flops.

    • NOR and NAND — NOR and NAND are functionally complete logic gates, meaning any Boolean function can be built from combinations of either one. Tying both inputs together makes each gate act like a NOT gate.

    • NOR gates
      • NOR gate — A NOR gate outputs 1 only when all of its inputs are 0, making it the inverse of an OR gate. It is a universal gate and can be used to build SR latches and other logic circuits.

    • NOT gate — A NOT gate, also called an inverter, outputs the opposite of its input. If the input is 0, the output is 1.

    • OR gate — An OR gate outputs a one when at least one input is one. Its inverted form is the NOR gate, which outputs one only when both inputs are zero.

  • Multiplexers — Multiplexers are digital logic components that select one of several input lines and route it to a single output based on control lines. They are commonly described as data selectors or muxes in circuit design.

  • transistor-transistor logic — Transistor-transistor logic is a digital logic family built around transistors, especially bipolar transistors, rather than resistors or diodes. It was widely used in early integrated circuits, uses standard voltage ranges for logic 0 and logic 1, and is associated with classic 7400-series integrated circuits. It was largely displaced by CMOS.
• Digital logic circuits
  • arithmetic circuits
    • adder — An adder is a digital logic circuit that sums binary inputs, with half-adder and full-adder forms. Quizbowl clues often mention XOR, AND, and OR gates, along with carry-in and carry-lookahead designs that reduce ripple delay.

Data Structures

Compare data structures by organization, operations, and tradeoffs.

Arrays and Linked Lists

• Array — contiguous block of memory; random access O(1); insertion/deletion at arbitrary index O(n) due to shifting; fixed size in static variants, amortized O(1) append in dynamic arrays. An array is an ordered data structure storing elements under one name, usually with constant-time access by index. Arrays are central to slicing, stride-based memory layout, and optimized implementations in languages and libraries such as FORTRAN, MATLAB, and NumPy.
  • arrays — Arrays are ordered indexed collections, often stored in contiguous memory and accessed with square brackets or integer position. They may be one-dimensional or multidimensional, underlie storage such as matrices, and are central to concepts like stride, bounds checking, and dynamic resizing. Dynamic versions are used in languages like Java, C++, PHP, and JavaScript.
    • one-dimensional arrays — One-dimensional arrays are contiguous blocks of memory accessed by integer indices. They are often used to illustrate in-place reversal and the difference between one-level and more complex memory structures.
  • Dynamic array (ArrayList / vector) — doubles capacity when full; amortized O(1) append; underlying copies are O(n) but infrequent.
• Linked list (singly) — each node stores a value and a pointer to the next node; O(1) head insertion/deletion; O(n) search and arbitrary access; no wasted capacity.
  • linked list — A linked list is a linear data structure made of nodes connected by pointers, usually with each node pointing to the next node and sometimes to the previous one as well. Common variants include singly linked, doubly linked, circular, headed, sentinel-based, and unrolled linked lists. They are used in stacks, queues, hash-table chaining, skip lists, and adjacency lists, and appear in languages such as Scheme and Lisp. Sentinels or unrolled variants can improve performance or simplify destruction.

    • sentinel node — A sentinel node is a dummy node used in linked lists to mark an endpoint or simplify list handling. In broader tree terminology, a leaf is a node with no children.

    • sentinel nodes — Sentinel nodes are empty or terminal nodes placed in linked lists to reduce null checks and off-by-one errors. They are also used in hash-table chaining as placeholders at the ends of buckets.

    • singly linked list — A singly linked list is a linear data structure whose nodes each point to the next node in the sequence. Its head node begins the chain, and cycle detection can be done with Floyd’s tortoise-and-hare algorithm.

  • Doubly linked list — each node stores prev and next pointers; O(1) deletion given the node; used in LRU cache implementations. This makes forward and reverse traversal easy. A sentinel node is sometimes used to simplify edge cases.

Stacks and Queues

• Stack — LIFO; push/pop/peek all O(1); implemented with array or linked list; used for function call frames, expression parsing, DFS. Also associated with the call stack, reverse Polish notation, canary values, and buffer overflow attacks.
  • Stack — A stack is a last-in, first-out data structure with constant-time push and pop operations. It is used for recursive call frames, reverse Polish notation, depth-first search, pushdown automata, and many virtual-machine implementations. In computer architecture, stack frames and stack pointers manage local variables and subroutine returns, and stack overflow occurs when recursion goes too far.

    • call stacks — A call stack is a last-in, first-out structure used to manage function calls and recursion. It stores frames for program execution, underlies backtracking, and is closely related to reverse Polish notation and stack overflow.

    • last in, first out — Last in, first out is the stack-processing order in which the most recently added item is the first one removed. It contrasts with queue behavior and is abbreviated LIFO.

  • stack operations
    • push and pop — Push and pop are the basic stack operations that add an item to the top of the stack and remove the top item. They are common building blocks in recursive algorithms and data-structure procedures such as quicksort.
• Queue — FIFO; enqueue/dequeue O(1) with circular array or linked list; used for BFS, scheduling.
  • queues — Queues are first-in, first-out data structures used to model waiting lines, buffers, and many scheduling problems. They appear in breadth-first search, priority-queue variants, and Kendall’s notation for queueing systems.
    • FIFO
      • First In, First Out — First in, first out is the queue discipline in which the first item added is the first one removed. It is a basic scheduling rule for tasks and the standard behavior of queues in computer science.
• Deque (double-ended queue) — O(1) insertion and deletion at both ends; sliding-window problems.
  • deque — A deque is a data structure that allows insertion at either end. In the version described here, removal is limited to the front end.
• Priority queue — element with the highest (or lowest) priority is dequeued first; typically implemented as a heap; O(log n) push/pop. It removes the highest- or lowest-priority element before the others rather than using first-in, first-out order. It is often implemented with a heap and appears in algorithms such as Prim’s minimum spanning tree method, A* search, and Fortune’s algorithm.
  • Priority queues — Priority queues are data structures that remove elements according to an associated priority value rather than simple insertion order. They are often implemented with heaps and are useful in graph algorithms such as Dijkstra’s algorithm.

Trees

• Binary tree — each node has at most two children; a complete binary tree fills levels left to right; a perfect binary tree has all leaves at the same level. Binary search trees, AVL trees, and red-black trees are important examples, and traversals such as pre-order, in-order, and post-order are standard ways to explore them.
  • binary trees — Binary trees are linked-node data structures in which each parent has at most two children, and they are traversed by pre-order, in-order, and post-order methods. The red-black and binary search variants are common quizbowl clues, along with the root node and the use of trees in search algorithms.
• Binary search tree (BST) — left child < parent < right child; search/insert/delete O(h) where h is height; degenerates to O(n) for sorted input.

  • AVL tree — self-balancing BST; height difference between subtrees ≤ 1; rotations maintain O(log n) operations. It is also called the Adelson-Velskii-Landis tree, named for Georgy Adelson-Velsky and Evgenii Landis; after insertions and deletions it uses single and double rotations to restore balance.

  • Red-black tree — self-balancing BST with node coloring; guarantees O(log n); used in C++ std::map, Java TreeMap, Linux scheduler. Its balancing rules color each node red or black and keep the longest root-to-leaf path at most twice the shortest, which supports efficient search, insertion, and deletion.

  • binary search trees
    • Binary Search Tree — A rooted tree in which all values in the left subtree are smaller than the node and all values in the right subtree are larger. It stores ordered data and supports efficient searching, insertion, and deletion; common traversals include preorder, inorder, and postorder. Red-black trees and treaps are related self-balancing examples.
  • balanced binary search trees
    • Red-black trees — Red-black trees are self-balancing binary search trees whose nodes are colored red or black to keep paths to leaves within logarithmic height. They are closely related to 2-3-4 trees and rebalance through rotations and recoloring.
  • balanced trees
    • balanced — A balanced tree or data structure keeps its height from growing too unevenly, as in AVL and red-black trees. Self-balancing trees rearrange themselves to preserve efficient logarithmic search time.
  • self-balancing trees
    • self-balancing — Self-balancing describes search trees that automatically rotate or restructure themselves to keep height low. AVL trees and red-black trees are the standard examples of this property.
  • randomized trees
    • Treap — A treap is a randomized data structure that combines binary-search-tree ordering with heap ordering on a priority key. Its name reflects the blend of tree and heap properties, and it is designed to support efficient search, insertion, and deletion on average.

• B-tree — generalized balanced tree with branching factor > 2; nodes can hold many keys; minimizes disk I/O; standard in database index structures; B+ tree variant stores all data in leaves with leaf-to-leaf linked list. A B-tree is a self-balancing search tree designed to keep many keys per node and minimize disk access. Its common variant, the B+ tree, stores all data in the leaves and links leaf nodes for efficient ordered traversal.

• Trie (prefix tree) — tree where each path from root to node encodes a string prefix; O(m) search where m is string length; used in autocomplete, spell-check.
  • tries
    • trie — A trie, or prefix tree, stores string keys by shared prefixes along paths from the root. It is used in applications like autocomplete, spell-checking, and longest-prefix matching.

• Segment tree — binary tree over an array; supports range queries (sum, min, max) and point updates in O(log n); a Fenwick tree (binary indexed tree) is a simpler structure for prefix sums.

• search trees
  • splay tree — A splay tree is a self-adjusting binary search tree that moves recently accessed nodes to the root through zig-zig and zig-zag rotations. It is studied for properties such as the dynamic optimality conjecture, the working set property, and amortized logarithmic performance.
• Balanced search trees
  • Rotations
    • tree rotation — A tree rotation is a local restructuring operation in a search tree that moves one node up and one node down while preserving order. Rotations are used to rebalance trees such as red-black trees and can reduce the height of the structure.
• tree traversals
  • converse postorder — Converse postorder is a tree traversal order used to reverse the usual postorder output. It is the kind of traversal needed to produce an output such as 3, 2, 1 from a tree.
• traversal
  • tree traversal — Tree traversal is the process of visiting every node of a tree, whether in preorder, inorder, or postorder form. It also underlies many compiler tasks, including AST walking, symbol-table construction, and certain SSA renaming steps.

Heaps

• Min-heap / max-heap — complete binary tree where parent ≤ children (min) or parent ≥ children (max); stored compactly in an array: left child at 2i+1, right child at 2i+2; insert O(log n), extract-min/max O(log n), peek O(1), build from array O(n).
  • heaps — Heaps are priority-queue data structures in which each parent is ordered relative to its children, commonly as a min-heap or max-heap. Common variants include binary heaps, Fibonacci heaps, binomial heaps, leftist heaps, and hollow heaps. They support operations such as decrease-key, meld, and heap construction algorithms like Floyd’s heapify.

    • binary heap — A binary heap is a complete binary tree stored in array form that supports priority queues efficiently. It gives quick access to the minimum or maximum element, and it underlies heap sort, which runs in O(n log n) time.

    • Fibonacci heap — A Fibonacci heap is a priority-queue data structure made of a forest of heap-ordered trees with amortized constant-time decrease-key and meld operations. It was introduced by Fredman and Tarjan and is often used to speed up algorithms like Prim’s and Dijkstra’s.

    • heap — A heap is a tree-based data structure used to implement priority queues and heap sort, where parents dominate or are dominated by their children. Variants include the Fibonacci heap, binomial heap, soft heap, and weak heap, each designed to speed up merge or decrease-key operations.

  • Heap applications — priority queues, heap sort, Dijkstra’s algorithm, scheduling.

Hash Tables

• Hash table — key-value store; hash function maps keys to bucket indices; average O(1) insert, delete, search; worst case O(n) with collisions. Collisions happen when different keys land in the same bucket and are commonly handled by chaining or open addressing.
  • hash tables — Hash tables store keys in arrays by means of a hash function, giving average constant-time lookup when collisions are handled well. They are commonly implemented with chaining or open addressing, and variants include hash maps and hash sets.

    • chaining — Chaining is a hash-table collision resolution method in which all keys that map to the same slot are stored together. It is the opposite of open addressing and typically uses linked lists or pointers to link collided entries.

    • open addressing

      • linear probing — Linear probing is an open-addressing hash-table collision resolution method that checks the next bucket, then continues consecutively until an open slot is found. It stores a collided value in the next available position instead of using a separate chain.
  • Collision resolution — separate chaining (each bucket is a linked list); open addressing (linear probing, quadratic probing, double hashing); load factor λ = n/m; rehashing triggered at high load.
• Hash function properties — deterministic, uniform distribution, fast to compute; cryptographic hashes additionally require preimage resistance and collision resistance.
  • hash functions — These one-way functions map arbitrary data to fixed values and are used to power hash tables and related lookup structures. They are also central to checksums, Bloom filters, collision resistance, and cryptographic constructions such as SHA.
    • hash — A hash is a function that maps input data to a fixed-size output, often used to support fast lookup and verification. Related terms include hash tables and cryptographic hashes such as MD5 and SHA.

Graphs

• Representations — adjacency matrix: O(V²) space, O(1) edge lookup; adjacency list: O(V + E) space, standard for sparse graphs.

• Directed (digraph) vs undirected — edges have direction or not; in-degree / out-degree vs degree.

• Weighted vs unweighted — weighted edges carry a numeric cost; used in shortest-path and MST algorithms.

• DAG (directed acyclic graph) — no cycles; enables topological sort; used in dependency resolution, build systems.

• Adjacency matrix — V×V matrix; entry [i][j] = 1 (or weight) if edge i→j exists; O(V²) space; O(1) edge lookup; preferred for dense graphs.

• Adjacency list — array of lists, one per vertex; O(V + E) space; the standard representation for sparse graphs; used by BFS, DFS, Dijkstra.

• directed graphs

  • Acyclic graph — A directed graph is acyclic, or a DAG, if depth-first search finds no back edge. This means the graph contains no directed cycles.

  • strongly connected — A directed graph is strongly connected when every vertex can reach every other vertex by a directed path. Kosaraju’s and Tarjan’s algorithms are standard tools for finding its components.

• graph theory

  • de Bruijn graphs — A de Bruijn graph is a directed graph built from overlapping k-mers or k-1-mers. It is important in DNA sequence assembly and in problems related to Eulerian paths and minimal cyclic superstrings.

  • clique problem — The clique problem asks whether a graph contains a complete subgraph of size k. It is a classic NP-complete problem often linked to independent sets and reductions from SAT.

  • free tree — A free tree is a connected, acyclic, undirected graph with no designated root. These graphs are often discussed as data structures and can be rooted by choosing a distinguished node.

  • graph — A mathematical or computer-science structure made of vertices connected by edges; it may be directed, undirected, weighted, simple, or cyclic. Graphs model networks such as road maps and are studied with adjacency lists and adjacency matrices, Kruskal’s algorithm, Dijkstra’s algorithm, breadth-first and depth-first search, topological sorting of DAGs, strongly connected components, graph coloring, clique size, shortest paths, spanning trees, and graph isomorphism.

  • graph properties
    • acyclic — Acyclic describes a graph or model with no cycles, making exact message-passing inference feasible in finite time. The term also appears in antiviral chemistry, including acyclic nucleoside phosphonates and the drug name aciclovir.
  • planar graphs
    • planarity — Planarity is the graph property of being drawable on a plane without edge crossings, equivalently embeddable on a two-dimensional surface. Kuratowski’s theorem characterizes it by forbidding subdivisions of K5 and K3,3, and the Hopcroft-Tarjan algorithm is a classic test for it; Lichtenstein and Demaine-style reductions also use planar gadgets.

  • spanning trees — A spanning tree connects all vertices of a graph without cycles. Minimum spanning trees are the optimal version of these structures, and they are central to algorithms such as Prim’s and Borůvka’s.

  • transitive closure — The transitive closure of a directed graph connects each vertex to every other vertex reachable from it. It can be computed efficiently by algorithms such as Warshall’s or Floyd-Warshall’s.

  • Vertex cover — A vertex cover is a set of vertices in a graph such that every edge touches at least one chosen vertex. Finding a minimum vertex cover is NP-complete and appears among Karp’s original NP-complete problems.

Other Key Structures

• Disjoint-set / union-find — data structure tracking a partition of elements into disjoint sets; supports find (which set does x belong to?) and union (merge two sets); with path compression and union by rank, both operations are nearly O(1) amortized (inverse Ackermann time); critical for Kruskal’s MST algorithm.

• Skip list — probabilistic data structure; layered linked lists with “express lanes”; supports search, insert, delete in O(log n) expected time; used in Redis sorted sets; invented by William Pugh (1990). The structure was invented by William Pugh in 1990 and is used in Redis sorted sets.

• Bloom filter — probabilistic set-membership structure; uses k hash functions and a bit array; false positives possible, false negatives impossible; space-efficient; used in databases, caches, and CDNs to avoid expensive lookups.

• Fenwick tree (binary indexed tree) — compact array-based structure for prefix-sum queries and point updates, both O(log n); simpler implementation than a segment tree for sum queries.

*O(1) deletion given a pointer to the node.

• Circular buffer (ring buffer) — fixed-size array treated as circular; head and tail pointers advance with wrap-around; O(1) enqueue and dequeue; used in I/O buffering, producer-consumer pipelines.

• Sparse matrix — matrix with mostly zero entries; compressed representations (CSR, COO) store only non-zero values; key in scientific computing, graph algorithms, and neural-network layers. Algorithms like Cuthill-McKee and reverse Cuthill-McKee are used to reorder sparse matrices into banded form for more efficient storage and computation.

• LRU cache — Least Recently Used eviction policy; implemented with a doubly linked list + hash map achieving O(1) get and put; frequent interview problem; used in OS page replacement and CPU caches.

Related Concepts and Applications

• lists — Lists are linear data structures that store elements in sequence and can be implemented as linked or doubly linked structures. In programming languages such as Python and Lisp-related systems, lists may be built with special notation or returned by functions that produce iterable sequences.

• quadtrees
  • quadtree — A quadtree is a hierarchical spatial data structure in which each internal node has up to four children, subdividing a region into quadrants. It is a standard way to organize two-dimensional data and appears in variants such as PR and PM quadtrees.
• Trees
  • Tree — A hierarchical plant or data structure, depending on context. Mythic examples include Yggdrasil and the Bodhi tree, while computer-science clues point to rooted structures with leaves, branches, and variants such as AVL, binary, quad-, and octrees. The answer is the broad category shared by both natural and abstract forms.

• Last in, first out / First in, first out — LIFO stands for last in, first out, and FIFO stands for first in, first out. These are standard inventory and data-structure ordering conventions that describe which item is removed first.

• list — A list is an ordered collection or sequence of elements; in programming it is often a basic container type that can be implemented with an array or a linked structure, including a linked list. Lists are accessed by index and traversed in order, and functional languages use operations such as cons. They are also used in operations like map and zip, and can be organized as skip lists for faster search.

Algorithms, Searching, and Sorting

Understand algorithmic strategies before individual searching and sorting methods.

Algorithms

• Algorithms — Algorithms are finite step-by-step procedures for solving problems or carrying out tasks. In computer science they are analyzed by time and space complexity, often using big-O notation, and common examples include sorting, search, divide-and-conquer methods, and greedy methods such as Prim’s and Kruskal’s.

  • algorithm — An algorithm is a finite step-by-step procedure for transforming input into output or solving a problem. Common examples include Dijkstra’s algorithm, Kruskal’s algorithm, Euclid’s algorithm, and Fisher-Yates shuffling.

  • divide-and-conquer algorithm — A divide-and-conquer algorithm solves a problem by recursively splitting it into smaller subproblems of the same type. Quicksort is the classic example, and the Master theorem is used to analyze its recurrence relations.

  • dynamic programming — Dynamic programming is an algorithmic technique that solves problems by breaking them into overlapping subproblems and storing intermediate results. It appears in knapsack, shortest-path, sequence-alignment, and parsing algorithms, and is often described through memoization or tabulation.
    • Viterbi algorithm — The Viterbi algorithm is a dynamic-programming method for finding the most likely hidden-state path in a hidden Markov model. It is also used in decoding convolutional codes and in applications such as speech recognition, part-of-speech tagging, and gene prediction.
  • exhaustive search
    • brute force — Brute force is the straightforward method of trying every possibility until a solution is found. In algorithms and cryptography, it usually refers to exhaustive search or exhaustive key testing rather than a clever shortcut.

  • Fisher-Yates shuffle — The Fisher-Yates shuffle is an algorithm for randomly permuting an array by swapping each element with a randomly chosen one from the remaining range. It runs in linear time and is closely related to Sattolo’s algorithm and the version popularized by Donald Knuth.

  • Floyd-Warshall algorithm — A dynamic-programming method for the all-pairs shortest path problem in a weighted graph. It repeatedly improves an adjacency-matrix table of distances, runs in cubic time, is especially efficient for dense graphs, and can detect negative cycles from the diagonal; it is also used for transitive closure.

  • greedy algorithms — Greedy algorithms make the locally optimal choice at each step in hopes of reaching a global optimum. They appear in problems such as fractional knapsack, Huffman coding, and Kruskal’s minimum spanning tree algorithm.
    • greedy algorithm — A greedy algorithm makes the locally optimal choice at each step, hoping to reach a global optimum. Standard examples include Dijkstra’s algorithm, Prim’s algorithm, Kruskal’s algorithm, and the classic change-making problem on suitable coin systems.
  • hashing — Hashing is the process of mapping data to fixed-size outputs for use in hash tables, where collisions can occur and salts can be added for password storage. Related applications include Bloom filters, locality-sensitive hashing for similarity search, and consistent hashing for load balancing.

    • hash collisions — A hash collision occurs when two different inputs produce the same output from a hash function. Collisions are central to hash tables and cryptography, including the birthday paradox and birthday-attack-style reasoning about collision probability. Common responses in hash tables include chaining and open addressing; they also matter in attacks on cryptographic hashes such as SHA-1.

    • Hashing function — A hash function maps input keys or arbitrary data to fixed values, often compressing data into table slots, indices, or memory addresses for efficient lookup. Good hash functions spread inputs uniformly and help avoid collisions. They are used in hash tables and related data structures, checksums, Bloom filters, Rabin-Karp-style string matching, and cryptography.

  • online algorithms — Online algorithms process input one piece at a time and must make immediate decisions without seeing the full data set in advance. They are analyzed with competitive analysis and include examples such as paging algorithms, insertion sort in streaming settings, and the work function algorithm.

    • Canadian traveler problem — The Canadian traveler problem is an online shortest-path problem on a graph whose edges may disappear during traversal. The goal is to minimize traversal cost relative to an offline algorithm that knows in advance which edges will be removed.

    • online algorithm — An online algorithm processes input one piece at a time without seeing the whole sequence in advance. Its performance is often studied with competitive analysis against an adversary, as in the ski-rental and secretary problems.

  • procedural generation — Procedural generation is a design method that uses algorithms and pseudorandomness to build game worlds, levels, or content from premade rules and assets. It underlies roguelike randomness and large-scale sandbox worlds such as those in No Man’s Sky.

  • Robert Tarjan — Robert Tarjan is a computer scientist known for algorithms on graphs and data structures, including one that finds strongly connected components in linear time. He also co-developed splay trees and Fibonacci heaps and worked on algorithms for least common ancestors.

  • search algorithms
    • search — Search is the computer-science task of locating a target item in a collection, whether by linear scan, binary search, depth-first search, breadth-first search, or Dijkstra-style traversal. Common examples include graph traversal and sorted-list lookup, with A* and Bellman-Ford appearing as related pathfinding and optimization methods.
  • Search techniques
    • backtracking — Backtracking is a search technique that explores a solution space recursively and retreats when a partial assignment fails. It is a standard approach for constraint-satisfaction problems such as Sudoku and the eight queens puzzle, and it can cause catastrophic behavior in regex engines.

  • searching — Searching is the task of finding a specific item or element in data, using methods such as linear search, binary search, depth-first search, breadth-first search, and string-searching algorithms like Rabin-Karp and KMP. It underlies search engines such as Google and Bing, regular-expression grep, and Grover’s quantum algorithm.

  • Sorting — Computer science task of arranging data into a specified order, such as least to greatest. Common algorithms include bubble sort, insertion sort, selection sort, merge sort, quicksort, heap sort, radix sort, shell sort, bucket sort, smoothsort, and bogo sort. Comparison-based methods require at least O(n log n) time in the general case, while some exchange-based sorts have worst-case quadratic time. Common clue words include pivot, buckets, and n log n runtime.

    • reverse sorted order — Reverse sorted order is an array arrangement with elements ordered from largest to smallest. It is the worst-case configuration for insertion sort because each new element must be shifted past all earlier ones.

    • sorted — A sorted list is arranged in order, making it suitable for binary search and other efficient lookups. In data processing and computer science, sortedness is the property that underlies many comparison-based and non-comparison-based algorithms.

• Euclidean algorithm — finds GCD of two integers by repeated remainder; GCD(a, b) = GCD(b, a mod b); terminates in O(log min(a,b)) steps; one of the oldest known algorithms (Euclid’s Elements, ~300 BCE); extended Euclidean algorithm finds Bezout coefficients. Its extended form also produces Bézout coefficients, making it useful for number-theoretic proofs and computations.

• Two-pointer / sliding window — linear-time techniques for array/string problems; two pointers move toward each other or both move right; avoids nested loops; examples: sorted pair sums, subarray problems.

• Bit manipulation — exploiting binary representations; XOR tricks (find single number, swap without temp), AND/OR masking, left/right shifts; bitmask DP for subset enumeration; O(1) operations.

Recursion and Divide-and-Conquer

• Recursion — a function that calls itself on a smaller subproblem; requires a base case; each call uses stack frame space, so O(n) space for depth n. It is a common pattern in divide-and-conquer algorithms and can be direct or indirect. Classic recursive examples include factorial, Fibonacci, Euclid’s algorithm, merge sort, and quicksort; tail recursion is a special form that can sometimes be optimized.

  • Recursive algorithm — A recursive algorithm solves a problem by reducing it to a smaller instance of the same problem. It is typically implemented by a method or procedure that calls itself.

  • recursive function — A recursive function is one that calls itself, using a base case to halt, and appears in divide-and-conquer algorithms and classic problems like factorials and Towers of Hanoi.

  • recursiveness — Recursiveness is the property of algorithms or functions that call themselves. Classic examples include factorial computation, the Ackermann function, and the McCarthy 91 function.

• Tail recursion — recursive call is the last operation; some languages/compilers optimize to iteration (tail-call optimization); Python does NOT.
  • tail — A tail can mean the rear part of an animal, a stream left by a comet, or the part of a list that follows the first element. In programming, tail recursion and tail-call optimization describe a call made at the end of a function, and Unix’s tail command prints the last lines of a file.
• Divide-and-conquer — split into subproblems, solve recursively, combine; merge sort, quicksort, binary search, Strassen’s matrix multiplication follow this pattern. It is a standard paradigm in algorithm design and also appears in recursive methods such as version-control merging.
  • divide and conquer algorithms — Divide and conquer algorithms solve a problem by breaking it into smaller subproblems, solving them recursively, and combining the results. Typical examples include merge sort, quicksort, binary search, Strassen matrix multiplication, and the Cooley-Tukey FFT, with runtimes often analyzed by the master theorem.

• Master theorem — gives O-notation for recurrences of the form T(n) = aT(n/b) + f(n). It gives closed forms for divide-and-conquer recurrences such as T(n)=aT(n/b)+f(n). It is commonly used to analyze runtimes like merge sort and appears in standard algorithm texts as a tool for asymptotic O-notation.

• recursion and iteration
  • iterative — Iterative methods repeat a process in a sequence rather than by self-reference, and compilers often try to convert recursive calls into that form to avoid repeated call overhead.

Dynamic Programming

• Dynamic programming (DP) — solve overlapping subproblems once, store results; two approaches: top-down (memoization) with recursion + cache; bottom-up (tabulation) fills a table iteratively.

• Optimal substructure — optimal solution to the whole contains optimal solutions to subproblems; required for DP.

• Classic DP problems — Fibonacci, 0/1 knapsack, longest common subsequence (LCS), longest increasing subsequence (LIS), edit distance (Levenshtein), matrix chain multiplication, coin change.

• Memoization — top-down DP; cache results of recursive calls so each subproblem is solved at most once; straightforward to implement from a recursive solution; may have call-stack overhead vs tabulation. It trades memory for speed and is especially useful for recursive problems such as Fibonacci numbers or factorials.

• Edit distance (Levenshtein) — minimum number of single-character insertions, deletions, substitutions to transform one string to another; O(nm) DP; used in spell-check, bioinformatics sequence alignment.

• Longest common subsequence (LCS) — O(nm) DP classic; not the same as longest common substring (contiguous); DNA sequence comparison, diff utilities.

• Sequence alignment algorithms

  • Smith-Waterman algorithm — The Smith-Waterman algorithm is a dynamic-programming method for local sequence alignment. It is slower than global alignment methods but is prized for its sensitivity in comparing DNA or protein sequences.

Greedy Algorithms

• Greedy — make the locally optimal choice at each step; does not always yield global optimum but works for some problems; requires proof of greedy choice and optimal substructure. Greedy regex quantifiers consume as much text as possible. Examples include Dijkstra’s algorithm, Prim’s algorithm, and Kruskal’s algorithm when used with a greedy edge choice.

• Greedy examples — activity selection, Huffman coding, Kruskal’s and Prim’s MST, Dijkstra’s shortest path (non-negative weights only).

• Huffman coding — greedy algorithm for optimal prefix-free compression; builds a binary tree by repeatedly merging the two lowest-frequency symbols; produces variable-length codes where frequent symbols get shorter codes; O(n log n); used in JPEG, MP3, ZIP; David Huffman (1952). It was developed by David Huffman in 1952. It is widely used in compression formats and systems including JPEG, MP3, gzip, and ZIP.

• Activity selection / interval scheduling — greedy: always pick the activity that finishes earliest; proves that greedy is optimal for maximizing non-overlapping intervals; classic proof of greedy correctness.

Graph Algorithms

• graph algorithms

  • depth-first search — Depth-first search is a graph traversal method that explores one branch as far as possible before backtracking. It uses a stack or recursion, timestamps vertices as white, gray, and black, and is used in proofs and algorithms involving trees, cycles, recursive discovery times, and strongly connected components by traversing a graph and its transpose.

  • maximum flow problem — The maximum-flow problem asks for the greatest possible flow through a capacitated network from source to sink. It is equivalent to the minimum cut problem, and classic algorithms include Ford-Fulkerson and Edmonds-Karp.

  • minimum spanning tree — A spanning tree of a connected weighted graph that includes every vertex, has no cycles, and minimizes total edge weight. It is commonly found with Prim’s or Kruskal’s algorithm; related ideas include Borůvka’s algorithm and Euclidean minimum spanning trees.

  • minimum spanning tree algorithms
    • Prim-Jarnik algorithm — The Prim-Jarnik algorithm is a greedy method for finding a minimum spanning tree. Starting from an arbitrary vertex, it repeatedly adds the shortest edge that expands the tree without forming a cycle.

  • minimum spanning trees — A minimum spanning tree is a spanning tree of a weighted graph whose total edge weight is as small as possible. Such trees are found by greedy algorithms like Prim’s and Kruskal’s, and they cannot exist in disconnected graphs because they must include every vertex in one acyclic subgraph.

  • minimum vertex cover — The minimum vertex cover problem asks for the smallest set of vertices that touches every edge of a graph. It has a standard factor-2 approximation and is a classic NP-complete optimization problem.

  • shortest path algorithms — The shortest path problem asks for the minimum-distance or minimum-weight route between vertices or nodes in a graph. Standard methods for finding shortest paths in different settings include Dijkstra’s algorithm, Bellman-Ford, A*, Floyd-Warshall, and Johnson’s algorithm.

    • Bellman-Ford algorithm — The Bellman-Ford algorithm finds single-source shortest paths by repeatedly relaxing edges, and it works with negative edge weights. It is used in Johnson’s algorithm and in distance-vector routing methods such as RIP, with SPFA as a queue-based optimization.

    • Bellman-Ford-Moore algorithm — The Bellman-Ford-Moore algorithm finds single-source shortest paths in graphs that may have negative edge weights. It runs in O(VE) time and can also be used to detect negative cycles.

    • Dijkstra’s — Dijkstra’s algorithm is the classic shortest-path algorithm associated with the Dutch computer scientist Edsger Dijkstra. It works by repeatedly improving tentative distances from a source node, and A* is a heuristic variant built on the same idea.

    • Johnson’s algorithm — Johnson’s algorithm finds all-pairs shortest paths by reweighting edges to eliminate negatives, then running Dijkstra’s algorithm from each vertex. It uses Bellman-Ford in the reweighting step and is often presented as a sparse-graph alternative to Floyd-Warshall.

    • negative edge weights — Negative edge weights are a graph property that breaks Dijkstra’s algorithm and requires Bellman-Ford or similar shortest-path methods. If a cycle of such edges exists, a shortest path may fail to exist at all.

    • negative weight — Graphs with negative-weight edges break Dijkstra’s algorithm, which assumes edge costs are nonnegative. Bellman-Ford can still handle those graphs because it relaxes edges repeatedly instead of relying on greedy shortest-path choices.

  • Shortest path problems
    • single-source shortest path problem — The single-source shortest path problem asks for the shortest paths from one starting vertex to all other vertices in a weighted graph. Dijkstra’s algorithm is the standard method for solving it on graphs with non-negative edge weights.
• Graph Traversal and Components

  • BFS (Breadth-First Search) — explores level by level using a queue; O(V + E); finds shortest paths in unweighted graphs; detects bipartiteness.

  • DFS (Depth-First Search) — explores as deep as possible using a stack (or recursion); O(V + E); used for cycle detection, topological sort, strongly connected components.

  • Topological sort — linear ordering of vertices in a DAG such that all edges go forward; Kahn’s algorithm (BFS-based) or DFS-based (reverse finish order).

  • Strongly Connected Components (SCC) — Tarjan’s algorithm (O(V + E)) and Kosaraju’s algorithm find SCCs in directed graphs.

  • graph traversal

    • breadth-first search — Breadth-first search explores a graph level by level, using a queue to visit all neighbors before moving outward. It is the traversal used for level-order tree searches and appears in algorithms such as Edmonds-Karp.
• Shortest Paths and Search

  • Dijkstra’s algorithm — single-source shortest paths in non-negative weighted graphs; uses a min-heap; O((V + E) log V) with binary heap; fails with negative edge weights. It produces a shortest-path tree and is commonly implemented with a priority queue or heap; Edsger Dijkstra devised it.

  • Bellman-Ford — single-source shortest paths tolerating negative edge weights; relaxes all edges V-1 times; O(VE); can detect negative cycles (a V-th relaxation pass changes a distance); slower than Dijkstra but more general.

  • Floyd-Warshall — all-pairs shortest paths via O(V³) DP; d[i][j][k] = shortest path from i to j using only vertices 1..k as intermediates; handles negative weights but not negative cycles; produces a distance matrix.

  • A* search — BFS/Dijkstra variant using a heuristic h(n) to guide search; optimal when h is admissible (never overestimates); used in pathfinding/game AI.

  • pathfinding algorithms

    • A* search algorithm — A* search is a pathfinding algorithm that uses a heuristic estimate of distance to the goal to speed up shortest-path search. It is a modification of Dijkstra’s algorithm and can be made faster, though less optimal, if its admissibility requirement is relaxed.
• Spanning Trees and Network Flow

  • Kruskal’s algorithm — minimum spanning tree (MST); sort edges by weight; add edge if it doesn’t create a cycle (union-find); O(E log E). It grows a spanning forest by repeatedly adding the lowest-weight edge that connects two separate components, so it also works naturally on disconnected graphs.

  • Prim’s algorithm — MST starting from a node; greedy; O((V + E) log V) with binary heap. It finds a minimum spanning tree in a weighted graph by repeatedly adding the cheapest edge that connects a new vertex.

  • Network flow (max-flow / min-cut) — find maximum flow through a directed capacity graph; Ford-Fulkerson method (augmenting paths); Edmonds-Karp uses BFS for O(VE²); max-flow min-cut theorem: maximum flow equals minimum cut capacity.

  • Network flow

    • Ford-Fulkerson algorithm — The Ford-Fulkerson algorithm is the classic method for computing maximum flow in a network. It works by finding augmenting paths in a residual graph, and its proof underlies the max-flow min-cut theorem and the Edmonds-Karp refinement.

    • maximum flow — The maximum flow problem asks for the greatest possible amount that can be sent through a capacitated directed network from a source to a sink. It is equivalent to the minimum cut by the max-flow min-cut theorem and is solved by Ford–Fulkerson and later algorithms such as Edmonds–Karp, Dinic’s, push-relabel, and Orlin’s method.

• search algorithms
  • admissibility — Admissibility is the property that makes evidence or a legal contribution acceptable in court. In A* search, an admissible heuristic never overestimates the remaining distance to the goal.

Related Concepts and Applications

• algorithm design
  • in-place algorithms — In-place algorithms produce their output by overwriting the input rather than using significant extra storage. This class includes simple sorting methods such as bubble sort and selection sort.
• Selection algorithms
  • median of medians algorithm — The median of medians algorithm is a deterministic linear-time selection method. It groups elements into fives, finds the middle of each group, and recurses on those medians to choose a good pivot.

Sorting and Searching

Sorting Algorithms

• sorting algorithms — Sorting algorithms arrange data or a list into order, often by repeatedly swapping adjacent elements, partitioning around a pivot, or comparing digits in a fixed base. Common examples include bubble sort, insertion sort, quicksort, heap sort, heapsort, radix sort, counting sort, cocktail shaker sort, and the inefficient bogo sort. Some are stable sorts.

  • Bogo-sort — Bogo-sort is a deliberately terrible sorting algorithm that repeatedly checks random permutations until one happens to be sorted. It is famous as an example of an absurdly inefficient algorithm, with super-exponential average behavior and potentially unbounded runtime.

  • bogosort — Bogosort is a deliberately terrible sorting algorithm that repeatedly shuffles a list at random until it happens to be sorted. Its average behavior is absurdly inefficient, and its worst-case running time is effectively infinite because success is left to chance.

  • bubble sort — Bubble sort is a simple comparison sort that repeatedly swaps adjacent out-of-order elements. It has quadratic worst-case performance, with cocktail shaker sort as a common bidirectional variant and sink-based imagery in its alternate name.

  • bucket sort — Bucket sort is a linear-time sorting method that distributes data into buckets or intervals, sorts each bucket, and then concatenates the results. It is closely related to pigeonhole sort and is often used as part of radix sort.

  • heap sort — This sorting algorithm uses a heap, a binary tree in which each parent node is ordered above its children. It builds a partially ordered structure and then repeatedly removes the largest element to produce sorted output.

  • pancake sorting — Pancake sorting is the classic prefix-reversal problem of arranging a stack of pancakes with spatula flips so they end up ordered by size. Its burnt variant adds an orientation constraint, and the problem has attracted results from Bill Gates and David X. Cohen as well as work on bounds for prefix reversal.

  • runs — In sorting, runs are already ordered subsequences that algorithms like Timsort use to speed up merging. In compression, methods such as Burrows–Wheeler-based schemes work better when repeated substrings are longer and more numerous.

  • selection sort — Selection sort repeatedly finds the minimum element in the unsorted portion of a list and swaps it into place at the front. It is simple but quadratic in time, and variants like shaker sort or heap-based selection can change its practical behavior.

  • Shell sort — Shell sort is a comparison sorting algorithm that improves insertion sort by comparing and swapping elements separated by shrinking gaps. It is one of the most efficient n-squared sorts and is associated with Donald Knuth’s gap sequence.

  • stable sorting
    • stable — A stable sorting algorithm preserves the original order of equal elements. Merge sort is typically stable, while quicksort and heapsort are commonly used as examples of unstable sorts.

  • Timsort — Timsort is a hybrid sorting algorithm used in Python. It combines merge sort and insertion sort by identifying already ordered runs and extending them before merging.

  • bin sort — Bin sort is a linear-time sorting method for keys drawn from a small fixed range. It works by placing each item into the bin corresponding to its key and then collecting the bins in order.

• Comparison-sort lower bound — any comparison-based sorting algorithm requires Ω(n log n) comparisons in the worst case; information-theoretic argument: n! possible orderings require at least log₂(n!) ≈ n log n comparisons to distinguish; applies to mergesort, heapsort, quicksort; non-comparison sorts (radix, counting) bypass this by exploiting integer structure.

• Stable sort — equal elements maintain their original relative order; merge sort and insertion sort are stable; quicksort and heap sort typically are not.

• Lower bound — comparison-based sorting cannot beat O(n log n) in the worst case (information-theoretic argument: ⌈log₂(n!)⌉ comparisons required to distinguish all n! orderings, by Stirling’s approximation Θ(n log n)); non-comparison sorts (counting, radix) bypass this with integer keys.

• Quicksort — divide-and-conquer; choose a pivot, partition into smaller/larger, recurse; average O(n log n), worst O(n²) on sorted input with bad pivot choice; in-place (O(log n) stack); Hoare’s original partition (1959); introsort (C++ STL) switches to heapsort after recursion depth exceeds 2 log n. Many implementations use Hoare’s original partition scheme (1959). Introsort, used in the C++ STL, switches to heapsort when recursion depth exceeds 2 log n.
  • Quicksort pivot strategies — first element (bad on sorted input), random pivot, median-of-three; introsort (used in C++ STL) switches to heap sort to avoid worst case.

• Merge sort — guaranteed O(n log n) all cases; stable; O(n) auxiliary space; recursive split-and-merge; preferred for linked lists; John von Neumann credited (1945); basis of Timsort (Python/Java default), which exploits natural runs in data. It was later adapted into parallel and network-based variants such as Batcher’s odd-even mergesort.

• Heapsort — in-place O(n log n) sort; build a max-heap in O(n), then repeatedly extract maximum; not stable; constant O(1) space advantage over merge sort; poor cache performance compared to quicksort.

• Counting sort — integer keys only; create a frequency array of size k; O(n + k) time and space; stable; efficient when k = O(n).

• Radix sort — sort by individual digits/characters from least significant to most significant (LSD) or reverse (MSD); O(nk) where k is number of digits; uses counting sort as subroutine; stable. A non-comparative sorting method that processes keys digit by digit, usually in least-significant-digit (LSD) or most-significant-digit (MSD) order. It can run in near-linear time for fixed-length keys and often uses stable bucket sorts or counting sort as a subroutine.

Searching

• Linear search — O(n); works on unsorted data.

• Binary search — O(log n); requires sorted array; halves the search space each step; classic source of off-by-one errors (use mid = lo + (hi - lo) / 2 to avoid overflow). It repeatedly compares the target to the middle element and is also a standard method in search trees and tools like git bisect.

• Interpolation search — O(log log n) average for uniformly distributed sorted data; O(n) worst case.

• search algorithms

  • A* algorithm — A* is a letter-named pathfinding algorithm that combines a heuristic estimate with the exact cost already traveled. It reduces to Dijkstra’s algorithm when the heuristic is zero and is widely used for finding shortest routes in graphs and maps.

  • pruning — Pruning is the technique of cutting away unnecessary branches in search procedures and decision trees. Its examples include alpha-beta pruning in minimax, beam search, and pruning methods used in neural networks and approximation algorithms.

  • search algorithm — Search algorithms are procedures for locating a desired item, value, or vertex in a data structure or collection. Examples include binary search on sorted lists, breadth-first search and depth-first search for graphs, and Grover’s algorithm as a quantum search algorithm for unstructured search. They are central to databases, web search engines, and graph traversal.
    • searching algorithm — A searching algorithm is a method for locating a desired item, whether by binary search, depth-first search, or breadth-first search. Its quantum version includes Grover’s algorithm, which achieves square-root time for an unstructured search.
  • Sequential search — Sequential search scans a list from the first element onward until the target is found or the list ends. It is the simplest linear method for searching unsorted data.

String Algorithms

• string algorithms

  • string searching — String searching, or string matching, is the task of finding a pattern within text. Algorithms such as KMP, Rabin-Karp, Boyer-Moore, and bitap are standard approaches, and the problem is also used in plagiarism detection and approximate matching.

  • String Matching or Pattern Matching — String matching, or pattern matching, asks how to find one sequence inside another efficiently. Algorithms such as Knuth-Morris-Pratt and Boyer-Moore are standard solutions to this problem.

  • Knuth-Morris-Pratt (KMP) — string search in O(n + m) time (n = text length, m = pattern length); precomputes a failure function (partial match table) encoding the longest proper prefix that is also a suffix; avoids re-examining text characters; Donald Knuth, James Morris, Vaughan Pratt (1977).

  • Rabin-Karp algorithm — string search using rolling hashes; O(n + m) expected, O(nm) worst case (hash collisions); particularly useful for multi-pattern search (detecting plagiarism); Michael Rabin and Richard Karp (1987).

  • Boyer-Moore algorithm — right-to-left pattern comparison with bad-character and good-suffix heuristics; O(n/m) best case (sublinear); common in practical text editors and grep.

  • Z-algorithm — linear O(n + m) string matching; builds Z-array where Z[i] = length of longest substring starting at position i that is also a prefix of the string; alternative to KMP.

• String processing
  • prefixes — A prefix is a substring that begins at the start of another string. Prefixes appear in algorithms such as KMP and Boyer-Moore, and in fields like notation and CIDR addressing.
    • hyper — Hyper- is the prefix behind terms such as hypertext, hypercard, hyperjacking, and hyperstition. It also appears in cultural theory through Baudrillard’s hyperreal and in computing through the “Hyper” software family.
• symbols
  • dollar sign — The dollar sign is the symbol appended as a terminator in the Burrows–Wheeler transform and used as a marker for reversibility in the LF mapping. It also appears in LaTeX for inline math and in bash for variable names. In spreadsheet formulas, the dollar sign marks absolute cell references that stay fixed when a formula is moved.
• strings — A data type consisting of sequences of characters used to store and manipulate text in programming languages. Clues mention concatenation, regular expressions, null termination, and algorithms like KMP and Rabin-Karp that search within them.

Randomization, Approximation, and Numerical Algorithms

Extend exact algorithm design to randomized methods, approximation, and numerical transforms.

• Approximation algorithms — polynomial-time algorithms for NP-hard optimization problems guaranteed to return a solution within a factor of optimal; e.g., 2-approximation for vertex cover; greedy (1 - 1/e)-approximation for set cover; PTAS = polynomial-time approximation scheme.

• Randomized algorithms — use random choices; Las Vegas algorithms always correct (expected fast, e.g., randomized quicksort); Monte Carlo algorithms always fast (may be wrong with small probability, e.g., Miller-Rabin primality test).

  • Las Vegas algorithm — A Las Vegas algorithm is a randomized algorithm that always returns a correct answer. Its runtime is probabilistic, unlike Monte Carlo methods, which trade correctness for bounded time.

  • Monte Carlo algorithm — A Monte Carlo algorithm is a randomized computational method that uses probabilistic sampling. It may trade guaranteed correctness for speed or a probabilistic runtime, as in methods like Metropolis and polynomial identity testing.

  • randomized — Randomized algorithms rely on probabilistic choices or random input, whether in quicksort pivots, Las Vegas methods, or Monte Carlo-style processes. The clues also connect this property to BPP, differential privacy, and experimental design.

• Fast Fourier Transform (FFT) — computes the Discrete Fourier Transform in O(n log n) instead of O(n²); Cooley-Tukey algorithm (1965); key to polynomial multiplication, signal processing, image compression (JPEG); used to multiply large integers.

• Pseudorandom number generation — Pseudorandom number generation is the computer creation of values that imitate randomness, usually produced from a seed, for uses such as simulations, games of chance, and security systems. Common methods include linear congruential generators, Mersenne Twister, Blum Blum Shub, and xorshift. Cryptographic variants are judged by tests such as the next-bit test.

• pseudorandom number generators
  • Mersenne twister — The Mersenne twister is a fast pseudorandom number generator widely used in simulation and software, especially video games. Its name refers to the very long period 2^19937 - 1.
• Randomness

  • pseudorandom number generator — A pseudorandom number generator is an algorithm that produces numbers with statistical properties resembling randomness. Examples include the Mersenne Twister and Blum Blum Shub, which are seeded to simulate dice rolls, coin flips, and other chance events.

  • random number generation — Random number generation is the process of producing unpredictable numbers, usually by hardware entropy sources or by pseudorandom algorithms seeded from an initial value. It underlies Monte Carlo methods and is the subject of classic generators such as the Mersenne Twister and Blum Blum Shub.

    • pseudorandom numbers — Pseudorandom numbers are values generated by an algorithm to imitate random output. They are used in Monte Carlo methods and can be produced by generators such as the Mersenne Twister.
• Fourier transforms
  • fast Fourier transform — The fast Fourier transform is an algorithm for computing the discrete Fourier transform efficiently, reducing the cost from quadratic time to roughly n log n; it also computes the inverse discrete Fourier transform. It was developed by Cooley and Tukey and is widely used in digital signal processing. Cooley–Tukey is the classic radix-2 method associated with its O(n log n) speedup, and related FFT families include Bluestein’s prime-size method and split-radix variants for special input lengths.
    • James W. Cooley and John W. Tukey — James W. Cooley and John W. Tukey are the computer scientists credited with the 1965 fast Fourier transform algorithm. Their method reduces the cost of discrete Fourier transforms from quadratic time to roughly n log n time.
• Matrix multiplication algorithms

  • Coppersmith-Winograd algorithm — The Coppersmith-Winograd algorithm is a matrix-multiplication method that improved on Strassen-style approaches. Its best-known significance is that it achieved the fastest asymptotic runtime for multiplying square matrices for a time, with later work improving the exponent slightly.

  • Strassen’s algorithm — Strassen’s algorithm is a faster matrix-multiplication method that improves on the naive cubic-time approach. By replacing one multiplication with several additions in each recursive step, it achieves a better asymptotic runtime.

Complexity and Computability

Distinguish efficiency questions from what is computable in principle.

Complexity Theory

Big-O Notation

• Big-O O(f) — upper bound on growth rate; O(g) means the function grows no faster than g asymptotically; constant factors dropped.

• Big-Omega Ω(f) — lower bound; Big-Theta Θ(f) — tight bound (both upper and lower).

• Common complexities — O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!).

• Amortized analysis — averages cost over a sequence of operations; dynamic array append is O(1) amortized despite occasional O(n) copies. It is commonly developed through aggregate, accounting, and potential analysis.

• Space complexity — memory used as a function of input size; important alongside time complexity; O(1) in-place (heapsort), O(log n) stack (quicksort), O(n) auxiliary (mergesort).
  • Savitch’s Theorem — Savitch’s theorem states that nondeterministic space can be simulated deterministically with only a quadratic increase in space. A standard corollary is that PSPACE equals NPSPACE.
• algorithm analysis
  • asymptotic complexity
    • n log n — n log n is the quasilinear running time associated with many comparison-based sorting algorithms and FFT-style divide-and-conquer methods. Mergesort, quicksort average case, and the Cooley-Tukey FFT are standard clues for this growth rate.
  • big-O notation
    • O — The letter O can name the oxygen element, the O horizon in soil, and the big-O notation used to describe algorithmic growth. It also marks the universal-donor blood type O negative, which lacks A and B antigens.
  • complexity — Complexity is a broad term covering the resources needed to describe or solve a problem, including time, space, and Kolmogorov-style description length. It appears in complexity theory and in measures of algorithmic and scientific systems, from big-O analysis to Chaitin’s incompressibility ideas.
• Computer science
  • Time complexity
    • big O of n — Big O of n is linear time, the complexity class in which an algorithm examines or processes each element once. Clues often use sequential search or binary-heap construction as examples of this runtime.
• asymptotic notation
  • big omega — Big omega denotes an asymptotic lower bound in algorithm analysis. The same Greek letter also names Chaitin’s constant in computability theory.
• Algorithmic complexity
  • O(n log n) — O(n log n) is a standard time complexity for many efficient comparison sorts, including merge sort and heap sort. It is also the average-case lower bound for comparison-based sorting and appears in algorithms such as FFT-related methods and Barnes-Hut approximations.
• time complexity

  • exponential time — Exponential time describes runtime that grows like a constant raised to n, such as 2^n. It is the class of growth associated with many brute-force algorithms, including dynamic-programming solutions to some instances of traveling salesman.

  • O (n^2) — O(n^2) is the quadratic time complexity that often appears in simple sorting algorithms such as bubble sort and selection sort. It is the worst-case running time of naive quicksort on already ordered input.

Complexity Classes

• complexity classes
  • EXPTIME — EXPTIME is the class of decision problems solvable by a deterministic Turing machine in exponential time. It contains problems such as generalized chess and Go, and the time hierarchy theorem shows it strictly contains P.
• Complexity Classes and Resource Bounds

  • P — decision problems solvable in polynomial time by a deterministic Turing machine; considered “tractable.” It is treated as the class of tractable problems, and it includes tasks such as linear programming and the greatest common divisor problem. A recurring question is whether P equals NP.

  • NP (Nondeterministic Polynomial time) — decision problems whose solutions can be verified in polynomial time; every problem in P is in NP.

  • co-NP — complement class of NP; problems where “no” instances can be verified in polynomial time; graph non-isomorphism is in co-NP.

  • PSPACE — problems solvable in polynomial space; PSPACE ⊇ NP; PSPACE-complete problems include TQBF. It contains TQBF and is equal to its nondeterministic version by Savitch’s theorem.

  • EXP / EXPTIME — problems solvable in exponential time 2^{poly(n)}; strictly contains PSPACE by the time-hierarchy theorem; chess on an n×n board is EXPTIME-complete.

  • #P (sharp-P) — counting complexity class; asks how many solutions exist (not just whether one exists); #P-hard problems include counting satisfying assignments to a 3-CNF formula; proved by Valiant (1979).

  • Time-hierarchy theorem — more time strictly enlarges the class of solvable problems; proves P ≠ EXPTIME and similar separations; does NOT prove P ≠ NP.

  • Space complexity classes — L (logspace, deterministic) and NL (nondeterministic logspace) sit below P; PSPACE contains NP and co-NP; EXPTIME contains PSPACE; hierarchy: L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME.

• Reductions, Completeness, and Open Questions

  • NP-complete — hardest problems in NP; a problem is NP-complete if (1) it is in NP and (2) every NP problem reduces to it in polynomial time; if any NP-complete problem is in P, then P = NP. Canonical examples include satisfiability, clique, vertex cover, subset sum, Hamiltonian cycle, subgraph isomorphism, and traveling salesman.

  • NP-hard — at least as hard as the hardest NP problems; need not be in NP (may not be decidable); optimization versions of NP-complete problems are NP-hard. Classic examples include optimization versions of NP-complete problems such as 0-1 integer programming and the traveling salesman problem. A nondeterministic polynomial-hard problem is at least as hard as every problem in NP under polynomial-time reduction.

  • Classic NP-complete problems — Boolean satisfiability (SAT, Cook’s theorem 1971), 3-SAT, vertex cover, clique, independent set, subset sum, 0/1 knapsack, Hamiltonian cycle, graph coloring (k ≥ 3), traveling salesman (decision form).

  • P vs NP — whether P = NP is the most famous open problem in computer science; a $1 million Millennium Prize Problem; most researchers believe P ≠ NP. It asks whether every problem whose solution can be checked in polynomial time can also be solved in polynomial time; it is closely tied to the existence of one-way functions.

  • NP-hardness reduction technique — to prove problem X is NP-hard, reduce a known NP-hard problem (often 3-SAT) to X in polynomial time; if you can solve X, you can solve 3-SAT; the direction of reduction matters.

  • Cook-Levin theorem — SAT (Boolean satisfiability) is NP-complete; proven independently by Stephen Cook (1971) and Leonid Levin; the first problem shown to be NP-complete; established the foundation for NP-completeness theory. Its proof typically encodes a polynomial-time nondeterministic Turing machine computation in a tableau.

  • SAT and 3-SAT — SAT asks whether a Boolean formula has a satisfying assignment; 3-SAT restricts to CNF clauses of exactly 3 literals; 3-SAT is NP-complete and serves as the standard starting point for NP-hardness reductions; 2-SAT is in P (solvable via SCCs).

  • Polynomial-time reduction — transformation from problem A to problem B computable in polynomial time; if A reduces to B and B is in P, then A is in P; if A is NP-hard and reduces to B, then B is NP-hard; the mechanism of NP-completeness proofs.

  • Oracle / relativization — a technique attaching a black-box oracle subroutine to a TM; Baker-Gill-Solovay (1975) showed there exist oracles A and B with P^A = NP^A and P^B ≠ NP^B; this means P vs NP cannot be resolved by relativizing proof techniques alone.

  • computational complexity

    • Big O — Big O notation is the asymptotic system computer scientists use to describe how an algorithm’s runtime or memory usage grows, usually by giving an upper bound. It is part of Bachmann-Landau notation and is used to classify growth rates such as quadratic performance.

    • NP — NP is the complexity class of decision problems whose proposed yes-certificates can be verified in polynomial time by a deterministic Turing machine. Equivalently, it is the class of decision problems solvable in polynomial time by a nondeterministic Turing machine. It is central to the P versus NP problem and includes standard NP-complete problems such as SAT, Clique, and Vertex Cover; Cook’s theorem showed SAT to be NP-complete. NP is also commonly compared with randomized complexity classes such as BPP.

    • P = NP — P versus NP is the central open problem asking whether every problem whose solution can be checked in polynomial time can also be solved in polynomial time. It is tied to the Cook–Levin theorem, Ladner’s theorem, and PCP-based hardness results, and it appears in complexity-theoretic world-building such as Pessiland and Heuristica.

    • polynomial time — Polynomial time is the complexity class of problems solvable in time bounded by a polynomial in the input size. It is the standard “fast” class behind P, and many clues contrast it with exponential time, NP, or notions like quadratic and cubic running time.

    • Decision problems — Decision problems are computational problems with only two possible answers, usually yes or no. In complexity theory, they are contrasted with optimization problems, which seek the best solution rather than a binary decision.

    • NP-complete problems
      • 3-SAT — 3-SAT asks whether a Boolean formula in conjunctive normal form with clauses of at most three literals can be satisfied. It became famous through the Cook-Levin theorem and remains one of Karp’s canonical NP-complete problems.
    • Oracle — In computational complexity, an oracle is a black-box subroutine attached to a Turing machine so it can query a decision problem in a single step. Oracles are used in relativization arguments.
      • Larry Ellison — Larry Ellison is the co-founder and longtime chief executive of Oracle, the database software company. He is often clued through his wealth, aggressive business style, and occasional takeover talk involving Apple.
    • quadratic time complexity
      • big O of n squared — Big O of n squared is the quadratic time complexity associated with insertion sort and bubble sort. It is also the worst-case behavior one tries to avoid in quicksort by choosing good pivots or randomizing input.
    • satisfiability
      • Boolean satisfiability problem — The Boolean satisfiability problem (SAT) asks whether a Boolean formula or expression can be made true by some assignment of truth values to its variables, often after conversion to conjunctive normal form. It was shown NP-complete by the Cook-Levin theorem and is a canonical NP-complete problem underlying reductions from NP problems. Common approaches include DPLL-style backtracking, CDCL solvers such as Chaff, and related reductions.
    • Satisfiability Problem — The satisfiability problem asks whether a Boolean formula can be made true by assigning truth values to its variables. It is a classic NP problem in computational complexity.
  • complexity theory
    • graph isomorphism
      • graph isomorphism problem — The graph isomorphism problem asks whether two graphs have the same structure up to relabeling of vertices. It is a famous problem in complexity theory because it is known to lie in NP, has resisted classification as P-complete or NP-complete, and was given a quasipolynomial-time algorithm by László Babai.
    • interactive proofs
      • interactive proof — An interactive proof is a protocol in which a prover tries to convince a verifier that a statement is true through a sequence of messages. These systems are associated with public-coin Arthur-Merlin protocols, zero-knowledge proofs, and the complexity class IP.

    • P and NP — P and NP are the central complexity classes of computational theory, with NP containing problems such as SAT by the Cook-Levin theorem. The equality of P and NP is one of the major open problems in complexity theory.

    • P versus NP problem — P versus NP asks whether every problem whose solution can be verified in polynomial time can also be solved in polynomial time. It is a Millennium Prize Problem, one of the most famous open problems in theoretical computer science, and underlies the difficulty of problems such as the traveling salesman problem.

    • Unique Games Conjecture — The Unique Games Conjecture is a complexity-theory conjecture proposed by Subhash Khot in 2002. It concerns approximation hardness for optimization problems and is often phrased in terms of a two-prover one-round promise game.
• Theory of computation
  • computational complexity theory — Computational complexity theory studies the inherent difficulty of computational problems by classifying them into groups such as P and NP. It is associated with results like the Cook-Levin theorem, Savitch’s theorem, and the use of oracles, padding, and hierarchy arguments.
    • computational complexity classes — Computational complexity classes are sets such as P and NP that group problems by their inherent difficulty. They organize decision problems, and some classes contain complete problems under efficient reductions.
  • recursively enumerable sets
    • recursively enumerable — Recursively enumerable sets are those whose members can be listed by an algorithm that may never halt, and they correspond to the type-0 languages of the Chomsky hierarchy.

Computability and Automata

• Computability and Undecidability
  • Turing machine — abstract model of computation: infinite tape, read/write head, state transitions; defines what is computable. Alan Turing’s 1936 model uses a finite state table to govern its transitions. It is named for him, and the halting problem for arbitrary Turing machines is undecidable. Related topics include universal, multitape, alternating, and oracle variants, Rice’s theorem, Church’s thesis, and its equivalence to other formal models such as unrestricted grammars.
    • Universal Turing machine — a TM that simulates any other TM given its description as input; the theoretical basis for stored-program computers; proves that a single machine can compute anything computable.

  • Church-Turing thesis — any function computable by an algorithm can be computed by a Turing machine; a thesis, not a theorem. It states that the intuitive notion of an algorithm is captured by Turing-machine computability and is a foundational claim in computability theory. It is also called Church’s thesis.

  • Halting problem — given a program and input, does it halt? Proven undecidable by Alan Turing (1936) via diagonalization; no algorithm can solve it for all inputs. It is often stated for Turing machines and is a standard starting point for results such as Rice’s theorem and reductions from Post’s correspondence problem.

  • Rice’s theorem — all non-trivial semantic properties of programs are undecidable; generalizes the halting problem. It says that any nontrivial semantic property of a program or recursively enumerable language is undecidable, and it applies to programs recognized by Turing machines.

  • Decidable vs recognizable — a decidable language has a TM that always halts; a recognizable (recursively enumerable) language has a TM that halts on “yes” instances but may loop on “no.”

  • Lambda calculus — formal system for expressing computation via function abstraction (λx.body) and application; Alonzo Church (1930s); equivalent in power to Turing machines (Church-Turing thesis); theoretical basis of functional programming; beta reduction is the computation rule. It is commonly described in terms of variables, abstractions, and applications. Related ideas include the Y combinator, the Curry–Howard correspondence, typed systems such as System F, and combinatory logic.

    • combinators — In lambda calculus, combinators are higher-order functions with no free variables. Bird names like the Y combinator and the SKI system make them a standard clue in theoretical computer science, where they can encode recursion and universal computation.

    • untyped lambda calculus — The untyped lambda calculus is Alonzo Church’s minimalist formal system for function definition and application. It uses alpha- and beta-reduction, forms the basis for Church numerals, and strongly influenced functional programming.

  • Undecidability examples — halting problem; Post correspondence problem; whether a CFG generates all strings; whether two CFGs are equivalent; whether a program has a bug (Rice’s theorem); all proven by reduction from the halting problem.
    • Post correspondence problem (PCP) — undecidable problem: given tiles with two strings, does some sequence make both sides equal? Standard target for undecidability reductions; Emil Post (1946).

  • Diagonalization — proof technique used by Turing (halting problem) and Cantor (uncountability of reals); construct an object that differs from every element of an enumerated list at the diagonal position; key tool in computability and complexity.

  • Entscheidungsproblem — Hilbert’s “decision problem” asking for an algorithm to determine the truth of any mathematical statement; proven unsolvable by Church and Turing (1936), giving birth to computability theory. Hilbert also framed it as asking whether there is an algorithm that can decide whether a formula is a theorem, or provable from a given formal system.

  • computability theory

    • busy beaver function — The Busy Beaver function is an uncomputable function defined for Turing machines with a fixed number of states. It grows faster than any computable function and is classically discussed through the maximum number of 1s or steps that an n-state machine can produce before halting.

    • computable functions
      • computable — A function is computable if some algorithm or Turing machine can produce its outputs, and such functions are also described as recursive or effectively calculable. The lambda calculus gives a formal way to describe computable functions, and computability theory also underlies decidability and reverse mathematics.

    • halting — The halting property is the ability of a computation or program to terminate rather than run forever. It is central to the halting problem, one of the first famous undecidable problems in computability theory. Clues often mention infinite loops, total correctness, the busy beaver function, and Chaitin’s constant.

    • hypercomputation — Hypercomputation is the hypothetical computation of functions beyond the Turing-computable class. The term is also discussed as super-Turing computation or as an infinite-time Turing machine model.

    • oracle machine — An oracle machine is a theoretical Turing machine equipped with a black box that can answer queries about a specified problem instantly. Oracle machines appear in discussions of relativization, the halting problem, and Grover-style quantum search oracles.

    • recursive functions
      • general — General recursive functions are the class of functions computable by the lambda calculus and by Turing machines. In logic and computation, the term can also appear in prompts about general titles or military ranks, but the core idea is computability in the sense of Church’s thesis. The set is often contrasted with specific or partial recursive functions.

    • Stephen Kleene — Stephen Kleene was a foundational logician in computability theory and formal languages, and he co-formulated Church’s lambda calculus. His name appears in the Kleene star on regular expressions and in recursion theorems about fixed points of computable functions.

    • Turing machines
      • Turing machine — A Turing machine is a theoretical model of computation with a finite control, a read-write head, and an infinite tape. Alan Turing introduced the idea in work related to the Entscheidungsproblem. Turing machines are central to computability theory and underpin results such as the halting problem and Rice’s theorem, as well as the Church-Turing thesis and universal computation.

    • Turing-completeness — Turing-completeness is the property of a system that can simulate a Turing machine and therefore compute any computable function. It is a standard clue for programming languages, cellular automata, and even joke examples like Brainfuck or PowerPoint.

    • undecidable — An undecidable problem is one for which no algorithm can always give a correct yes-or-no answer. Famous examples include the halting problem, the Post correspondence problem, and other problems shown impossible to solve by a Turing machine.
  • Computational theory
    • Computability
      • nondeterminism — Nondeterminism is the property of a computational model whose choices can be explored by constructions such as the powerset construction and by results like Savitch’s theorem. It is the defining “N” in NP and appears in finite automata, pushdown automata, and complexity classes such as NP.
        • non-deterministic — A non-deterministic machine can have multiple possible transitions from a given state and may accept if any path reaches an accept state. In complexity theory, the “N” in NP refers to this property, contrasting with deterministic computation.
  • undecidable problems
    • Post correspondence problem — The Post correspondence problem asks whether a sequence of paired strings can be arranged so the top and bottom strings match. It is a classic undecidable problem associated with Emil Post and commonly used in reduction proofs.
• Automata, Grammars, and Formal Languages
  • Finite automaton (DFA/NFA) — models recognizing regular languages; DFA and NFA accept the same class (regular languages); both weaker than pushdown automata.
    • NFA (Nondeterministic Finite Automaton) — finite automaton that can be in multiple states simultaneously (or take epsilon transitions); accepts if any branch accepts; equivalent in expressive power to DFA; exponential blowup possible in determinization (subset construction).

  • Context-free grammar (CFG) — generates context-free languages (e.g., balanced parentheses); recognized by pushdown automata; relevant to parsing programming languages.

  • Chomsky hierarchy — regular < context-free < context-sensitive < recursively enumerable; each class strictly contains the previous; Noam Chomsky formalized this (1956).

    • context-sensitive grammar — A context-sensitive grammar is a Type-1 grammar in the Chomsky hierarchy and is stronger than a context-free grammar. These grammars correspond to linear bounded automata and can generate languages with equal numbers of multiple symbols, such as strings of A’s, B’s, and C’s in matched counts.

    • context-sensitive languages — Context-sensitive languages are the Type-1 languages of the Chomsky hierarchy, recognized by linear bounded automata. They are more powerful than context-free languages and are closed under complement.

  • Pushdown automaton (PDA) — finite automaton augmented with a stack; recognizes context-free languages; nondeterministic PDAs = deterministic PDAs in power (unlike finite automata).

  • Regular expressions — formal notation for regular languages; operators: concatenation, union (

    ), Kleene star (*); every regex corresponds to an NFA by Thompson’s construction; used in text processing, compilers (lexical analysis). Also used as pattern-matching notation in tools such as grep, awk, and Perl for text search and replacement.

  • Pumping lemma — necessary condition for a language to be regular (or context-free); used to prove languages are NOT regular; for regular: if

    w

    ≥ pumping length p, then w can be split so that the middle part can be pumped (repeated) and stay in the language.

  • Context-sensitive language — Chomsky hierarchy level 2; recognized by linear bounded automata; more expressive than context-free; example: {aⁿbⁿcⁿ}.

  • Kleene star — closure operation in formal language theory: L* = all finite concatenations of strings from L, including the empty string ε; fundamental in regular expressions and automata theory; Stephen Kleene (1956). It is distinct from Kleene plus, which requires one or more repetitions.

  • formal grammars
    • Backus-Naur form — Backus-Naur form is a notation for describing context-free grammars with productions, nonterminals, and symbols like ::= and angle brackets. It was developed for describing ALGOL-style languages and later extended into forms such as EBNF and ABNF. The name honors John Backus and Peter Naur.
  • formal language theory

    • context-free languages — Context-free languages are the class of formal languages accepted by pushdown automata and generated by context-free grammars. Typical examples include balanced parentheses and palindromes, and the class sits below the languages accepted by Turing machines.

    • formal languages — Formal languages are sets of strings over an alphabet governed by explicit rules. They include regular languages and are studied through automata theory, grammars, and decision problems.

      • context-free grammar — A context-free grammar is a type-2 formal grammar whose productions have a single nonterminal on the left-hand side and whose languages are studied with pumping lemmas and parsers. It is commonly written in Backus-Naur form and underlies many parsing systems for programming languages.

      • context-free language — A context-free language is generated by a context-free grammar, such as one written in Backus-Naur Form, and is exactly the class of languages recognized by pushdown automata. It can be put into normal forms such as Chomsky normal form or Greibach normal form, and the CYK algorithm gives a polynomial-time recognition method.

      • empty string — The empty string is the unique string of length zero, often written epsilon in formal-language theory. In Chomsky normal form, productions are not allowed to generate it except in restricted cases.

      • regular languages — Regular languages are the formal languages recognized by finite automata and describable by regular expressions. They are a Type-3 class in the Chomsky hierarchy and are closed under standard operations such as union, concatenation, and Kleene star.

    • regular language
      • Regular — A regular language is the simplest kind of formal language, equivalent to what finite automata recognize and what regular expressions describe. The word also describes polygons with equal sides and angles, matrices with inverses, and the well-behaved points of differential equations.
  • automata theory

    • pushdown automaton — A pushdown automaton is a finite automaton equipped with a stack, often described as an infinite stack. It recognizes context-free languages, and every context-free grammar can be converted into one.

    • automata — Automata are self-operating machines, from courtly marvels like mechanical birds and thrones to the abstract machines studied in formal language theory.

    • cellular automata — Cellular automata are discrete dynamical systems in which grid cells update by local rules based on neighboring states. Conway’s Game of Life is the classic example, and the field also includes lattice-gas models and other discrete-space, discrete-time systems.
      • Cellular automaton — A cellular automaton is a discrete computational model in which cells on a grid update through repeated generations according to fixed rules. Conway’s Game of Life is the classic example, and John von Neumann helped develop the field.

    • Finite Automaton — A finite automaton is an abstract model of computation with a finite set of states, a start state, transition rules, and accepting states. It recognizes a regular language; regular languages are exactly the languages accepted by finite automata. Finite-state automata come in deterministic and nondeterministic forms, and the nondeterministic version can be converted by subset construction. They may be depicted as directed graphs or finite-state machines and are less powerful than pushdown automata.

    • finite state machines — Finite state machines are computational models with a finite number of states and labeled transitions between them. Deterministic and nondeterministic finite automata are standard forms, and Mealy and Moore machines are common design variants.

      • Deterministic finite automaton — A deterministic finite automaton is a finite-state machine that reads input symbols one at a time and follows exactly one transition for each symbol from each state. It recognizes exactly the regular languages and is used to accept or reject strings in a regular language. Standard results about it include the powerset construction, Hopcroft minimization, and the Myhill-Nerode theorem.

      • Finite State Machine — A finite state machine is a model of computation with a set of states, an initial state, and transition rules on input symbols. It has a limited number of internal states and is used as an acceptor, recognizer, or transducer in the study of regular languages. Deterministic and nondeterministic versions are standard, with Mealy and Moore machines as common variants; probabilistic versions also appear in models such as Markov chains.

      • Mealy machine and Moore machine — A Mealy machine and a Moore machine are the two most common types of finite state machine. They differ in whether outputs depend directly on the current input, the current state, or both.

      • Moore machine — A Moore machine is a finite-state automaton whose outputs depend only on the current state, not directly on the input. It is the state-output counterpart to a deterministic machine and is often contrasted with a Mealy machine.

    • nondeterministic — Nondeterministic describes systems, automata, or Turing machines that can make multiple possible choices from a given state. The term is central to automata theory and complexity theory, including the definition of NP and the powerset construction that converts such automata into deterministic ones.

    • states — States are the configurations a finite automaton can occupy, such as Moore and Mealy machine states or the nodes in a DFA. The word also names political entities like the US states under the Articles of Confederation and the sovereign states of international relations.
  • determinism
    • deterministic — Deterministic means a process or algorithm has a single predictable outcome rather than randomness. In computing it describes finite automata and parsers whose next step is uniquely determined, and in number theory it is a key feature of the AKS primality test.
  • Strings — Strings are data types used to store text, often represented as arrays of characters or sequences of characters in programming languages. They are matched with regular expressions, can be null-terminated in C, and can be concatenated or printed in many languages.
• John Conway
  • Conway’s Game of Life — John Conway’s zero-player cellular automaton from 1970, played on an infinite grid where cells live or die according to simple birth-and-survival rules based on neighboring cells. It is famous for patterns such as gliders, glider guns, spaceships, oscillators, and methuselahs, and for its Turing-complete behavior and role as a standard example of emergent complexity.
• Strings
  • concatenation — Concatenation is the operation of joining strings end to end, such as by using plus signs in common programming languages. It combines separate text objects into a single longer string.
    • string concatenation — String concatenation is the operation of joining strings end to end, often represented by plus signs or other language-specific operators. In automata and formal-language settings, it corresponds to linking one machine’s accepting states to the start of the next, and it interacts with the Kleene star on regular expressions.

Information Theory and Coding

• Audio codecs
  • MP3 — MP3 is the common lossy digital audio format formally known as MPEG-1 Audio Layer III, short for MPEG Audio Layer 3. It became a standard for compressed music files and portable players such as the Rio, with psychoacoustic encoding reducing imperceptible sound data; it was also central to the music industry’s fight over online file sharing.
• Character encodings
  • ASCII — ASCII stands for the American Standard Code for Information Interchange. It is a 7-bit character encoding standard that maps numbers 0 through 127 to letters, numbers, punctuation, symbols, and control codes, and is used as a common text format for computer communication. It is the basis for fixed-width text art and early internet culture such as ASCII art and telnet displays. Its extended form adds more symbols beyond the original 128-character set.

• compression — Compression is the process of reducing the size of data, with both lossless methods like Huffman and Lempel-Ziv and lossy methods used for formats such as JPEG and MP3. It often uses coding schemes that make frequent symbols shorter and can involve dictionary or transform-based algorithms.

• data compression — The process of reducing the storage size of data, either losslessly or with information discarded in lossy form. It encodes data so it uses less space; standard methods include Huffman coding, Lempel-Ziv methods, Rice-Golomb coding, and DEFLATE. ZIP and JPEG are standard examples.

  • Burrows–Wheeler transform — The Burrows–Wheeler transform is a reversible data-transformation used in compression that sorts rotations of a string and outputs the last column. It is closely tied to suffix arrays and underlies block-sorting compressors such as bzip2.

  • Huffman codes — Huffman codes are variable-length binary codes that assign shorter strings to more frequent symbols. They are built from a frequency-weighted tree and are known for the prefix-free property used in data compression.

  • Lempel-Ziv — Lempel-Ziv is a family of data-compression algorithms that build dictionaries of repeated patterns to shrink information. The name is often paired with Huffman coding and ZIP-style lossless compression in quizbowl clues.

  • Lempel-Ziv algorithm — The Lempel-Ziv algorithm is a family of dictionary-based compression methods used in formats such as GIF and PNG-related schemes. Its variants include LZ77, LZ78, and Lempel-Ziv-Welch, which use previously seen strings to encode data efficiently.

  • lossless compression — Lossless compression is fully reversible data compression that preserves all original information. Formats such as PNG, FLAC, and ZIP use it, while JPEG and MP3 do not.

  • lossless data compression — Lossless data compression reduces the number of bits needed to represent information without discarding anything essential. Techniques such as entropy coding and transforms like Burrows-Wheeler are used in formats such as PNG.

• digital audio
  • audio — Audio is data representing sound, speech, or music, often digitized by pulse-code modulation and stored in formats like WAV or MP3. Its processing and compression commonly involve sampling rates such as 44.1 kHz, along with codecs like FLAC, Vorbis, and AAC.
• Digital technology
  • digital — Digital is the adjective behind digital humanities, digital anthropology, digital natives, and the digital divide. It also describes modern information formats and control signals that replace analog transmission.
• Information theory

  • Claude Shannon — Claude Shannon founded information theory and helped define entropy, channel capacity, and the limits of error-free communication. His clues may mention the noisy-channel coding theorem, the Shannon-Nyquist sampling theorem, or whimsical inventions like the Ultimate Machine.

  • Coding theory

    • prefix codes — Prefix codes are coding systems in which no codeword begins another codeword, so each message has a unique interpretation. They appear in data-compression schemes such as Fibonacci coding and Huffman coding, and can be tested using the Kraft-McMillan inequality.
• compression algorithms
  • Huffman encoding — Huffman encoding is a greedy compression method that constructs a binary tree from character frequencies. By placing common symbols closer to the root, it minimizes the number of bits needed to represent text.

Quantum Computing and Quantum Complexity

Compare quantum gates and circuits with classical models of computation before studying complexity distinctions.

• Quantum threat — Shor’s algorithm (polynomial time on a quantum computer) would break RSA and ECC; post-quantum cryptography (lattice-based, etc.) is under active standardization (NIST).

• quantum computing — Quantum computing uses qubits, superposition, and entanglement to perform computation in ways that can outperform classical algorithms on certain tasks. Shor’s and Grover’s algorithms are among its best-known examples.
  • CNOT gate
    • cnot — The CNOT gate, or controlled-NOT gate, is the quantum analogue of XOR. It flips a target qubit conditional on a control qubit and is a standard gate for generating entanglement.

  • decoherence — Decoherence is the loss of quantum coherence caused by interaction with the environment, which makes a system behave more classically. It is a central practical problem in quantum computing and is closely associated with work by Wojciech Zurek.

  • Peter Shor — Peter Shor is a computer scientist known for Shor’s algorithm, which factors integers in polynomial time on a quantum computer. He also devised important quantum error-correcting codes, including the 9-qubit Shor code.

  • quantum advantage — Quantum advantage is the claim that a quantum computer can outperform classical computers on some task by more than a polynomial speedup. Google’s Sycamore experiment was presented as evidence for this idea, and the older term quantum supremacy has been criticized for its colonial overtones.

  • quantum algorithms — Quantum algorithms are procedures designed to run on qubits and exploit quantum effects to solve certain problems efficiently. Famous examples include Deutsch-Jozsa, Grover’s search algorithm, and Shor’s factoring algorithm.

    • Deutsch-Jozsa algorithm — The Deutsch-Jozsa algorithm is an early quantum computing algorithm for distinguishing constant functions from balanced ones. In the idealized setting it makes a single oracle query and uses Hadamard transforms; it is often cited as an exponential separation from classical deterministic approaches. It is built around quantum gates such as the controlled-NOT gate.

    • Grover’s algorithm — Grover’s algorithm is a quantum search algorithm that finds a marked item in an unsorted database with quadratic speedup over classical search. It works by repeating an oracle and diffusion step on a uniform superposition, with the number of iterations proportional to the square root of the search space.

    • Shor’s algorithm — Shor’s algorithm is a quantum algorithm for factoring integers and finding the order of a number modulo N. It uses the quantum Fourier transform and helped establish that factoring lies in the BQP complexity class.

  • quantum annealing — Quantum annealing is an optimization technique that evolves a quantum system toward a ground state. It is associated especially with D-Wave machines and is often described as a way to search for minima of an objective function.

  • quantum circuits
    • quantum gates — Quantum gates are unitary operations that act on qubits and form the building blocks of quantum circuits. Examples include Hadamard and controlled-NOT, and the Solovay-Kitaev theorem concerns how such gates can approximate arbitrary operations.
      • Hadamard gate — The Hadamard gate is a one-qubit quantum logic gate that maps basis states into equal superpositions. It is denoted H and is central to algorithms such as Grover’s and Shor’s because it creates the uniform superposition used at the start of many quantum computations.
  • quantum computers — Quantum computers use qubits, superposition, and entanglement to perform calculations beyond classical machines. Clues often mention Shor’s algorithm, period-finding, Hadamard gates, decoherence, and applications such as factoring integers or breaking RSA.
• quantum complexity classes
  • BQP — BQP is the complexity class of decision problems solvable by a quantum computer in polynomial time with bounded error. Shor’s algorithm places factoring and discrete logarithms in this class, whose relationship to PH remains a major topic in complexity theory.
    • Bounded error Quantum Polynomial time — Bounded-error quantum polynomial time, or BQP, is the class of problems solvable by a quantum computer in polynomial time with bounded error. Its famous examples include factoring and discrete logarithms, and its relation to NP is unknown.

Architecture and Operating Systems

Connect machine architecture to operating-system responsibilities.

Computer Architecture

Computer architecture studies the interface between hardware and software and the organization of processors, memory, and input/output to meet goals for performance, energy, cost, reliability, and security. Historical machines appear in Computing History; operating-system memory management appears under Operating Systems.¹

• Computer architecture

  • Harvard architecture — Harvard architecture is a computer architecture with physically separate memory systems for instructions and data. It is associated with Howard Aiken and the Mark I machine, and contrasts with the von Neumann architecture.

  • hazards — Hazards are the problems that arise in pipelined computer architectures when instructions interfere with one another. The main kinds are data, structural, and control hazards, with data hazards occurring when one instruction depends on a result not yet written back.

  • instruction pipelining — Instruction pipelining is the CPU technique of overlapping stages such as fetch, decode, execute, memory access, and writeback. It raises throughput rather than lowering latency, so stalls, bubbles, and branch prediction matter. The classic RISC pipeline is often cited as a five-stage example of this approach. Hazards such as data dependencies and mispredicted branches are the main reasons the pipeline must be managed carefully.
    • Pipeline — A pipeline is a staged system that overlaps instructions in a processor to increase throughput. The term also refers to oil transport networks, and it appears in the title of a famous surf-rock instrumental.
  • instruction set architectures
    • instruction set architecture — An instruction set architecture is the interface between software and hardware that specifies supported operations, registers, data types, and memory behavior. Examples include x86 and ARM, and the term is often contrasted with broader architectural models such as Harvard and von Neumann.
      • machine instructions — Machine instructions are the basic operations of machine language, the “words” executed by a CPU. They are fetched, decoded, and executed in architectures described by an instruction set or ISA, and are central to pipelining and VLIW design.
    • PowerPC — PowerPC is a reduced-instruction-set processor family jointly developed by Apple, IBM, and Motorola. It was used in Power Macintosh computers and was intended to bridge the gap between PCs and Macs. It is a RISC instruction-set architecture first prototyped in IBM’s 801 project and later used in Apple’s G3, G4, and G5 Macintosh computers. It became notable for features like the record bit in its opcode formats and for Motorola’s AltiVec vector extension, also called VMX or Velocity Engine. Early versions relied on emulation to run older 68K Macintosh software.
  • memory hierarchy
    • CPU cache — A CPU cache is a small, fast memory layer that stores data the processor is likely to need again, improving access speed through locality. Modern caches are often organized into levels such as L1, L2, and L3, and they may use direct-mapped or set-associative designs.
  • parallel architectures
    • MIS-D — MISD is the parallel computer architecture in which multiple processors execute different instructions on the same data stream. It contrasts with SISD, SIMD, and MIMD.
  • Performance bottlenecks
    • von Neumann bottleneck — The von Neumann bottleneck is the performance limit created by limited throughput between the CPU and memory in a von Neumann architecture. It arises because instructions and data share the same memory space, forcing traffic over a narrow channel.

  • pipelining — Pipelining is the computer architecture technique that overlaps instruction stages so multiple operations can be in progress at once. It is used to improve throughput in processors, but branch mispredictions can create bubbles and stall the pipeline.

  • processor components
    • Arithmetic Logic Unit — The arithmetic logic unit is the part of a computer processor that performs arithmetic, logical, bitwise, and Boolean operations. It works alongside registers and the control unit to execute basic machine instructions.

  • reduced instruction set computing — Reduced Instruction Set Computing (RISC) is a CPU architecture philosophy that uses a small set of simple, fast instructions, often with fixed-length encoding. It typically emphasizes a load/store design and many general-purpose registers. Common examples include MIPS, SPARC, PowerPC, and ARM.

  • register — A register is a small, quickly accessible storage unit inside a processor. RISC architectures often move values between memory and registers in a load-store design, and registers are used to hold operands during computation.

  • Registers — Registers are small, fast, temporary storage locations inside a CPU, smaller and more accessible than cache or main memory. They hold values during instruction execution and context switching, and assembly code frequently names and manipulates them, as in x86 examples such as EAX. They are central to code generation and register allocation in compilers, including graph-coloring and linear-scan methods.
    • processor registers — Processor registers are the small, very fast storage locations on a CPU that hold operands and special values like the program counter and stack pointer. They sit at the top of the memory hierarchy and are central to hazards and register allocation in compiler design.

  • von Neumann architecture — The stored-program, or von Neumann, architecture is a computer design in which data and instructions share memory, with instructions kept in memory rather than wired permanently into the machine. It was developed to overcome the fixed-program limitations of early machines such as ENIAC. Its classic drawback is the von Neumann bottleneck, because the CPU must fetch instructions and data sequentially rather than in parallel.

  • branch prediction — Branch prediction is the CPU technique of guessing whether conditional jumps will be taken so the pipeline can keep working efficiently. It often uses one-bit or two-bit saturating counters, tournament or hybrid predictors, and related schemes such as BTFNT and YAGS.

  • cache memory — Cache memory is a small, fast form of memory that stores frequently used data and instructions so the processor can access them quickly. It sits between the CPU and main memory and improves performance by reducing repeated slower accesses.

• Instruction execution — a processor fetches an instruction from memory, decodes it, and carries out the specified operation. Registers hold working values; the program counter identifies an instruction address. An instruction set defines the machine-level operations visible to software; different processor implementations can execute the same instruction set.²

• Pipelining and parallelism — a pipeline overlaps stages of different instructions, improving throughput without necessarily reducing the latency of one instruction. Data dependencies and branches can interrupt that overlap. Multiple cores can run work concurrently, but synchronization and the serial part of a task limit speedup.²

• Abstraction layers — an instruction set architecture (ISA) is the contract visible to compilers and operating systems; a microarchitecture is one hardware implementation of that contract, built from digital logic. IBM announced System/360 on 7 April 1964 as a family of machines sharing one ISA across different price and performance levels, separating software compatibility from hardware implementation.³

• Stored-program and Harvard organization — in a stored-program organization, instructions and data share memory and the processor fetches instructions by address; a Harvard organization separates instruction and data memories, a distinction still visible in some microcontrollers and in separate instruction and data caches. Attribution of the stored-program idea is discussed in Computing History.¹

• Data representation — hardware stores information as bit patterns whose meaning depends on interpretation. Two’s-complement encoding lets one adder handle signed and unsigned addition; fixed-width integers can overflow; floating-point formats such as IEEE 754 trade exact representation for range, so a value like 0.1 is only approximated in binary.¹

  • bit — A bit is the basic unit of digital information, representing one of two values, 0 or 1. Bits form bytes eight at a time and underlie computer word size, bitwise operations, Gray code, baud rates, and information-theoretic entropy; their quantum analogues can exist in superposition. In quantum teleportation, two classical bits must be sent to complete the protocol.

  • endianness — Endianness is the ordering of bytes in computer memory, with the familiar forms being big-endian and little-endian. Danny Cohen’s “On the Holy Wars and a Plea for Peace” popularized the term as a playful reference to the egg-cracking dispute in Gulliver’s Travels.

    • big-endian — Big-endian describes a memory layout in which the most significant byte is stored at the lowest address. The term comes from Gulliver’s Travels and contrasts with little-endian ordering.

• Processor performance equation — the time a program takes equals its instruction count times the average clock cycles per instruction times the clock period. Architecture, compiler, and program all affect these terms, so clock rate or core count alone does not predict performance; benchmarks compare systems on stated workloads.

• RISC and CISC — reduced instruction set computers use simple, regular instructions suited to pipelining and optimizing compilers, while complex instruction set designs such as x86 offer richer instructions. Berkeley’s RISC-I and Stanford’s MIPS processors of 1982 and 1983 demonstrated the RISC approach; later x86 processors translate complex instructions into simpler internal operations, so the modern contrast concerns instruction-set design more than internal execution.³

• Memory hierarchy and locality — programs tend to reuse recently accessed data (temporal locality) and nearby data (spatial locality), so small fast caches in front of larger, slower memory can deliver much of the speed of fast memory at lower cost. Cache misses and data movement can dominate time and energy use; paging and virtual memory appear under Operating Systems.¹

• Speculation and side channels — processors predict branches and execute instructions ahead of certainty, discarding wrong-path work. Speculation raises performance but wastes work on mispredictions, and the Meltdown and Spectre attacks disclosed in 2018 showed that speculative and out-of-order execution can leak protected data through side channels.⁴

• Input/output and interrupts — devices are controlled through registers, interrupts signal events without constant polling, and direct memory access lets devices move data without the processor copying every byte. These mechanisms link architecture to operating-system design.¹

• Flynn’s taxonomy — Michael Flynn’s 1966 classification distinguishes single and multiple instruction and data streams: SISD, SIMD, MISD, and MIMD. Vector instructions and graphics processors exploit data parallelism, while multicore processors and clusters are MIMD systems; Amdahl’s law, under Programming Paradigms and Languages, limits speedup when part of a workload remains serial.⁵

• End of Dennard scaling — Dennard scaling described how shrinking transistors could hold power density roughly constant; Hennessy and Patterson describe it slowing significantly from 2007, as transistor-density growth also fell behind Moore’s projections. Because power must leave a chip as heat, designers shifted from faster single cores toward multicore processors and specialization.³ Around 2006–2007, transistor scaling stopped delivering faster chips as shrinking transistors could no longer keep power density roughly constant. Hennessy and Patterson note the slowdown from 2007, with transistor-density growth also lagging Moore’s projections, pushing designers from faster single-core CPUs toward multicore processors and specialization because chip heat must be dissipated.

• Domain-specific architectures — accelerators such as graphics processors, neural-network processors like Google’s Tensor Processing Unit, and network processors gain performance and energy efficiency by tailoring memory use, numeric precision, and parallelism to one class of workloads. They depend on domain-specific languages and compilers and trade generality for efficiency.³

• Open instruction sets, security, and sustainability — RISC-V, begun at UC Berkeley in 2010, is an open, royalty-free ISA that anyone can implement without licensing a proprietary instruction set. Current curricula also treat hardware support for isolation and memory protection, heterogeneous and quantum architectures, and the energy and environmental costs of computing as part of architecture.⁶¹

• computer hardware

  • CPU — A CPU is the main component of a computer that fetches, decodes, executes, and writes back instructions to run programs. It carries out arithmetic and control tasks through a control unit, an arithmetic logic unit, and registers, and may use cache, buses, multiple cores, or superscalar/pipelined designs to improve performance. It is often described as the computer’s brain, and performance-related terms associated with it include clock speed, overclocking, RISC and MIPS designs, and Amdahl’s law. Intel’s Pentium family is an example.

  • dongle — A dongle is a small device that connects to a computer, often serving as a peripheral or hardware key. The term is often associated with commercial hardware like encryption devices, audio interfaces, and payment readers.

  • Integrated circuits — Semiconductor devices built from patterned layers of circuitry that pack many tiny circuit elements onto a single piece of material, forming the basis of microchips and modern computer processors. Their design may use RTL synthesis, SPICE-based simulation, and standard-cell or full-custom layout methods. Named examples and clues associated with them include the 555 timer, Jack Kilby’s work at Texas Instruments, and Moore’s law predicting transistor counts doubling every couple of years.

  • Interface standards
    • Small Computer System Interface — SCSI stands for Small Computer System Interface, a high-speed parallel interface standard for connecting devices. It is often abbreviated with the pronunciation “scuzzy.”

  • Laptops — Laptops have become performance tools for electronic musicians, composers, and live coders who use them to run software such as Ableton, Logic, Finale, or Sibelius. Ensembles and improvisation scenes have treated them as instruments in their own right.

  • motherboard — The motherboard is the main printed circuit board of a computer, and it houses the CPU socket, chipset, and connections for memory and storage. Hardware clues often mention ATX form factors, CMOS batteries, and connectors such as SATA, IDE, Berg, or Molex.

  • overclocking — Overclocking is the practice of running a CPU or memory faster than its rated speed. It is often used to boost performance, but it can also increase heat and instability and may void the warranty.

  • plug and play — Plug and play is the computer feature that lets a system automatically detect and configure attached hardware. It became a common phrase with Windows 95 and later peripheral support in PC systems.
• computing hardware
  • computers — Computers are the devices or programs that can run live-coded music, support DAWs and MIDI, and serve as the objects studied in human-computer interaction. They also appear in debates over artificial intelligence and cognition, including the Turing test and Searle’s Chinese room argument.
• computer arithmetic
  • floating-point numbers — A floating-point number is an approximate computer representation of a real number using a sign bit, exponent, and significand. Common IEEE 754 formats include single and double precision, and they are prone to rounding error, underflow, NaNs, and infinities.
• data units
  • Byte — A byte is a unit of digital information equal to eight bits. It is a basic measure of storage and file size in computer systems.
• Encoding and decoding
  • decoder — A decoder is the component or role at the end of the encryption and decryption process that turns coded information back into readable form. It is the inverse side of encoding and is common in computing and communications contexts.
• number systems

  • binary number system — The binary number system is the base-2 system built from digits 0 and 1 and underlies modern computing. Its common methods for representing negatives include sign-and-magnitude and two’s complement, and its digits are called bits.

  • hexadecimal — Hexadecimal is base 16, using digits 0 through 9 and letters A through F. It is common in programming and networking for MAC addresses, IPv6 notation, and 0x-prefixed constants. Because each hex digit corresponds to four bits, hexadecimal is easy to convert to and from binary. It is also used for color codes and many debugging dumps.
    • hexadecimal or base-16 — Hexadecimal is the base-16 numeral system used heavily in computing. Each hex digit corresponds to four bits, and the system is often used in programming and HTML color codes.
  • nybbles
    • nybble — A nybble is four bits, or half of a byte. The term is used in computer architecture for the small unit left after a byte is shifted right four times.
• Number systems and representations
  • binary — Binary is the base-2 number system used by computers and also a general term for two-valued logic. In algorithms, binary search repeatedly halves the search space, and binary trees have nodes with at most two children.
• numeral systems
  • binary code — Binary code represents information using 0s and 1s, with bits as the basic units. It is the low-level numeral system commonly used for machine code and other computer internals.
• numerical computing
  • floating point number — A floating point number is a numeric data type used to approximate real values with a sign, significand, and exponent. IEEE 754 defines common floating-point formats, including 32-bit and 64-bit variants.
• signed integer representation
  • two’s complement — Two’s complement is the standard binary method for representing signed integers. Negative values are formed by inverting the bits and adding one.
• Computer performance
  • floating-point operations per second — FLOPS is an abbreviation for floating-point operations per second, a standard measure of computer performance.
• computer memory — Computer memory is the storage resource used by programs, including random-access and virtual memory, and it must often be managed manually in low-level programming. Clues include malloc and free, segmentation faults, thrashing, caches, and hardware forms such as RAM, ROM, and flash memory.

  • DRAM — DRAM, or dynamic random-access memory, is computer memory built from capacitors that must be refreshed continuously. It stores active data for a system and is commonly packaged in DIMMs for use in modern computers and devices.

  • Random Access Memory — Random access memory (RAM) is volatile computer memory used as the computer’s main working memory for data and instructions currently in use. It can be accessed in any order and is designed for fast read and write access. Common forms are dynamic RAM (DRAM), which uses capacitor-transistor cells and requires periodic refresh, and static RAM (SRAM), which uses six-transistor flip-flop circuitry and is often used for caches. Newer variants include non-volatile and magnetoresistive designs. RAM capacity is often measured in gigabytes; common desktop systems use several gigabytes or more, and shortages can force systems to swap to disk.

  • ROM — ROM, or read-only memory, is nonvolatile storage that normally cannot be rewritten in ordinary use. It appears in forms such as mask ROM, EPROM, EEPROM, and flash memory, and was used in early core rope systems and video game cartridges.

  • SDRAM — SDRAM, or synchronous dynamic random access memory, is a volatile form of computer memory that stores bits on capacitors. Its double-data-rate version transfers on both clock edges and is associated with pipelining and memory speed.

• Computer storage

  • flash memory — Flash memory is a nonvolatile storage technology used in USB drives, memory sticks, and devices like graphing calculators. It comes in NAND and NOR forms and stores data in floating-gate transistors using charge tunneling.

  • hard disk drive — A hard disk drive is a nonvolatile computer storage device that stores binary data on rotating magnetic platters using a movable read/write head. It is measured by capacity in gigabytes or terabytes, and its performance is described by terms such as seek time, tracks, sectors, and areal density. Hard drives were historically common as the system drive associated with the C: letter, and early examples include the IBM RAMAC. As platter densities increased, later designs faced limits from the superparamagnetic effect. Hard disk drives are still used in RAID arrays and other mass-storage systems, though many uses have been replaced by solid-state drives. They are commonly sold in 2.5-inch and 3.5-inch sizes.

• Computer hardware interfaces
  • PS/2 — PS/2 is the keyboard-and-mouse connector standard that became common with ATX motherboards in the mid-1990s. Its pinout includes clock, power, ground, and a single data line, and the name is also shared by an older line of computer hardware.
• computer input devices
  • computer mouse — A computer mouse is a pointing peripheral used to move the cursor on a screen or graphical interface. Douglas Engelbart built the first one, and his patent called it an “X-Y position indicator for a display system.” Early models used wheels or trackballs, and later popular versions included optical and mechanical models with multiple buttons.

• FireWire — Apple’s high-speed data transfer interface, standardized as IEEE 1394 and developed as an alternative to USB. It was promoted for fast multimedia and video connections, later revisions improved speed and connector options, and versions used six-pin or nine-pin plugs. Sony used the same interface under the iLink/i.LINK name, and it appeared on the PlayStation 2 as a port for linking to other machines.

• interrupts
  • Interrupt — An interrupt is a signal that causes a computer to stop its current task and handle a request for attention. Hardware and software interrupts are associated with interrupt request lines and service routines.

• microcontrollers — Microcontrollers are single-chip computers that combine a CPU, memory, and input-output pins for embedded control tasks. They often communicate through UART or SPI and are common in platforms such as Arduino boards based on AVR chips.

• Graphics hardware
  • Graphics Processing Units — Specialized electronic circuits designed for rendering images and handling highly parallel computations. They are used to accelerate computation in tasks such as deep learning, and appear in products such as NVIDIA’s GeForce and AMD’s Radeon lines. Associated APIs and frameworks include CUDA, OpenGL, DirectX, OpenCL, and DirectCompute.
• hardware
  • Field-programmable gate arrays — Field-programmable gate arrays are reconfigurable integrated circuits built from configurable logic blocks and switch matrices. They are programmed with hardware description languages such as Verilog or VHDL and are more flexible than ASICs, though often larger and more power-hungry. They are used for rapid prototyping, hardware emulation, and other tasks that need logic to be rewritten after manufacturing. Xilinx and Altera are major vendors, and projects like IceStorm and Project X-Ray focus on reverse engineering their bitstreams and architectures.

Operating Systems

• operating systems
  • file permissions
    • chmod — chmod is the UNIX command used to change file or directory permissions. It can set permissions with symbolic or octal notation.
  • input/output
    • Asynchronous input/output — Asynchronous input/output is I/O in which control returns to the user program before the operation finishes. It contrasts with synchronous I/O, where the program waits for the request to complete.

  • kernel — A kernel is the central component of an operating system, controlling hardware access, memory, and process execution. The same word also appears in mathematics as the null space of a linear map, in machine learning as a kernel function or kernel trick, and in image processing as a convolution matrix.

  • kernel — The core part of an operating system, separate from user space and accessed through system calls. It handles privileged hardware access and runs in ring zero. Modern operating systems may use monolithic or microkernel designs, and Docker containers can share the same kernel while user space remains separate.

  • Linux — Linux is a Unix-like open-source operating system created by Linus Torvalds, with common distributions such as Ubuntu, Fedora, Debian, and Red Hat. It uses a shell for command-line interaction and is commonly paired with desktop environments like GNOME and KDE.

  • pipes — Pipes are hollow cylinders used to transport fluids; their flow properties are studied with ideas such as Reynolds number, friction factor, and the Darcy-Weisbach equation. The word also refers to smoking implements, ceremonial or peace pipes in Native American contexts, a UNIX communication channel between processes, and the subject of Magritte’s The Treachery of Images (“This is not a pipe”).

  • POSIX — POSIX is the Portable Operating System Interface, a family of Unix-based standards for compatible APIs, shells, and utilities. It is the standard basis for pthreads and similar cross-platform programming interfaces on Unix-like systems.

  • process creation
    • fork — A fork is a tactic in chess in which one piece attacks two or more targets at once, often including a royal fork against the king and queen. In computing, to fork a process means to duplicate the current running process, producing a child that can later be replaced by exec. The word also names the utensil introduced to the West in stories about Theophanu, making it a recurring clue in both science and history questions.
  • processes — In computing, a process is an executing instance of a program, distinct from a thread but able to contain many threads. Processes can be duplicated by fork, and orphan processes are reparented to init or another early system manager.
• Processes, Scheduling, and Synchronization

  • Process vs thread — a process is an independent execution environment with its own memory space; threads share memory within a process; lighter-weight context switching for threads.

  • Scheduling — OS decides which process/thread runs on the CPU; algorithms: FCFS (first-come-first-served), SJF (shortest job first), round-robin (time slices), priority scheduling.

    • resource starvation — Resource starvation is a scheduling problem in which a process is continually denied the resources it needs to finish. It is distinct from deadlock, though both can prevent progress.

    • CPU scheduling — FCFS: simple, convoy effect; SJF (Shortest Job First): optimal average wait time, requires knowing burst times; Round Robin: time slices (quantum), good for interactive systems; Priority scheduling: can cause starvation (solved by aging).

  • Context switch — saving and restoring CPU state when switching between processes/threads; overhead degrades performance at high frequency.

  • Deadlock — four necessary conditions (Coffman, 1971): mutual exclusion, hold-and-wait, no preemption, circular wait; prevention requires denying at least one condition; detection via resource-allocation graph; Dining Philosophers problem (Dijkstra) illustrates deadlock and starvation with five philosophers alternating eating/thinking. It occurs in concurrent systems when processes are each waiting for resources held by others.
    • Dining Philosophers problem — five philosophers sit at a round table; each needs two forks to eat; naive solution deadlocks when all pick up left fork simultaneously; solutions include resource ordering, Chandy/Misra approach, or an arbitrator; classic concurrency textbook problem. It is also used to illustrate starvation as well as deadlock, and solutions such as resource ordering or the Chandy-Misra solution.

  • Semaphore — synchronization primitive invented by Edsger Dijkstra; integer counter with atomic P (wait/down) and V (signal/up) operations; binary semaphore (0/1) = mutex; counting semaphore controls a pool of N resources; prevents race conditions and coordinates producer-consumer.

  • Mutex (mutual exclusion lock) — only one thread holds the lock at a time; prevents race conditions on shared data; a thread that cannot acquire a mutex blocks (sleeps) until the holder releases it; distinct from a spinlock, which busy-waits.

  • Race condition — output depends on the non-deterministic interleaving of concurrent operations; prevented by synchronization. It is a common source of security bugs in threaded programs and in time-of-check, time-of-use exploits.

  • Spinlock — busy-wait synchronization; thread loops checking a flag rather than sleeping; avoids context-switch overhead for very short critical sections; wastes CPU if the wait is long; common in OS kernel code.

  • Condition variable — synchronization primitive used with a mutex; threads wait (sleep) until another thread signals a condition (e.g., pthread_cond_wait/signal); used in monitor-based concurrency; avoids busy-waiting.

  • Monitor — high-level synchronization construct combining a mutex and one or more condition variables; ensures mutual exclusion automatically; Java’s synchronized keyword implements monitors; C. A. R. Hoare (1974).

  • Livelock — two or more threads keep changing state in response to each other but make no progress; distinct from deadlock (where threads are blocked); example: two people in a hallway each stepping aside in the same direction.

  • IPC (inter-process communication) — mechanisms for processes to exchange data: pipes, message queues, shared memory, sockets, semaphores, signals; shared memory is fastest (no kernel copy); pipes are simplest for parent-child processes.

  • Concurrent computing
    • concurrency — Concurrency is the property of allowing multiple computations or events to proceed at the same time. In geometry it refers to lines meeting at a point, while in computer science it describes out-of-order or parallel execution without changing the result.
      • barriers
        • barrier — A barrier reef is a reef separated from land by a lagoon, such as the Great Barrier Reef off Queensland. In computing, a barrier is a synchronization point that forces threads to wait until all have arrived.

      • Multithreading — Multithreading is a programming and systems technique that divides execution into multiple threads that can run concurrently or appear to do so. The clues reference its use in fast Fourier transform algorithms, pipeline hazards, and instruction-level parallelism in computer architecture.

      • race conditions — A race condition is a concurrency bug that occurs when two threads or processes access shared data at the same time without proper synchronization. Mutexes and semaphores are common ways to prevent these hazards.

      • Synchronization
        • Mutual exclusion — Mutual exclusion is the synchronization principle that keeps two threads from entering the same critical section at the same time. It is enforced with locks or mutexes, and the term also describes events in probability that cannot both occur.

          • Dekker’s algorithm — Dekker’s algorithm is an early solution to the mutual exclusion problem in concurrent programming. It uses competing flags and spinning to coordinate access to a critical region.

          • mutexes — A mutex is a mutual-exclusion primitive that lets only one thread enter a critical section at a time. It is a special kind of semaphore and, in systems programming, is commonly used to protect shared data.

      • synchronization problems
        • the dining philosophers problem — The dining philosophers problem asks how competing agents can share too few utensils without deadlock or starvation. It is a classic concurrency problem often solved with semaphores and other synchronization schemes.

      • thread — A thread is a lightweight strand of fiber or cord, and in computing it is a unit of concurrent execution within a process, allowing concurrency without the overhead of a full process switch. The word also names a literal cord-like object worn in rites such as the Hindu upanayana ceremony.

      • Threads — Threads are units of execution in parallel programming, able to run concurrently within a single process. They are also textile strands used in garments such as the mangala sutra and the sacred thread worn in Hindu initiation rites.
  • concurrency problems
    • Dining Philosophers — The Dining Philosophers is a classic concurrency problem introduced by Dijkstra. It models five thinkers competing for shared forks without causing deadlock or starvation.
  • concurrent programming
    • Synchronization primitives
      • semaphores — Semaphores are Dijkstra’s synchronization primitives for controlling access to shared resources in concurrent programming. They are commonly described with wait and signal operations and appear in problems like dining philosophers and producer-consumer.
  • concurrency control
    • locks — Locks are synchronization mechanisms that give one user or thread exclusive access to a shared resource, often to preserve isolation in concurrent systems and databases. They are closely associated with mutexes and other mutual-exclusion primitives used to prevent contention and control access to data.
      • Lock — A lock is a fastening device used to secure doors and other objects against intrusion. The same word also appears in computing, where a lock or mutex keeps more than one thread from entering a critical section at the same time.
• Virtual Memory, Caches, and Storage

  • Virtual memory — abstraction giving each process its own address space; paging maps virtual to physical addresses via a page table; a TLB (translation lookaside buffer) caches recent translations. It gives programs a contiguous address space even when physical memory is noncontiguous, mapping virtual addresses to physical ones through paging, page tables, and translation lookaside buffers.

  • Page fault — a process accesses a page not in physical memory; OS loads it from disk; thrashing occurs when excessive page faults dominate CPU time.

  • Memory hierarchy and cache — registers → L1 cache → L2 cache → L3 cache → RAM → SSD/HDD; each level trades speed for size; cache hit serves data from fast cache; cache miss fetches from slower memory; cache coherence is the challenge in multi-core systems.

  • Cache replacement policies — LRU (Least Recently Used): evict the item unused longest; LFU (Least Frequently Used); FIFO; LRU implemented efficiently with a doubly linked list + hash map.

  • Thrashing — when a process spends more time swapping pages than executing; occurs when working set does not fit in RAM; addressed by working-set model or page-fault frequency control. It is the severe slowdown that happens when a system spends most of its time swapping pages between RAM and disk, usually because the working set does not fit in memory and page replacement becomes constant and inefficient.

  • caching
    • cache — A cache is a small, fast storage layer or memory structure placed between registers and main memory, or alongside a processor, to keep recently used data close to the processor and reduce access time by exploiting temporal and spatial locality. Common levels include CPU L1, L2, and L3 caches. Caches may use policies such as LRU, FIFO, write-back, and write-allocate. Specialized examples include a translation-lookaside buffer (TLB) and a browser cache.
  • file paths
    • absolute path — An absolute path is a file path that begins at the root directory rather than from the current working directory. It names a location by tracing every successive directory down from the root, unlike a relative path.
  • File systems

    • Deleting a file — Deleting a file is the irreversible action performed by commands such as rm when a file is removed from storage. Moving something to a recycle bin does not necessarily delete it permanently.

    • Files — Files are the stored data objects organized in directories on a computer, often identified by extensions such as .txt or .pdf. Operating systems manage them with file systems like FAT and NTFS, and details about them may be tracked by inodes or symbolic links.

    • fragmentation

      • file system fragmentation — File system fragmentation is the scattering of related data across noncontiguous storage blocks instead of keeping it sequential. It can slow access on magnetic drives and is often reduced by defragmentation tools or better allocation strategies.

  • File system — organizes data on disk; UNIX uses an inode-based structure; ext4, NTFS, HFS+ are common; journaling file systems log changes before committing to prevent corruption.

  • storage
    • RAID — RAID is a storage technology that combines multiple hard disks or drives into one logical unit for performance or fault tolerance. Its common levels include striping without redundancy at level 0, mirroring at level 1, and parity-based schemes such as levels 5 and 6.
• Kernels and Systems Software

  • System call — interface between user programs and the OS kernel; transitions CPU from user mode to kernel mode; examples: read(), write(), fork(), exec().

  • Kernel architecture
    • Monolithic kernel — A monolithic kernel puts most operating-system services into kernel space rather than separating them into a small core. Linux is the standard example, contrasted with microkernels such as the GNU Hurd design.
  • Linux distributions
    • Debian — Debian is a major Linux distribution known for its stability, strong commitment to free software, and the GNOME desktop environment as its default. It is the upstream basis for Ubuntu.
  • systems software
    • operating system — Software that acts as the layer between hardware and applications, managing a computer’s hardware, processes, user programs, memory use, multitasking, and access to devices, often through a kernel. Standard examples include Linux, Windows, and macOS; research systems include Plan 9 and Inferno. Containers can share a single kernel at this level of virtualization.
  • Virtualization

    • virtual machine — A virtual machine is software that emulates a physical computer and runs its own operating system on top of a host system. Quizbowl clues often mention Java bytecode and HotSpot, QEMU and Xen, or the use of a hypervisor to host one or more such systems.

    • virtual machines — Virtual machines are software emulations of computers that let one system host another, from Java’s JVM to enterprise hypervisors like ESXi and Hyper-V. They support platform-independent execution and are a standard way to isolate operating systems or processes inside a physical machine.

  • Unix
    • sudo command
      • sudo — sudo is the Unix command used to run programs with elevated privileges, most often as root. Its name reflects “superuser do,” though it can also be used to act as another user account.
  • Unix commands

    • grep — grep is the command-line search utility that prints lines matching a regular expression. Its variants include fgrep and ripgrep, and it is commonly used to count or filter text matches in plain files.

    • less — Less is the Unix pager command that lets users move through files while also naming the common grammar error of using it where “fewer” should appear with count nouns. In both contexts, it contrasts with a complementary command or word: more in computing and fewer in grammar.

    • rm — This is the Unix remove command, used to delete files from the command line. It is commonly abbreviated rm and is one of the standard shell utilities.

• memory management

  • pages — Pages are fixed-size blocks of virtual memory, usually 4 kilobytes, that operating systems move between RAM and storage. A missing page can trigger a page fault, and Linux manages them through mechanisms such as page tables and huge pages.

  • translation lookaside buffer — A translation lookaside buffer, or TLB, is a cache in the memory-management unit that stores page-table entries. It speeds virtual-to-physical address translation, and a miss forces a page-table walk.

Databases and Distributed Networks

Follow data storage into databases and distributed systems.

Databases

• Databases — Databases are organized collections of information or data-storage systems, often queried with SQL in the relational case and structured into tables. They may be relational or non-relational; examples and associated systems include Mongo, Hadoop, and MapReduce. They are governed by concepts such as Codd’s rules, ACID properties, and schema-on-read versus schema-on-write ideas.

  • database — A database is an organized collection of information, often structured into tables with rows and columns. Relational databases are queried with SQL and are designed to satisfy normalization rules and ACID properties.

  • query — A query is a request from a database, usually written in SQL with statements such as SELECT. The term also appears in graph query languages such as Cypher and Gremlin, and in the name of the jQuery library.

  • relational databases — Relational databases organize information into tables of rows and columns and are queried with SQL. They are associated with Edgar F. Codd’s relational model, normal forms, foreign keys, and ACID transactions.

  • transactions — Transactions are single logical units of work in database systems, governed by the ACID properties of atomicity, consistency, isolation, and durability. They are started and ended with commands such as COMMIT and ROLLBACK, and transaction costs also appear in economics.
    • Atomicity — Atomicity is the property of operations or transactions that happen all at once or not at all. In the ACID database properties, it requires a transaction to act as a single irreducible unit, so if it fails halfway through none of it is supposed to take effect. The term also appears in concurrency control, lock-free algorithms, and the total ordering of some distributed broadcasts.
  • views
    • view — A view is the virtual table returned by a database query, and a materialized view stores that result physically. The term also appears in the model-view-controller pattern, in viewing frustums, and in web analytics as a page access.
• Relational Models and Querying

  • Relational database — data organized in tables (relations) with rows and columns; SQL is the query language; primary keys uniquely identify rows; foreign keys enforce referential integrity. It follows Edgar Codd’s relational model, with rows typically identified by primary keys and foreign keys used to enforce referential integrity.

  • Relational model and Codd — Edgar F. Codd (IBM) proposed the relational model in 1970 (“A Relational Model of Data for Large Shared Data Banks”); introduced relations (tables), keys, and relational algebra; Turing Award 1981; prior systems were hierarchical (IMS) or network-based.

  • SQL — Structured Query Language; declarative language for relational databases; ANSI standard since 1986; DDL (CREATE, ALTER, DROP), DML (SELECT, INSERT, UPDATE, DELETE), DCL (GRANT, REVOKE); first implemented in IBM System R (1974). It was developed at IBM by Donald Chamberlin and Raymond Boyce in 1974, based on Edgar Codd’s relational model, and is used by systems such as Oracle, MySQL, and PostgreSQL, which support SQL dialects.
    • SELECT statements
      • SELECT — In databases, SELECT is the statement used to retrieve rows from tables, often with clauses such as WHERE, GROUP BY, HAVING, and ORDER BY. In everyday use, it can also refer to choosing or picking out items, and in programming it commonly names the main data-reading command.

  • Normalization — process of eliminating redundancy; 1NF (atomic values), 2NF (no partial dependencies), 3NF (no transitive dependencies), BCNF (Boyce-Codd). The term also appears in probability and quantum mechanics, where it means scaling a wavefunction so its total probability is one.

  • Index — auxiliary data structure (typically B+ tree) speeding up lookups at the cost of write overhead and storage; a clustered index dictates physical row order.

  • JOIN types — INNER JOIN (matching rows only), LEFT/RIGHT OUTER JOIN (all rows from one side), FULL OUTER JOIN, CROSS JOIN (Cartesian product).

  • View (SQL) — virtual table defined by a SELECT query; stored query, not stored data; simplifies complex queries; materialized view physically stores the result for performance.

  • Stored procedure — named, precompiled SQL routine stored in the database; reduces round trips; can accept parameters; common in enterprise databases; debated in modern architectures.

  • Query optimization — RDBMS parses SQL into a query plan; the optimizer chooses join order, index use, and execution strategy using cost estimates; EXPLAIN shows the chosen plan.

  • ORM (Object-Relational Mapper) — maps OOP objects to relational tables; examples: Hibernate (Java), SQLAlchemy (Python), ActiveRecord (Ruby).

  • database operations
    • join — A join is the relational database operation that combines rows from two tables using a shared field. SQL uses inner and outer joins, while relational algebra treats the natural join as a primitive-looking operation built from selection, projection, product, and renaming. The same idea appears in theoretical computer science under both natural and categorical formulations.
• Transactions and Distributed Data

  • ACID — properties of a reliable transaction: Atomicity (all-or-nothing), Consistency (data integrity invariants preserved), Isolation (concurrent transactions do not interfere), Durability (committed data persists).

  • Transaction isolation levels — Read Uncommitted, Read Committed, Repeatable Read, Serializable; higher levels prevent more anomalies (dirty reads, non-repeatable reads, phantom reads) at the cost of concurrency.

  • CAP theorem — during a network partition, a distributed read/write service cannot guarantee both linearizable consistency and a response to every request received by a non-failing node. Linearizability makes operations behave as if they occurred in one order consistent with real time. A service can preserve that consistency by delaying or refusing some operations, or keep serving requests while accepting weaker consistency. The tradeoff applies during a partition, not as an unrestricted “pick any two” rule.⁷
    • CAP theorem proof / Brewer’s theorem — stated by Eric Brewer (2000), proved by Gilbert and Lynch (2002); in the presence of a network partition, a distributed system cannot be both consistent and available; modern systems acknowledge CP vs AP trade-offs.

  • BASE — alternative to ACID for distributed/NoSQL: Basically Available, Soft state, Eventually consistent.

  • NoSQL categories — key-value (Redis), document (MongoDB), column-family (Cassandra, HBase), graph (Neo4j); trade normalization and ACID for horizontal scalability.

  • Sharding — horizontal partitioning of a database across multiple servers by a shard key (e.g., user ID); scales writes; complicates joins and transactions; used by large-scale web applications.

  • Replication — copying data to multiple database replicas; primary-replica model: writes to primary, reads from replicas; improves read throughput and fault tolerance; introduces replication lag.

  • Two-phase commit (2PC) — distributed transaction protocol ensuring all-or-nothing commit across multiple nodes; Phase 1 (prepare): coordinator asks all participants to vote; Phase 2 (commit/abort): coordinator sends final decision; blocks on coordinator failure.

  • Eventual consistency — distributed systems guarantee that if no new updates are made, all replicas will eventually converge; weaker than strong consistency but allows higher availability and partition tolerance; common in NoSQL (Cassandra, DynamoDB).
• Database management systems
  • MySQL — MySQL is a widely used relational database system that became a standard part of the LAMP stack and was later acquired by Sun and then Oracle. Its transactional behavior depends on InnoDB, while MyISAM was the older default storage engine; MariaDB later split off as an open-source fork.
• Database software
  • Access — Access is Microsoft’s database management program in the Office suite. It is the component that distinguishes some older Office editions and is also the name of money or influence given in political fundraising phrasing.

Networking Basics

• OSI model — 7-layer reference model: Physical, Data Link, Network, Transport, Session, Presentation, Application; TCP/IP model collapses to 4 layers. It was developed by ISO in the late 1970s as a conceptual framework for understanding and troubleshooting network communication, though real protocols do not map cleanly onto it. It is protocol-independent and often used to explain how networking functions such as switches and congestion control are organized.

• IP (Internet Protocol) — connectionless, best-effort delivery; IPv4 (32-bit addresses, ~4.3 billion), IPv6 (128-bit, effectively unlimited).

• TCP vs UDP — TCP provides reliable, ordered, connection-oriented delivery (three-way handshake: SYN, SYN-ACK, ACK); UDP is connectionless, unreliable, faster; used for DNS, streaming, gaming.

• DNS — Domain Name System; translates hostnames to IP addresses; hierarchical distributed database. Paul Mockapetris introduced it in 1983; it translates human-readable domain names to IP addresses.

• HTTP/HTTPS — HyperText Transfer Protocol; stateless, application-layer; HTTPS adds TLS encryption.

• Router vs switch vs hub — hub broadcasts to all ports; switch learns MAC addresses and forwards frames to the correct port (Layer 2); router routes packets between networks using IP addresses (Layer 3).

• Subnet and CIDR — Classless Inter-Domain Routing partitions IP space with prefix notation (e.g., 192.168.1.0/24 = 256 addresses); subnetting divides a network into smaller blocks; NAT allows multiple hosts to share one public IP.

• Port and socket — IP address identifies a host; port (16-bit integer) identifies a process; a socket is a (IP, port) pair; well-known ports: HTTP 80, HTTPS 443, SSH 22, DNS 53, SMTP 25.

• Three-way TCP handshake — SYN (client → server), SYN-ACK (server → client), ACK (client → server); establishes sequence numbers and connection state; four-way FIN handshake tears down the connection.

• CDN (Content Delivery Network) — geographically distributed servers cache and serve static content close to users; reduces latency; examples: Cloudflare, Akamai, AWS CloudFront. They also reduce load on the origin server by caching and serving content closer to users.

• Load balancer — distributes incoming requests across multiple backend servers; algorithms: round-robin, least connections, IP hash; Layer 4 (transport) vs Layer 7 (application/HTTP) balancers.

• computer networking

  • client — A client is the computer in a client-server system that requests services from a server. Thin clients do little local processing, while fat clients handle more work on the local machine.

  • Congestion control
    • network congestion — Network congestion is the overload condition that occurs when packet arrival exceeds transmission capacity, causing delay and loss. It is the problem addressed by TCP slow start, additive-increase/multiplicative-decrease, and queue-management tools such as random early detection.
  • network addresses
    • MAC address — A MAC address is the 48-bit hardware identifier assigned to a network interface. It is the source of the hexadecimal value that early GUID schemes were based on.

  • network switches — Network switches are devices that forward traffic between hosts on a local network using learned addresses. Layer 3 or multilayer switches can also route traffic between separate networks, combining switching with higher-level forwarding.

  • Sockets — Sockets are the standard endpoint for network communication, and they can also connect two programs running on the same machine. Once connected, a socket pair allows bidirectional data transfer between the two sides.
• Networking

  • Application Layer — The application layer is the top layer of the OSI model and the highest TCP/IP layer closest to the user. Protocols such as HTTP, FTP, SMTP, DNS, DHCP, and POP3 belong there rather than at the lower transport or network layers.

  • broadcasting — Broadcasting in quantum information is the attempt to distribute a mixed state to multiple systems, subject to the no-broadcasting theorem. In networking, broadcast domains are the layer-2 regions over which a frame is flooded to all devices.

  • computer networks — Computer networks are systems of interconnected nodes that communicate with one another, often organized by topologies such as point-to-point, daisy chain, or bus. They include packet-switched systems routed by routers, and layer 3 of the OSI model describes them above the data link layer.

    • latency — Latency is the delay or lag between a cause and its effect, often measured as network round-trip time. In epidemiology, it also names the interval between infection and contagiousness. The term is used for network ping times and other wait-time phenomena.

    • local area networks

      • local area network — A local area network is a computer network that connects devices over a short distance, such as within a building. It is the meaning of the abbreviation LAN, in contrast to a long-haul or wide-area network.

  • congestion — Congestion is the network condition in which traffic exceeds capacity, causing packets to be dropped and performance to fall. TCP uses mechanisms such as slow start, congestion avoidance, ECN, and RED to manage it.

  • payload — A payload is the maximum load a vehicle or spacecraft can carry. In networking, it is the body of transmitted data, and in cybersecurity it can mean the malicious code portion of an attack.

  • telephone numbers — Telephone numbers are the digit strings used for routing calls, including country calling codes and related dialing systems. They also appear in cultural clues like Tommy Tutone’s “867-5309/Jenny,” and in sampling methods such as random-digit dialing.
• serial communication
  • RS-232 — RS-232 is the serial communication standard used to connect computers and external devices over a cable. It is associated with Hewlett-Packard instrumentation and other remote device communication setups.
• Telecommunications
  • Broadband Integrated Services Digital Network — Broadband Integrated Services Digital Network expands the acronym B-ISDN. It refers to a broadband telecommunications architecture intended to carry integrated voice, data, and video services.
• wireless communication
  • Bluetooth — Bluetooth is a short-range wireless communication standard for connecting devices such as phones, headsets, keyboards, and mice. It uses the 2.4 GHz band and is named for Harald Bluetooth, the Danish king who united Denmark and Norway.
• Addresses
  • address — An address is an identifier used to locate data or devices, including memory addresses in computing and network addresses on the Internet. Examples include MAC addresses for hardware and IPv4 or IPv6 addresses for internet routing.
• network protocols
  • Internet Protocol — Internet Protocol (IP) is the network-layer protocol in the TCP/IP suite that addresses hosts and routes packets between them on packet-switched networks. Routers use IP addresses to forward messages. Its two main versions are IPv4 and IPv6; IPv6 uses colon-separated hexadecimal addresses and expands the address size to 128 bits.
• Client-server computing
  • servers — Servers are the computers that respond to client requests and often run backend services for applications. They are a standard setting for Linux distributions such as Red Hat Enterprise Linux and for server-side runtimes like Node and Express.

Distributed Systems and Blockchain

• Paxos / The Part-Time Parliament — Leslie Lamport’s consensus paper was written in 1989, first submitted in 1990, and published in ACM Transactions on Computer Systems 16(2), 133–169 (1998). Its publication history explains the multiple dates; Paxos concerns agreement despite failures, rather than a single universally applicable implementation.⁸

• Blockchain platforms
  • Ethereum — Ethereum is the smart-contract blockchain platform created by Vitalik Buterin. It runs decentralized applications through the Ethereum Virtual Machine and is closely associated with the Solidity programming language.
• Distributed computing — Distributed computing uses multiple networked computers to act like one system. It is associated with volunteer projects such as SETI@home and Folding@home.
  • consensus — In blockchain systems, consensus is the state in which distributed processes agree on the result of a computation. It is reached by protocols such as proof-of-work and proof-of-stake, and is central to the Byzantine generals problem.
    • Byzantine generals — The Byzantine generals are the model for the Byzantine Generals Problem, a classic fault-tolerance problem in distributed computing. It asks how separated commanders can reach agreement when some messengers or participants may be traitors, and Lamport’s signed-message result is a standard clue.
• distributed ledger technology
  • blockchain — A blockchain is a distributed ledger made of records linked together with cryptographic hashes. It underlies Bitcoin and Ethereum, and changes that force everyone to upgrade their software are called hard forks.

    • blocks — Blocks are basic building units in many games, especially Roblox and related sandbox or construction platforms. In statistics and agriculture, blocks are homogeneous groups used to reduce noise in experiments by partitioning subjects or plots by shared traits such as gender. In Bitcoin, a block is a unit added to the blockchain to record transactions.

    • Mining

      • cryptocurrency mining — Cryptocurrency mining is the energy-intensive proof-of-work process that creates new virtual currency and validates blockchain transactions. It often uses GPUs and hash algorithms such as SHA-256 and Scrypt.
  • blockchains — A blockchain is a distributed ledger that records transactions in linked blocks. Bitcoin’s proof-of-work system and many NFT applications use blockchains to append tamper-resistant records.
• Distributed systems
  • statelessness
    • stateless — A stateless system does not retain information from one request or interaction to the next. In REST and similar service designs, that means each request is independent, while stateless firewalls and applications avoid keeping prior-session data.

Cryptography and Security

Distinguish cryptographic tools, security goals, and common attacks.

Cryptography Fundamentals

• Encryption, Keys, and Cryptanalysis

  • Symmetric encryption — the same key encrypts and decrypts; fast; key distribution is a challenge; AES (Advanced Encryption Standard) is the current standard (128/192/256-bit keys). It is used for bulk data transfer in TLS; a common example is AES-256-GCM.

  • Asymmetric (public-key) encryption — mathematically linked key pair: a public key encrypts, a private key decrypts; solves key distribution; examples: RSA (factoring hardness), Elliptic Curve Cryptography (ECC) (discrete log over elliptic curves).

  • RSA — Rivest-Shamir-Adleman (1977); security rests on the difficulty of factoring the product of two large primes; key sizes typically 2048–4096 bits. The RSA algorithm is a public-key cryptosystem named for Rivest, Shamir, and Adleman. Its public key uses n and e, while the private key uses d; it is widely used in systems such as PGP and SSL.
    • RSA cryptography
      • Clifford Cocks — Clifford Cocks is a British mathematician and cryptographer who independently arrived at the basic idea behind RSA in 1973. His discovery was classified by the British government for years before becoming public.
  • Diffie-Hellman key exchange — allows two parties to establish a shared secret over a public channel without transmitting the secret; basis for TLS/SSL key agreement. 1976 method by Whitfield Diffie and Martin Hellman that uses the computational difficulty of the discrete logarithm problem; the first practical public-key protocol.
    • Diffie–Hellman and ECDH — classical finite-field Diffie–Hellman uses a suitable subgroup of the nonzero residues modulo a prime; elliptic-curve Diffie–Hellman uses an elliptic-curve group. Computing the shared secret from the public values is the Diffie–Hellman problem; solving the corresponding discrete logarithm problem would solve it. Unauthenticated key exchange alone does not prevent a man-in-the-middle attack.⁹
  • AES (Advanced Encryption Standard) — symmetric block cipher standardized by NIST (2001); replaced DES; key sizes 128, 192, or 256 bits; block size 128 bits; uses SubBytes, ShiftRows, MixColumns, AddRoundKey rounds; selected from the Rijndael cipher (Joan Daemen and Vincent Rijmen).
    • AES cryptanalysis — distinguish full-round key recovery from reduced-round, related-key, or known-key results. The 2011 biclique paper reported costs of approximately 2¹²⁶·¹, 2¹⁸⁹·⁷, and 2²⁵⁴·⁴ operations for AES-128, AES-192, and AES-256 respectively; these are theoretical shortcuts, not practical decryptions. AES remains specified by NIST; implementation security and correct modes are separate questions.¹⁰

  • Block cipher modes — AES alone encrypts a single 128-bit block; modes chain blocks: ECB (insecure, patterns visible), CBC (chained XOR), CTR (turns block cipher into stream cipher), GCM (authenticated encryption); CTR/GCM are preferred.

  • Elliptic curve cryptography (ECC) — public-key cryptography over elliptic curve groups; same security as RSA with much smaller keys (256-bit ECC ≈ 3072-bit RSA); used in TLS, Bitcoin (secp256k1); discrete logarithm problem over elliptic curves is the hard problem.

  • Key exchange
    • Diffie–Hellman — Diffie–Hellman is the classic public-key key-exchange method that lets two parties establish a shared secret over an insecure channel. It appears in foundational cryptography discussions alongside ElGamal and the 1976 paper New Directions in Cryptography.
  • Classical cryptography
    • substitution ciphers
      • Shift cipher — A simple monoalphabetic substitution cipher that rotates each letter of the plaintext by a fixed number of positions in the alphabet, usually using an integer key from 0 to 25. The Caesar cipher is the classic example; a three-letter shift turns HI into KL. It is named for Julius Caesar, whose use of it was reported by Suetonius.
    • Vigenère cipher — The Vigenère cipher is a polyalphabetic substitution cipher that uses a keyword to apply different Caesar shifts across a message. It is usually taught with the tabula recta and is vulnerable to frequency-based attacks.
• Hashes, Authentication, and Privacy Protocols

  • Cryptographic hash function — maps arbitrary input to a fixed-length digest; properties: deterministic, fast to compute, preimage resistant, collision resistant; examples: SHA-256 (256-bit), SHA-3, MD5 (128-bit, broken).

  • Digital signature — hash of a message encrypted with the sender’s private key; recipient verifies with public key; ensures authenticity and non-repudiation.

  • TLS/SSL — Transport Layer Security; cryptographic protocol securing web (HTTPS) and other traffic; combines asymmetric exchange with symmetric session keys.

  • Message authentication code (MAC) — keyed checksum ensuring integrity and authenticity; HMAC uses a cryptographic hash (e.g., HMAC-SHA256); distinct from a digital signature (which uses asymmetric keys).

  • Zero-knowledge proof — interactive protocol where a prover convinces a verifier they know a secret without revealing the secret; properties: completeness, soundness, zero-knowledge; modern SNARKs enable non-interactive variants; used in privacy-preserving cryptocurrencies (Zcash). The proof system is the basis for modern SNARKs and STARKs and for privacy-preserving cryptocurrency systems such as Zcash.

  • Cryptographic hash functions

    • MD5 — MD5 is a cryptographic hash function introduced by Ron Rivest that produces a 128-bit digest. It is widely used for checksums, but its collision resistance has been broken.
• cryptography — Cryptography is the field of secure communication that studies ciphers, encryption, and other methods for protecting messages. Its standard clues include RSA, Diffie-Hellman, elliptic curves, one-time pads, and assumptions about discrete logarithms and factoring.

  • AES — AES is the NIST-selected symmetric block cipher that replaced DES as an official U.S. encryption standard in 2001. It is based on the Rijndael design, uses 128-, 192-, and 256-bit keys, and applies repeated substitution and permutation steps, including the SubBytes transformation built around arithmetic in GF(2^8).

  • cipher — A cipher is an encryption algorithm for transforming plaintext into ciphertext; in classical cryptography it often refers to substitution ciphers such as Caesar, Playfair, and Atbash. Examples of modern encryption algorithms include AES, whose steps include SubBytes, ShiftRows, and MixColumns, and RSA, which relies on factoring large composites. Rotor machines such as the British Mercury machine also implemented ciphers.

  • ciphers — Ciphers are systems for disguising messages, ranging from classical substitution schemes to modern encryption methods. They include famous examples such as Caesar-style substitution, the Vigenère cipher, Enigma, and RSA.
    • Dorabella cipher — The Dorabella cipher is Elgar’s unsolved private cipher sent to his friend Dora Penny. It is written as a string of arched squiggles in different orientations and remains undeciphered.
  • Classical ciphers
    • Caesar cipher — The Caesar cipher is a substitution cipher that shifts each letter by a fixed number of places in the alphabet. It is named for Julius Caesar, who reportedly used it for military messages with a shift of three.
  • discrete logarithm problem — The discrete logarithm problem asks for the exponent x such that b equals a to the x in a finite group. It underlies ElGamal, Diffie-Hellman, and elliptic-curve cryptography, and index calculus attacks search for relations to solve it more quickly.
    • discrete logarithm — The discrete logarithm problem asks for the exponent needed to express one group element as a power of another. It is central to Diffie-Hellman, ElGamal, and related public-key cryptography because it is believed to be computationally hard.

  • elliptic curve cryptography — Elliptic curve cryptography is a public-key system built on arithmetic over points on elliptic curves, where the hard problem is the discrete logarithm. It achieves strong security with relatively short keys and underlies elliptic-curve variants of Diffie-Hellman and DSA.

  • encryption — Encryption is the process of converting information into a form that only intended recipients can read, often using public-key systems such as RSA. Related clues include ciphers, hash functions, and historical machines like Enigma and Purple.

  • integer factorization — The problem of expressing an integer as a product of prime powers or smaller integers. It is central to RSA cryptography because it is hard to do quickly for large numbers. Classical methods include trial division, Pollard’s rho, the quadratic sieve, and the general number field sieve; Shor’s algorithm gives a polynomial-time quantum method.

  • keys — Keys are cryptographic values used to encrypt, decrypt, and authenticate data, as in RSA and Diffie-Hellman. The word also names database identifiers and the everyday objects that the Locke family finds in the fantasy series mentioned in the clues.

  • Merkle structures
    • Ralph Merkle — Ralph Merkle is known for Merkle trees and for the Merkle-Damgård construction of hash functions. His name also appears in hash-tree structures used to organize Bitcoin transactions.

  • one-way functions — One-way functions are easy to compute but hard to invert, and their existence would imply P is not equal to NP. They underlie cryptographic constructions such as hash functions, trapdoor permutations, pseudorandom generators, and commitments.

  • Public key encryption — Public-key encryption uses a pair of keys, one for encryption and one for decryption, and underlies most modern asymmetric cryptosystems. Diffie-Hellman belongs to this broader class, as does RSA.

  • Public-key cryptography — Public-key cryptography uses a matched pair of keys, one public and one private, for encryption and decryption. Diffie-Hellman and RSA are standard examples, and the system is valued for authentication and secure message exchange.
    • public-key cryptosystem — A public-key cryptosystem is one in which encryption information may be published openly, but decryption requires private information held by the recipient. RSA is the classic example, and later work such as Gentry’s bootstrapped scheme extended the idea to fully homomorphic encryption.
  • public-key cryptosystems

    • ElGamal encryption scheme — The ElGamal encryption scheme is a public-key cryptosystem named for Egyptian cryptographer Taher ElGamal. Its security relies on the hardness of discrete logarithms or the Diffie-Hellman problem in a cyclic group.

    • RSA cipher — RSA is a public-key cryptosystem built from two large primes and a number relatively prime to their product. Its security relies on modular arithmetic and the difficulty of factoring the composite modulus.

  • quantum cryptography — Quantum cryptography uses quantum states, often photons and their polarization, to distribute keys securely. Its security comes from the fact that eavesdropping disturbs the system and can be detected.

  • steganography — Steganography is the practice of hiding a message inside another object so that outsiders do not know a message exists. Common examples include least-significant-bit image encoding, invisible ink, and secret data hidden in headers or spectrograms.

  • symmetric-key cryptography — Symmetric-key cryptography uses the same secret key for both encryption and decryption. Block ciphers such as AES, DES, Twofish, and Blowfish are examples of this approach, and HMACs are commonly used for authentication within it.
    • Data Encryption Standard — The Data Encryption Standard is a classic symmetric-key block cipher that became a U.S. national standard in 1976. It uses a 56-bit key and 16 Feistel rounds, later became vulnerable to brute-force attack, and was eventually superseded by stronger standards such as triple DES and AES. It was also the subject of long-running debate over possible NSA influence on its design.

  • Vigenere cipher — The Vigenere cipher is a polyalphabetic substitution cipher that shifts letters according to a repeating keyword. It was developed in the 16th century and later broken by Babbage and Kasiski.

  • one-time pad — A one-time pad is a cryptographic scheme that achieves perfect secrecy when the key is truly random, as long as it is never reused. It is often described as the strongest mathematically possible cipher and is closely related to the Vernam cipher.

Computer Security and Privacy

• Bash vulnerabilities
  • Shellshock — Shellshock was a critical Bash vulnerability announced in 2014 that allowed attackers to run commands through vulnerable CGI and web-facing systems. The bug affected the Bourne Again Shell and was considered by some experts even more serious than Heartbleed.
• computer security

  • overflow — Overflow is the error state in which data or arithmetic exceeds a system’s limits, producing problems like buffer overflow, stack overflow, and integer overflow. Programming exploits such as stack smashing and return-to-libc rely on it, which is why the name of Stack Overflow fits the classic memory-safety vulnerability.

  • authentication — Authentication is the process of verifying the identity of a user or sender, often strengthened by two-factor methods. It appears in cryptography alongside protocols such as Kerberos and with tools like HMACs that resist length-extension attacks.
    • passwords — Passwords are secret strings used to authenticate logins, and they are often stored only as hashes rather than in plain text. Clues about them include rainbow tables, salt, brute-force cracking, and one-time password devices such as YubiKeys.

  • CAPTCHA — CAPTCHA is the automated challenge-response test used to tell computers and humans apart. It often appears as distorted text or images designed to resist OCR and block spam bots.

  • Denial-of-service attacks
    • denial of service attack — A denial-of-service attack overwhelms a computer or network so legitimate users cannot access its resources. Distributed denial-of-service attacks do the same thing by coordinating traffic from many sources, and SYN flooding is a related variant that leaves servers stuck with half-open connections.

  • Hacker — A hacker is someone who explores or pushes the limits of a computer system, often with strong technical skill and problem-solving ability. The term can also refer to malicious intruders, often contrasted with white-hat or black-hat behavior.

  • hacking — Hacking is the act of finding and exploiting weaknesses in a computer system or network, often to gain unauthorized access. It is closely associated with bypassing security and breaking into machines, whether in fiction or real-world cybercrime.

  • malware — Malware is malicious software designed to disrupt, damage, or gain unauthorized access to computer systems. Worms, trojans, ransomware, and viruses are common forms of malware.
    • computer virus — A computer virus is a form of malware that spreads by infecting other programs or files. Well-known examples include Melissa, Cryptolocker, and Stuxnet, and closely related malware can include worms and rootkits.
• Digital rights management — Digital rights management is access-control software used to restrict copying or use of copyrighted works. It became controversial in contexts such as CD protection schemes and games like Spore, and is often abbreviated DRM.
  • copy protection — Copy protection is the set of technical measures used to prevent unauthorized copying or use of software, games, or other digital media. Examples include the NES 10NES system, Sega’s TMSS, dongles, and disc-rootkit schemes such as Sony’s notorious CD protection.
    • Anti-piracy measures — Anti-piracy measures are built-in game protections or fake screens designed to frustrate illicit copies. Famous examples include bizarre punishments, sudden difficulty spikes, and false error messages that target pirated versions.
• memory safety vulnerabilities
  • buffer overflow — A buffer overflow is a security flaw in which data are written past the end of an array or other storage area, corrupting memory. It is a classic source of code-injection attacks and is often discussed alongside stack smashing, canaries, and address-space randomization.
• Password attacks
  • Password Cracking — Password cracking is the attempt to recover a hidden password or key from stored or intercepted data, often by brute force or dictionary attack. Common countermeasures include salts, stretching, and shadow-file protection, while tools such as John the Ripper and Cain and Abel are often associated with the task.
• cybersecurity
  • companies
    • CrowdStrike — CrowdStrike is the cybersecurity company whose faulty Falcon Sensor update caused a massive worldwide Windows outage in July 2024. The incident was tied to Channel File 291 and briefly made the firm notorious far beyond the security industry.

Software, Interfaces, and Applications

Connect software design and interfaces to application domains.

Software Engineering

Software engineering applies systematic methods to building, operating, and changing software under constraints of cost, schedule, quality, safety, and security. The IEEE Computer Society’s SWEBOK Guide V4.0 (2024) spans requirements, architecture, design, construction, testing, operations, maintenance, configuration management, management, process, models and methods, quality, security, professional practice, and economics.¹¹

• Design, Development Methods, and Maintenance

  • Origins of the discipline — the NATO Software Engineering Conference at Garmisch, Germany, in October 1968 promoted engineering discipline for software development. Participants described chronically late, over-budget, and unreliable projects as a “software crisis.”¹²

  • Requirements and abstraction — requirements specify what a system must do and its constraints; interfaces state what a component provides while hiding implementation details. Modularity helps changes remain local. Version control records changes so collaborators can review and recover earlier versions.¹³

  • Quality attributes — functional requirements state behavior, while quality attributes such as performance, security, reliability, usability, and maintainability constrain how well that behavior must be delivered. Because requirements are often incomplete, conflicting, or changing, elicitation, validation, prioritization, and traceability continue throughout development.

  • Life-cycle models — plan-driven models sequence requirements, design, implementation, verification, and maintenance, whereas iterative and incremental models deliver working increments and revise them with feedback. Winston Royce’s 1970 paper, commonly cited as the source of the “waterfall,” called a single linear pass risky and recommended feedback and repeated work; the spiral model organizes iterations around risk.¹⁴

  • Agile methods and DevOps — the Manifesto for Agile Software Development, written at Snowbird, Utah, in February 2001, values individuals and interactions, working software, customer collaboration, and responding to change over processes and tools, comprehensive documentation, contract negotiation, and following a plan, while affirming that the latter still have value. Scrum and Extreme Programming are common agile approaches; DevOps extends short feedback loops into deployment and operations through automation, continuous integration and delivery, and monitoring.¹⁵

  • Architecture and modular design — software architecture defines major components, their responsibilities, interfaces, and deployment. David Parnas’s 1972 Communications of the ACM paper argued that modules should hide design decisions likely to change, the principle of information hiding. Low coupling between modules and high cohesion within them keep changes local; design patterns record reusable solutions to recurring design problems.¹⁶

  • Configuration management and release — version control, dependency management, reproducible builds, and release records identify which source, libraries, and settings produced a deployed system. Without them, defects are hard to reproduce, audit, or roll back.

  • Maintenance, evolution, and technical debt — long-lived software changes to correct defects, adapt to new platforms, and add capabilities. Ward Cunningham’s 1992 technical-debt metaphor compares expedient code to borrowing: it can speed delivery, but unrepaid shortcuts make later change more expensive. Refactoring improves internal structure without changing external behavior.¹⁷

  • Estimation and team scale — Fred Brooks’s The Mythical Man-Month (1975) argued from IBM OS/360 experience that adding people to a late project can make it later, because newcomers need time to become productive and communication overhead grows. His 1986 essay “No Silver Bullet” argued that no single technology or management technique promised an order-of-magnitude improvement within a decade, because much of software’s complexity is essential rather than accidental.¹⁸

  • software development — Software development is the process of creating and maintaining programs, from planning and coding to testing and deployment. It is commonly associated with the waterfall, agile, spiral, and DevOps approaches, as well as version control and collaborative tooling.

    • bus factor — The bus factor is the minimum number of team members who can disappear before a project stalls because too much knowledge is concentrated in too few people. The term is associated with software-maintenance analyses and estimators that try to measure project vulnerability to key-person loss.

    • Fred Brooks — Fred Brooks wrote The Mythical Man-Month and is remembered for Brooks’s law, the warning that adding manpower to a late software project makes it later. His essays on software design also stress communication, organization, and the limits of silver-bullet solutions.
      • The Mythical Man-Month — Fred Brooks’s The Mythical Man-Month is a classic essay collection on software engineering. Its title alludes to Brooks’s Law: adding programmers to a late project usually makes the schedule slip further, a lesson drawn from his work on an ALGOL compiler.

    • open-source software — Open-source software is software whose source code is publicly available to view, modify, and redistribute. The term is closely associated with the free software movement and with development models described in The Cathedral and the Bazaar.

    • refactoring — Refactoring is the process of improving the structure of existing code without changing its external behavior. It often means breaking messy programs into cleaner, smaller units and is a common step in test-driven development and general software maintenance.

    • spaghetti code — Spaghetti code is software with tangled control flow, often marked by heavy use of GOTO statements and global variables. The nickname compares the code’s structure to strands of spaghetti that are hard to untangle.
  • software development models
    • waterfall model — The waterfall model is the classic sequential software development process in which requirements, design, implementation, testing, and maintenance proceed in order. It is associated with Winston Royce and often contrasted with later iterative approaches such as the spiral model and agile development.
  • Agile software development
    • Extreme Programming — Extreme Programming is an agile software-development method that emphasizes communication, simplicity, feedback, and courage. It favors practices such as pair programming, frequent releases, and extensive unit testing.
  • software development methodologies
    • Agile — Agile is an iterative software development approach emphasizing flexibility, customer collaboration, and working software over heavy documentation. It is associated with the Agile Manifesto, Scrum, stand-up meetings, continuous adjustment to changing requirements, and methods such as extreme programming.
  • Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides
    • Design Patterns: Elements of Reusable Object-Oriented Software — Design Patterns: Elements of Reusable Object-Oriented Software is the classic software engineering book by the Gang of Four. It organizes reusable object-oriented solutions into creational, structural, and behavioral patterns.
  • Build automation
    • make — make is the Unix build utility that reads Makefiles to decide how to compile targets and manage dependencies. It uses rules, variables such as CC and CFLAGS, and special targets like clean and check.
  • version control

    • commit — In version-control systems, this command records staged changes as a new revision, often after git add and before git push. Outside computing, the same word can mean to place someone in a mental hospital or to pledge oneself to an action.

    • branches — Branches are woody plant structures that grow from stems or trunks and support lateral growth. They are also a standard metaphor in computer science, where branches represent alternate lines of development in version control.

    • merging — Merging is the process of combining branches or commit histories, including when closing a Git pull request. The same term also names the recombination step in merge sort, which repeatedly divides and then combines subarrays.

  • Software maintenance
    • Patches — In ecology, patches are discrete habitat units that can be studied as mosaics in landscape dynamics. In computing, patches are code updates released to fix bugs or security holes.
  • software design patterns
    • creational patterns
      • Singleton Pattern — The singleton pattern is a creational software design pattern that restricts a class to one instantiated object. It is commonly implemented with a private constructor and a static reference to the sole instance.

    • decorator pattern — The decorator pattern is a structural software design pattern that adds behavior to an existing object by wrapping it in another class. It is used as an alternative to subclassing when new functionality needs to be layered on dynamically.

    • Design Patterns — Design patterns are reusable software solutions such as Singleton, Builder, Abstract Factory, Facade, and Adapter. They are the subject of the Gang of Four book Design Patterns: Elements of Reusable Object-Oriented Software, and include Observer-style event handling patterns.
      • singleton — A singleton is a design pattern that restricts a class to one instance, often through a private constructor and controlled access method. The pattern is widely used for shared objects like loggers and thread pools, and the term also means a set with one element.

    • Facade — Facade can refer to William Walton’s 1926 setting of Edith Sitwell’s poems for narrator and chamber ensemble. It also names the software design pattern that presents a simple unified interface to a more complex set of underlying interfaces.

    • MVC — MVC is the model-view-controller design pattern, which separates data, user interface, and control logic. It is widely used in graphical and web applications, including Ruby on Rails, and is sometimes adapted into presenter-based variants.
  • SOLID principles
    • Liskov substitution principle — The Liskov substitution principle says a subtype should be usable anywhere its supertype is expected. It is one of the key object-oriented design principles associated with Barbara Liskov and is often stated in terms of preserving provable properties across subtypes.
  • programming methodology
    • literate programming — Literate programming is Donald Knuth’s approach of mixing explanatory prose with source code so that the human-readable document is primary. Its code is commonly woven into documentation and tangled back into executable programs, with WEB and CWEB as classic systems associated with it.
• Testing, Verification, and Professional Practice
  • Software testing — unit tests examine individual components, integration tests examine their interactions, and system tests examine complete behavior. Regression tests check that a change preserves required behavior. Passing tests demonstrates the cases checked; it does not prove a program has no defects. Reviews and static analysis can detect problems without executing the program.¹³ It is commonly supported by frameworks such as xUnit, and by mocks or stubs for isolating components and assertions for checking expected behavior. Test-driven development is the practice of writing tests before the code they exercise; other commonly used test types include beta and stress tests.

    • beta testing — Beta testing is the stage of software release in which outside users test a near-complete build in real-world conditions before commercial release. It typically comes after internal testing and before the release candidate stage.

    • testing — Testing is the software-development stage that checks whether code works, including unit testing and beta testing. Agile methods often do it continuously, while tools like JUnit support automated checks and fuzzing uses random data.

    • Unit testing — Unit testing is software testing that checks small pieces of code in isolation. It is commonly associated with test-driven development and extreme programming.

    • unit tests — Unit tests are small automated tests that check individual pieces of code, often using mocks or fakes. They are commonly written with frameworks that support setup and teardown methods and are measured by code coverage.

    • Black Box — A black box is a system described only by its inputs and outputs, with its internal workings left opaque. The term also names the orange flight recorder carried by aircraft, despite the common nickname.

  • Verification beyond testing — inspections, static analysis, model checking, and mathematical proof can establish properties for all executions within a model, whereas tests sample particular cases. Formal methods are applied selectively, most often where failures are costly, because precise specifications and proofs require substantial expertise.

  • Failure analysis — software failures often involve specifications, assumptions, reuse, and review practices as well as code. Ariane 5’s first flight on 4 June 1996 was lost when its inertial reference software, essentially the Ariane 4 design, raised an unhandled exception in an alignment function that served no purpose after lift-off: a 64-bit floating-point value related to horizontal velocity was too large to convert into a 16-bit signed integer. The inquiry board found that the specifications and equipment tests had not included Ariane 5 trajectory data.¹⁹

  • Professional ethics — the Software Engineering Code of Ethics and Professional Practice, approved by the IEEE Computer Society and ACM in 1999, organizes obligations under eight principles: public, client and employer, product, judgment, management, profession, colleagues, and self. Security, privacy, accessibility, and safety requirements affect people well beyond a development team.²⁰

  • Evidence and open questions — the effectiveness of practices such as pair programming, test-driven development, or a particular process model depends on team, domain, and context, so evidence from one setting transfers imperfectly. AI-assisted code generation raises unresolved questions about verification, security, licensing, maintainability, and accountability.

  • debugging — Debugging is the process of finding and fixing errors in software or a computer program. Common techniques include breakpoints, print statements, stack traces, examining core dumps or variable values during execution, and tools like GDB. The term is famously linked to Grace Hopper’s moth anecdote and later informal methods like rubber duck debugging.

  • program verification
    • loop invariants
      • Loop invariant — A loop invariant is a condition that remains true throughout the execution of a program loop. They are used to prove the correctness of loop logic in computer programs.
  • Programming errors

    • run-time errors — Run-time errors are programming errors that occur while a program is actually executing. They do not stop compilation, but they can cause a program to abort during execution, as with a segmentation fault or floating-point exception.

    • segmentation fault — A segfault, or segmentation fault, is a program crash caused by invalid or illegal memory access, such as dereferencing a null or dangling pointer. Common causes include bad pointers, double freeing memory, and stack overflows. It often produces a core dump and may exit with signal 11.

  • software bugs

    • computer bugs — Computer bugs are defects or errors in software that can cause programs to fail or behave unexpectedly. The term is famously linked to Grace Hopper’s anecdote about a moth found in the Mark II computer.

    • computer bug — A computer bug is a flaw or glitch in a computing system that causes it to misbehave. The term is often linked to Grace Hopper and to the famous story of an actual moth found in a machine.

• computer systems
  • fault-tolerance — Fault tolerance is the ability of a system to keep operating correctly even when one or more components fail.
• Typesetting systems
  • TeX — Donald Knuth’s typesetting system for mathematical and scientific documents, later extended by LaTeX for easier formatting. It is a standard tool for scientific writing and is known for its precise box-and-glue page layout model; related packages include TikZ and amsmath.
• Software deployment
  • containers — Containers are isolated execution environments used in modern software deployment, often managed by Kubernetes, Docker, and OpenShift. The same word also refers to large rectangular shipping boxes used in intermodal freight transport.

Human-Computer Interaction

Human-computer interaction (HCI) studies how people use, experience, and are affected by interactive systems, drawing on computer science, psychology, design, and the social sciences. The history of graphical interfaces is covered in Computing History.²¹

• Usability and accessibility — usability concerns how people complete tasks with a system; accessibility addresses barriers faced by people with disabilities. User research, prototypes, and task-based evaluation reveal problems that technical correctness alone misses. Keyboard operation, meaningful text alternatives, clear labels, and visible focus help people use the same content through different forms of input and perception.²²

• Human-centered design — design proceeds through repeated cycles of understanding users and contexts, specifying needs, creating designs, and evaluating them with people. Designers are not their users, so interviews, surveys, observation, personas, journey maps, and needs assessments help teams test their own assumptions.²¹

• Usability attributes — Jakob Nielsen describes usability through learnability, efficiency, memorability, errors, and satisfaction, and distinguishes it from utility, whether a system provides the functions people need. A useful system needs both.²³

• Perception, cognition, and movement — attention, perception, memory, and recognition shape interaction; interfaces that let people recognize options generally demand less memory than those requiring recall. Fitts’s law, derived from Paul Fitts’s 1954 experiments on aimed movement, predicts that pointing takes longer as target distance increases and target width decreases.²⁴

• Affordances, signifiers, and mental models — the psychologist James J. Gibson coined “affordance” in 1977 for the action possibilities an environment offers. Don Norman adapted the idea for design in The Design of Everyday Things (1988) and later emphasized signifiers, perceivable cues that show which actions are possible. Feedback and consistent structure help users form accurate mental models of system state.²⁵

• Interaction styles — command languages, menus, forms, direct manipulation, windows and pointing, touch and gesture, voice, and virtual or augmented reality distribute effort differently among recall, recognition, precision, and speed. Suitability depends on task, expertise, setting, and ability rather than on one universally superior style.

• Prototyping — sketches and paper prototypes explore concepts cheaply, while interactive high-fidelity prototypes test detailed flows, timing, and visual design. Rough prototypes tend to invite critique of the concept; polished ones can narrow feedback to surface details.

• Heuristic evaluation and walkthroughs — in heuristic evaluation, which Jakob Nielsen developed with Rolf Molich in 1990, evaluators inspect an interface against principles; Nielsen’s ten heuristics, refined in 1994, include visibility of system status, error prevention, and recognition rather than recall. Cognitive walkthroughs step through tasks from a new user’s perspective. Inspection is fast but can miss problems that only representative users reveal.²⁶

• Usability testing and experiments — representative users attempt realistic tasks while researchers observe success, errors, time, and think-aloud comments. Nielsen recommends frequent small iterative tests, often about five users per round, to find major problems; estimating differences between designs requires controlled experiments or A/B tests with adequate samples.²³

• Accessibility standards and assistive technology — the W3C Web Content Accessibility Guidelines (WCAG) 2.2 organize testable success criteria under four principles, perceivable, operable, understandable, and robust, with conformance levels A, AA, and AAA. Screen readers, switch access, captions, magnification, and voice control depend on content that exposes structure and meaning to software; conformance is a baseline, and testing with disabled users can reveal barriers a checklist misses.²⁷

• Inclusive and cross-cultural design — ability, age, language, culture, literacy, and experience shape how people interpret interfaces. Internationalization, universal design, and evaluation with diverse participants reduce the risk that findings from convenient samples fail to generalize.²¹

• Collaboration and social computing — computer-supported cooperative work and social computing study synchronous and asynchronous communication, online communities, social media, and shared tools, where coordination, awareness of others, and community norms matter alongside individual efficiency.²¹

• Values, persuasion, and deceptive design — value-sensitive design identifies direct and indirect stakeholders and the values a system affects. Persuasive design can support goals such as health, but manipulative “dark patterns” disguise advertising, obstruct cancellation, bury key terms, or trick people into sharing data; a September 2022 U.S. Federal Trade Commission staff report documented such practices in e-commerce, cookie banners, children’s apps, and subscriptions.²⁸

• History and current directions — Douglas Engelbart’s 9 December 1968 demonstration of the NLS system showed a mouse, hypertext, windows, and real-time collaboration; later graphical interfaces made such ideas widespread. Mobile, ubiquitous, and AI-based systems extend HCI to automation, explanation, privacy, trust, and appropriate reliance.²⁹

• computer interfaces
  • What You See Is What You Get — What You See Is What You Get is the standard expansion of the computing acronym WYSIWYG. It refers to software that shows text or page layout on-screen as it will appear when printed or published.
• virtual reality — Virtual reality is a computer-generated immersive environment experienced through headsets, sensors, and screens. It is used in games, training simulators, and art installations such as works made for Oculus Rift.
  • Oculus VR — Oculus VR is the virtual reality company behind the Rift headset and the Samsung Gear VR collaboration. It was acquired by Facebook after an early Kickstarter-era rise and became a major gaming-focused VR brand.
• automatic identification
  • barcodes — Barcodes are machine-readable patterns used for retail scanning and for labeling individual cells or samples in sequencing workflows. They also appear in projects such as QR codes, UPC scanning, and other technologies that use short identifying sequences or tags.
• Microsoft Office
  • PowerPoint
    • Microsoft PowerPoint — Microsoft PowerPoint is the slideshow program in Microsoft Office that became the standard presentation software rivaled by Keynote and Prezi. Edward Tufte famously attacked its “cognitive style,” arguing that it encourages bullet-point simplification and poor information transfer.
• Spreadsheet software
  • Microsoft Excel — Microsoft Excel is the spreadsheet program associated with PivotTables, VBA, and the common use of INDEX-MATCH in place of VLOOKUP. It is also notorious for data-conversion mistakes, including misreading gene names or turning numbers into dates.

Computer Graphics

• Computer graphics — methods for representing geometry, materials, lighting, and cameras to construct images. A scene description is converted into an image through rendering. The Cornell box provides a standard scene for comparing calculated light transport with measured photographs.³⁰ It is a subfield of computer science devoted to rendering and synthesizing images. Common techniques include ray tracing, rasterization, and shading, and a standard benchmark is the Utah teapot.

  • Ambient lighting — Ambient lighting is the uniform background illumination used to simulate indirect light in a scene. It is a basic term in computer graphics and rendering.

  • anti-aliasing — Anti-aliasing is a graphics technique used to reduce jagged edges when rendering images at lower resolution. It works by smoothing lines or polygons through intermediate shading or sampling to counter aliasing artifacts.
    • spatial anti-aliasing — Spatial anti-aliasing is the computer-graphics technique used to smooth jagged edges in rasterized images. It reduces staircasing and other sampling artifacts by blending neighboring pixel values along lines and boundaries.

  • Bezier curves — Bézier curves are parametric curves developed by Pierre Bézier for Renault automobile design. They are defined using Bernstein polynomials and control points; in the simplest cubic form, they use two endpoints and two control points. They remain inside the convex hull of those points. de Casteljau’s algorithm is used for stable evaluation. They are foundational in computer graphics, scalable vector graphics, and font rendering.

  • Blitting — Blitting is the graphics technique of copying blocks of image data from one surface or buffer to another. It is used in game design to draw images by transferring pixel data into display memory.

  • clipping
    • geometric clipping — This graphics operation removes objects or portions of objects that fall outside the view volume before rasterization. Common examples include Cohen-Sutherland clipping for lines and Greiner-Hormann clipping for polygons.
  • depth buffer
    • Z-buffer — A z-buffer is a depth buffer used in computer graphics to store pixel depth values. It is used to decide which object is visible when multiple surfaces overlap in 3D rendering.

  • dithering — Dithering is the deliberate use of noise or dot patterns to simulate colors or preserve detail when reducing image or audio resolution. In graphics it can help approximate out-of-palette colors, and in audio it reduces truncation distortion.

  • GPU — A GPU is a graphics processing unit originally built to render images, and modern ones are used for parallel computation with APIs like CUDA, OpenCL, and Vulkan. Their many-core design makes them useful for machine learning, cryptocurrency mining, and shader programs. These devices are the hardware behind many graphics cards and video cards, including Nvidia products used for CUDA-based computing. They can also contain specialized shader units and dedicated tensor or ray-tracing cores.

  • morphing — In Animorphs, morphing is the ability to transform into another animal using an Escafil cube and a two-hour time limit. In computer graphics, morphing is a smooth image transformation created by blending one shape or image into another.

  • raster
    • The RASTER — Raster refers to the scan-line pattern used in displays, the no-signal background left when the applied signal is removed. It is a basic term in video and image rendering.

  • rasterization — Rasterization is the process of converting vector graphics or other geometric descriptions into pixels on a screen. It is closely related to antialiasing and line-drawing methods such as Bresenham’s algorithm and the midpoint circle algorithm.

  • ray tracing — Ray tracing is a computer graphics rendering technique that follows geometric rays to simulate light and reflections in an image. It is slower than scan-line methods but can produce realistic illumination effects, especially in recursive variants such as Whitted-style ray tracing.

  • Rendering — Rendering is the computer-graphics process of generating an image from scene data or from 2D or 3D models, using rasterization, ray tracing, or other lighting models; it can also be done in real time, as with Blender’s EEVEE engine. The term can also mean converting markup or code into a visible visual format.
    • image rendering — Image rendering is the process of converting graphics into pixels, whether by rasterization, scanline methods, or ray tracing. Common technical clues include z-buffers, anti-aliasing, and algorithms such as Bresenham’s and Wu’s.
  • Rendering techniques
    • cel-shading — Cel-shading is a 3D rendering style that makes objects look flatter and more cartoon-like by simplifying lighting and color gradients. It is associated with games such as Jet Set Radio, Viewtiful Joe, Okami, and The Wind Waker.

  • shaders — Shaders are programmable GPU programs used in graphics pipelines, originally developed to control effects such as lighting and later expanded into vertex and fragment stages. Vertex shaders transform geometry through the pipeline, while fragment shaders determine the color of individual pixels.

  • shading — Shading is a computer graphics technique for assigning color and light levels to surfaces and pixels. Common methods include flat, Gouraud, and Phong shading, and programmable shaders perform related work in graphics pipelines.

  • sprites — Sprites are small bitmap-based images used to represent moving objects or characters in computer graphics and video games. They are commonly layered over a background and animated as independent two-dimensional graphic elements.

  • Texture mapping — Texture mapping is the computer graphics technique of applying a two-dimensional image to the surface of a three-dimensional object. Edwin Catmull pioneered the process to make rendered objects carry detailed surface patterns.

  • vector graphics — Vector graphics are images built from geometric primitives such as points, lines, curves, and polygons. Because they are defined mathematically rather than as pixels, they can be scaled without losing resolution and are common in illustration and GIS work.

• Rasterization and ray tracing — rasterization projects geometric primitives, often triangles, onto an image and determines which samples they cover. Ray tracing finds intersections between rays and scene geometry; secondary rays can test shadows or follow reflections. Both approaches still need shading rules to determine the resulting colors.³⁰

• Phong reflection and shading — the Phong reflection model combines ambient, diffuse, and specular contributions; the specular exponent controls highlight concentration. Phong shading interpolates surface normals across a polygon and evaluates lighting at image samples. The reflection model and interpolation method are distinct, although they share Bui Tuong Phong’s name.³⁰

• 3D computer graphics
  • voxels — Voxels are three-dimensional pixels used to model objects with volume, density, and composition rather than flat surfaces. They are less efficient than polygons for shapes with lots of empty space, and the marching cubes algorithm is a classic method for extracting meshes from them.

• collision detection — Collision detection is the computational task of determining whether objects intersect or touch. It is widely used in physics engines, video games, and spatial indexing, often with bounding boxes, quadtrees, or algorithms such as GJK and separating-axis tests.

• Color model
  • red, green, blue — In quantum chromodynamics, quark color charge comes in three types: red, green, and blue. The same trio also names the additive primaries used to form colors on a pixel display.
• Digital image processing
  • digital images — Digital images are graphical data stored as pixels, with formats such as PNG and JPEG and representations ranging from bitmaps to vector graphics that are rasterized for display. They are the input type for convolutional neural networks and are often accompanied by metadata such as Exif tags.
    • continuous tone — A continuous-tone image has smoothly varying shades rather than a limited dot pattern. Grayscaling can be used to convert certain black-and-white images into computer graphics of this kind.
• Digital imaging
  • pixel — A pixel is the smallest image-forming unit of a digital display, also described as a picture element or single dot. Higher-resolution screens contain more pixels per unit area.
• raster graphics

  • bitmap — A bitmap is a raster image stored as separate color values for each pixel. BMP is a common abbreviation for this format, and GIF, JPEG, and PNG are often discussed alongside it in image compression contexts.

  • pixels — Pixels are the tiny square picture elements that make up raster images and digital displays. They are the smallest units of raster images and are used to describe display resolution. In standard digital displays, each pixel is subdivided into red, green, and blue components. Pixels are the units manipulated by anti-aliasing, compression, tracking pixels, and pixel art.

• Rendering software
  • RenderMan — RenderMan is Pixar’s proprietary 3D rendering software, long used to generate the studio’s films and later released in a free noncommercial version. It has also appeared in major effects-heavy productions such as Jurassic Park and The Lord of the Rings.
• Image editors
  • Photoshop — Adobe’s image-editing program, developed by the Knoll brothers and later used to alter or composite photographs. It is known for alpha compositing, layer masks, marquee selections, the spot healing tool, and newer object-selection features, and its name has become a generic verb for digitally manipulating images.

Artificial Intelligence

• chess engines
  • Stockfish — Stockfish is a powerful open-source chess engine widely used for analysis by major chess sites and commentators. Its name also comes from a Scandinavian dried-cod food, though the program is far better known than the dish.
• Computational knowledge engines

  • **Wolfram

    Alpha** — Wolfram Alpha is a computational knowledge engine that can answer mathematical and factual queries directly. It is named for Stephen Wolfram, the computer scientist behind Mathematica.

• computer algebra systems
  • Mathematica — Mathematica is the computer algebra system created by Stephen Wolfram and released in 1988 by Wolfram Research. It is known for symbolic manipulation and is often mentioned as a competitor to MATLAB and Maple.
• Computer chess
  • Deep Junior — Deep Junior is the Israeli chess program developed by Amir Ban and Shay Bushinsky with help from Boris Alterman. It drew Garry Kasparov in 2003 and is associated with the famous bishop sacrifice on h2 in its match against him.
• Evolutionary algorithms
  • genetic algorithm — A genetic algorithm is a biology-inspired optimization and search method modeled on natural selection. It evolves a population of candidate solutions by scoring them with a fitness function and favoring better bitstrings or other chromosome-like encodings for later generations. Standard operators include selection, crossover, mutation, and recombination; common selection schemes include tournament and roulette-wheel selection. It is often discussed in terms of schema and building-block ideas and is used for hard optimization problems such as the traveling salesman problem.
• image processing
  • Edge detection — Edge detection is the image-processing task of finding boundaries between objects in a picture. Methods for it include the Sobel and Prewitt operators, Canny’s algorithm, and the Hough transform.
• Maze solving
  • solving a maze — Solving a maze is the task of finding a continuous path from an entrance to a goal without getting trapped by dead ends. It appears in studies of learning and navigation and in familiar examples such as a cornfield labyrinth.
• natural language processing

  • machine translation — Machine translation is the automatic conversion of text from one language into another by computer. Clues often mention BLEU, IBM statistical models, parallel corpora, and the ALPAC report’s setback for the field.

  • bag-of-words model
    • Bag-of-words — The bag-of-words model represents text by counting word frequencies rather than preserving word order. It is a common baseline for tasks such as classifying emails, tweets, and other short texts.
  • Spell Checker — A spell checker is a word-processing tool that compares words against a dictionary and flags probable misspellings. Simpler versions rely on edit-distance checks, while later systems were added to browsers and often work alongside grammar checkers.
• Optimization algorithms

  • ant colony optimization — Ant colony optimization is a metaheuristic inspired by the way ants collectively find efficient paths to food. It uses pheromone trails on graph edges to approximate shortest-path solutions and was proposed by Marco Dorigo.

  • simulated annealing — Simulated annealing is a probabilistic optimization method modeled on cooling metal, using a gradually decreasing temperature to move toward a low-energy solution. It accepts worse states early on with some probability, then becomes more restrictive as the schedule cools, making it useful for searching large solution spaces.

• optimization problems
  • traveling salesman problem — The traveling salesman problem asks for the shortest route, or minimum-weight Hamiltonian cycle, that visits each city or node exactly once and returns to the start. It is a classic NP-hard optimization problem; the decision version is NP-complete. Common variants include metric and Euclidean TSP. Notable methods and results include the Held-Karp dynamic program and bound, Christofides’s approximation algorithm, nearest-neighbor and Lin-Kernighan heuristics, and exact solvers such as Concorde. Historical work by Held, Karp, and Menger helped define the field.
    • heuristics
      • Nearest Neighbor Algorithm — The Nearest Neighbor Algorithm is a greedy approach to the traveling salesman problem that repeatedly chooses the closest unvisited city. It is fast but usually suboptimal, though it can be used as an approximation method in Euclidean settings.

Computational Biology

• bioinformatics
  • BLAST — The Basic Local Alignment Search Tool, or BLAST, is an NCBI bioinformatics program for finding homologous biological sequences by comparing DNA, RNA, or protein inputs against public databases using heuristic local alignment. It is widely used to compare homologous genes across species, is related to Smith-Waterman, and comes in variants such as BLASTn and BLASTp. It is commonly contrasted with FASTA.
• sequence alignment
  • Clustal — Clustal is a multiple-sequence alignment program used to compare DNA or protein sequences across organisms. Its common command-line versions include ClustalW and Clustal Omega.
• Molecular mechanics
  • force fields — Force fields are the energy functions used in molecular mechanics and molecular dynamics to approximate interatomic potentials. They combine terms for bonds, angles, torsions, electrostatics, and van der Waals interactions, with examples including AMBER, CHARMM, MM2, and ECEPP.

Computing in Fiction and Culture

Use fictional computing and robot narratives as related cultural context after the technical material.

• Isaac Asimov
  • Robot series
    • Three Laws of Robotics — Isaac Asimov’s famous fictional rules governing robot behavior, built into his robots’ positronic brains and first appearing in the story “Runaround.” In standard form, they forbid a robot from harming a human, require obedience to human orders, and demand self-preservation so long as that does not conflict with the earlier laws. They became one of the best-known ideas in modern science fiction and were later associated with Asimov’s Foundation-era science fiction.

Computer Scientists

Associate computer scientists with the methods and results studied.

Key Figures and Turing Award Context

• Turing Award — highest honor in computer science, awarded annually by the ACM since 1966; first recipient was Alan Perlis. It is often called the “Nobel Prize of Computing” and is named for Alan Turing.

• Foundations, Algorithms, and Information
  • Alan Turing — foundational theorist: Turing machine, computability, halting problem (1936); codebreaking at Bletchley Park; died 1954. The Turing Award is named for him but he never received it.
    • Computing Machinery and Intelligence — “Computing Machinery and Intelligence” is Alan Turing’s 1950 paper introducing the idea that would become the Turing test. In it, he asks whether machines can think and replies to objections to machine intelligence.

  • John von Neumann — von Neumann architecture (CPU, memory, I/O bus, stored-program concept); also contributed to game theory and quantum mechanics. The 1945 “First Draft of a Report on the EDVAC” described the stored-program architecture in which instructions and data share memory, allowing programs to modify themselves; this became the dominant CPU design model. He coauthored Theory of Games and Economic Behavior (1944) with Oskar Morgenstern, is associated with the minimax theorem, the Manhattan Project, the MANIAC computer, and the theory of self-reproducing automata, and his work also influenced von Neumann algebras, set theory, and functional analysis.

  • Edsger Dijkstra — shortest-path algorithm (1956), structured programming, semaphores, Dijkstra’s algorithm and the “GOTO statement considered harmful” letter; Turing Award 1972. He was a Dutch computer scientist whose shortest-path algorithm finds shortest paths in graphs with nonnegative edge weights.

  • Donald Knuth — The Art of Computer Programming series; developed TeX; Turing Award 1974; coined the term “literate programming.” He also created Metafont and contributed to Algorithm X, the Knuth-Morris-Pratt string-search algorithm, up-arrow notation for large numbers, dancing links for exact cover problems, and the balanced base-2i number system. He popularized literate programming through WEB, and was an early email user who later stopped using it.
    • The Art of Computer Programming — The Art of Computer Programming is Donald Knuth’s multivolume computer science treatise. It is famous for its detailed treatment of algorithms and for Knuth’s reward of a hexadecimal dollar to readers who find errors.

  • Claude Shannon — founder of information theory; A Mathematical Theory of Communication (1948); defined bit and entropy.

  • Richard Manning Karp — Richard Manning Karp is a theoretical computer scientist known for major results in NP-completeness and for work on algorithms such as Hopcroft-Karp, Edmonds-Karp, and Rabin-Karp. His paper on reducibility among combinatorial problems helped define standard NP-completeness techniques.

  • John Barkley Rosser Sr. — John Barkley Rosser Sr. was a logician associated with work on the halting problem and the Rosser paradox. He also worked with Stephen Kleene on lambda calculus and proved a theorem with Church about confluence of reductions.

  • Vaughan Pratt — Vaughan Pratt is a Stanford computer scientist known for work on shell sort, string matching with Knuth and Morris, and the most common primality certificate. His name appears in Pratt certificates and related algorithmic results in theoretical computer science.

  • logicians
    • Stephen Cole Kleene — Stephen Cole Kleene was a logician and computer scientist whose work includes Kleene star, Kleene normal form, the s-m-n theorem, and Kleene algebra. He also co-authored work connected to the Kleene–Rosser paradox and the recursion theorem.
• Languages, Systems, and Software Design

  • Grace Hopper — pioneered compilers; developed COBOL; coined “debugging” after removing a literal moth from the Mark II computer (1947). She was a U.S. Navy rear admiral and computer scientist; created the A-0 compiler in 1952 and Flow-Matic, and championed human-readable programming languages.

  • Dennis Ritchie and Ken Thompson — created UNIX (1969) and the C programming language at Bell Labs; Turing Award 1983.

  • Linus Torvalds — created the Linux kernel (1991) and Git (2005). Finnish-American software engineer; received the Millennium Technology Prize in 2012. The Linux kernel is maintained through a distributed open-source model he still oversees. He is also associated with Linus’s law, the idea that with enough eyes all bugs are shallow.

  • Tim Berners-Lee — invented the World Wide Web (1989–1991) at CERN; proposed HTTP, HTML, and URLs. British computer scientist; developed ENQUIRE and wrote the first browser. He chose not to patent HTTP or HTML, making the web openly available, and founded the World Wide Web Consortium (W3C) in 1994 to develop web standards. Knighted in 2004.

  • Niklaus Wirth — designed Pascal (1970), Modula-2, Oberon; Turing Award 1984; proposed “Wirth’s law” — software gets slower faster than hardware gets faster; championed structured programming.

  • Tony Hoare — invented Quicksort (1959); designed Communicating Sequential Processes (CSP); Turing Award 1980; introduced the null reference and called it his “billion-dollar mistake.”
    • Tony Hoare: Quicksort and CSP — Hoare’s Quicksort article appeared in The Computer Journal 5(1), 10–16 (1962); the algorithm had already appeared as a short Communications of the ACM algorithm in 1961. His Communicating Sequential Processes article appeared in Communications of the ACM 21(8), 666–677 (1978); distinguish it from the later 1985 book.³¹

  • Barbara Liskov — Liskov Substitution Principle (LSP): if S is a subtype of T, objects of type T may be replaced by objects of type S without altering program correctness; Turing Award 2008; designed CLU (first language with abstract data types as a linguistic construct).

  • Leslie Lamport — distributed systems pioneer; Paxos consensus algorithm; logical clocks (“Time, Clocks, and the Ordering of Events in a Distributed System,” 1978); LaTeX document system; Turing Award 2013.

  • John Backus — designed FORTRAN (1957), the first widely used high-level programming language; invented BNF (Backus-Naur Form) notation for grammars; Turing Award 1977; also proposed “function-level programming.”

  • Peter Naur — formalized BNF with Backus; co-editor of the ALGOL 60 report; Turing Award 2005; his name appears in “Backus-Naur Form.”

  • James Gosling — James Gosling is the computer scientist best known as the inventor of Java at Sun Microsystems. He later became a notable witness in the Microsoft antitrust case over the language’s technical soundness. Quizbowl clues usually identify him through Java’s creation and Sun’s role in software history.
• Artificial Intelligence and Symbolic Computing

  • John McCarthy — invented Lisp (1958); coined the term “artificial intelligence”; Turing Award 1971.

  • Marvin Minsky — co-founder of MIT AI Lab; Perceptrons book (with Papert) showed limits of single-layer networks; Turing Award 1969; built the first neural network simulator (SNARC, 1951).

  • Stephen Wolfram — Stephen Wolfram is the computer scientist behind Mathematica and the Wolfram Language, as well as the Wolfram Alpha computational engine. He is also associated with cellular automata, including Rule 110 and the classification of one-dimensional automata.

    • A New Kind of Science — Stephen Wolfram’s massive book argues that simple rules can generate the behavior of complex systems. It was presented as a sweeping attempt to overturn conventional scientific thinking and leans heavily on Mathematica.
• computer scientists

  • Alan J. PERLIS — Alan Perlis was a pioneering computer scientist associated with the development of early programming languages and the first graduate computer science department at Carnegie Tech. He was the first recipient of the Turing Award and a founder of the ACM’s intellectual culture.

  • Brian Kernighan — Brian Kernighan is a Canadian computer scientist best known for coauthoring The C Programming Language and for his work on Unix tools. His name appears in Kernighan’s law about debugging, in AWK, and in the Lin–Kernighan heuristic for optimization problems.

  • Brian W. Kernighan — Brian W. Kernighan is a computer scientist best known for collaborating with Dennis Ritchie on The C Programming Language. His name is often linked with the development and teaching of the C language.

  • David Gelernter — David Gelernter is a Yale computer science professor and Unabomber survivor. He is associated with the book Mirror Worlds, which the Unabomber referenced after bombing Gelernter’s office.

  • Douglas Hofstadter — Douglas Hofstadter is a cognitive scientist, computer scientist, and writer best known for Gödel, Escher, Bach and I Am a Strange Loop. His other works include Metamagical Themas, The Mind’s I, and Le Ton beau de Marot. His work bridges self-reference, strange loops, recursion, consciousness, translation, language, art, music, and artificial intelligence, and he is associated with discussion of the Hofstadter butterfly.
    • Godel, Escher, Bach: An Eternal Golden Braid — Gödel, Escher, Bach: An Eternal Golden Braid is Douglas Hofstadter’s book about recursion, consciousness, and self-reference. It features fictional languages like BlooP and FlooP, plus repeated nods to Achilles and the Tortoise and the idea of a “strange loop.”

  • Edsger W. Dijkstra — Edsger Wybe Dijkstra was a Dutch computer scientist known for foundational work in algorithms and programming. He developed Dijkstra’s shortest-path algorithm and the shunting-yard algorithm, contributed to structured programming, and worked on the dining philosophers problem, deadlock avoidance, and concurrency control. He was also a prominent critic of the GOTO statement.

  • Emil Leon Post — Emil Leon Post was a logician and computer scientist known for Post canonical systems, Post’s correspondence problem, and early work on computability. He also proposed the simple Post machine model and studied closed classes of Boolean functions in what is now called Post’s lattice.

  • Gregory Chaitin — Gregory Chaitin is a computer scientist known for work in algorithmic information theory and incompleteness results. He is associated with Chaitin’s constant, the halting probability of a randomly chosen program, and with a form of incompleteness theorem tied to Kolmogorov complexity.

  • Haskell Curry — Haskell Curry was an American logician and computer scientist whose name is attached to currying and the Curry-Howard correspondence. He also appears in set theory through Curry’s paradox.

  • Richard Bellman — Richard Bellman founded dynamic programming and co-names the Bellman-Ford shortest-path algorithm. He is also associated with Bellman equations and the principle of optimality, and he coined dynamic programming to disguise the military character of his work.

  • Richard Karp — Richard Karp is the computer scientist best known for proving the NP-completeness of many classic problems in his paper on reducibility among combinatorial problems. His name also appears in graph and string algorithms, including the Hopcroft-Karp matching algorithm and the Karp-Rabin string-searching method. He is also the first namesake of the Karp-Lipton theorem, which says that if SAT lies in P/poly then the polynomial hierarchy collapses to its second level.