GLOBAL KNOWLEDGE ARK

Reference library

Foundations

Explore concepts, laws, equations and methods, with clear explanations of their use and sources. Choose an area of study or find a specific entry.

More filters

Reference entries

Showing 1–30 of 204 reference entries

Physics · Information · MeasurementScientific records

Build an inspectable physics record, test and revise a bounded cart model, preserve processing history, and plan findable data with appropriate sharing conditions.

MethodMathematics & logic · InformationClassical propositions and connectives

Classical logic combines truth-valued propositions using defined connectives.

DefinitionMathematics & logic · InformationSets, membership and basic operations

A set specifies membership without counting duplicate listings.

DefinitionMathematics & logic · InformationFunctions, domain and codomain

A function assigns exactly one output to each input in its domain.

DefinitionMathematics & logic · InformationMathematical induction

A base case and general successor step establish a predicate on all nonnegative integers.

MethodMathematics & logic · InformationComplex numbers

A complex number has real coordinates a and b and an imaginary unit satisfying i²=−1.

DefinitionMathematics & logic · Information · PhysicsLinear maps and matrix representation

A linear map preserves linear combinations and has a matrix once bases are chosen.

DefinitionMathematics & logic · InformationProbability space and axioms

A probability assigns nonnegative, normalised, countably additive weights to events.

DefinitionMathematics & logic · InformationConditional probability and independence

Conditioning restricts attention to an event of positive probability.

DefinitionMathematics & logic · InformationExpected value of a discrete random variable

Expected value weights possible values by their probabilities.

DefinitionInformation · Mathematics & logicBits and unsigned binary encoding

A bit has two possible states; a fixed-width unsigned binary word encodes an integer.

DefinitionInformation · Mathematics & logicShannon entropy of a discrete distribution

Shannon entropy measures uncertainty in a specified probability distribution.

DefinitionInformationAlgorithm and decision procedure

An algorithm specifies effective steps; a decision procedure must terminate on every permitted input.

MethodInformation · Mathematics & logicUndecidability of the halting problem

No total algorithm decides halting for every program and input in a general computation model.

Mathematical statementInformation · Mathematics & logicAsymptotic upper bounds and big O

Big O bounds eventual growth up to a fixed constant factor.

DefinitionInformationFinite-alphabet mutual information

Mutual information measures statistical dependence in bits.

DefinitionInformationNear-lossless source coding threshold

Entropy bounds asymptotic compression for an iid source.

Mathematical statementInformationDiscrete memoryless channel capacity

Capacity is the maximal asymptotically reliable rate.

Mathematical statementInformationHamming distance and error correction

Separated codewords permit bounded symbol-error recovery.

Mathematical statementInformationInternet protocol layers

Protocol layers divide communication responsibilities.

DefinitionInformationTCP reliable byte-stream transport

TCP orders bytes and retransmits detected losses.

MethodInformationEncryption, hashes and message authentication

Cryptographic primitives serve distinct security properties.

DefinitionInformationPublic-key digital signatures

A signing key and a verification key have different roles.

DefinitionInformationComputable reductions and undecidability

Reduction direction determines which impossibility transfers.

Mathematical statementInformationDecision classes P and NP

Polynomial solving and polynomial verification differ.

DefinitionInformationNP-hardness and NP-completeness

NP-completeness combines verification and reduction hardness.

DefinitionInformationBounded-error randomized computation

Random choices permit a stated probability of error.

DefinitionInformationFinite graphs and trees

Graphs represent pairwise connections; trees impose acyclicity.

DefinitionInformationData-structure interfaces and operation costs

An interface defines operations; an implementation determines costs.

MethodInformationLoop invariants and total correctness

An invariant establishes correctness only with its proof obligations.

Method
MethodSource checked

Data-structure interfaces and operation costs

Information

An interface defines operations; an implementation determines costs.

Key knowledge

A stack removes the most recently added item; a queue removes the earliest. A dictionary supports key lookup, insertion and deletion. Arrays offer constant-time indexed access in a word-RAM model, while linked-list traversal to an arbitrary index takes linear time.

Conditions and scope

  • Specify representation, input size and machine-cost assumptions.
  • Worst-case, expected and amortized operation bounds are distinct.
Sources · 1

References

Sources retain their recorded scope. A source link alone does not establish verification of every statement.

  1. 6.006 2020, Lecture 2: Data structuresErik Demaine, Jason Ku and Justin Solomon / MITCourse notes · PDFocw.mit.eduRead source

Evidence and review

Interface/implementation distinction, sequence/set operations, stack/queue and array/linked-list operation costs.

2026-10-10 · Basic abstract operations and two representation cost examples.

Related reference entries

Explore relationships within this area of study and its connections to other areas.

Showing 1–6 of 6 relationships

Scientific relationships · 6 / 6

The relationship type describes the connection. Its linked statements, sources and conditions define the scope.

  1. Uses definition
    Relationship sources · 1

    Linked statements

    • A stack removes the most recently added item; a queue removes the earliest. A dictionary supports key lookup, insertion and deletion. Arrays offer constant-time indexed access in a word-RAM model, while linked-list traversal to an arbitrary index takes linear time.
  2. Uses definition
    Relationship sources · 1

    Linked statements

    • A hash table maps keys to buckets and stores colliding keys in a chain. With load factor α=n/m and a suitably randomized universal hash family, lookup takes expected O(1+α); an adversarial collision pattern can instead require O(n).
  3. Uses definition
    Relationship sources · 1

    Linked statements

    • An AVL binary search tree maintains subtree heights differing by at most one at every node. Its height is O(log n); search and updates with local rotations and maintained heights take O(log n) worst-case time.
  4. Uses definition
    Relationship sources · 1

    Linked statements

    • A binary max heap stores a complete binary tree in an array with every parent key at least its children's keys. Maximum lookup is O(1); upward/downward restoration after insertion or extraction costs O(log n), and bottom-up heap construction costs O(n).
  5. Uses definition
    Relationship sources · 1

    Linked statements

    • A nondeterministic pushdown automaton augments finite control with one unbounded last-in-first-out stack. The languages it recognizes are exactly the context-free languages; a grammar is simulated by expanding stack variables and matching terminal symbols.
  6. Uses definition
    Relationship sources · 1

    Linked statements

    • For n records with integer keys 0≤k<U, append records to U insertion-ordered buckets by key, then concatenate buckets in increasing key order. This sorts stably in O(n+U) time and space with unit-cost indexing and appends. Duplicate keys retain their input order.
Entry detailsPermanent link to this entry ↗
Record identity
info-data-structures
Revision
university-reference.1
Structured reference record
University reference