aiwiki.page
English

Algorithms & Theory

141 entriesPage 2 of 3
Hash Table

A hash table stores keys and associated values using computed array positions, providing fast lookup, insertion, and deletion under suitable hashing and capacity conditions.

hash-table
Heapsort

Heapsort is an in-place comparison sorting algorithm that uses a binary heap to achieve worst-case O(n log n) running time with constant auxiliary storage.

heapsort
Heuristic

A practical problem-solving method that uses estimates or simplified rules to guide decisions without necessarily guaranteeing an optimal result.

heuristic
Heuristic Evaluation Function

A function that estimates the value of a state or the cost of reaching a goal, enabling search algorithms to make decisions without exhaustive exploration.

heuristic-evaluation-function
Huffman coding

Huffman coding constructs variable-length prefix codes that minimize average codeword length for a specified symbol distribution.

huffman-coding
HyperLogLog

HyperLogLog is a probabilistic algorithm for estimating the number of distinct elements in a dataset using a compact, mergeable sketch.

hyperloglog
In-place Algorithm

An in-place algorithm transforms data within its existing storage while using only a small amount of additional memory.

in-place-algorithm
Information Gain

Information gain measures how much an observation or data split reduces uncertainty, commonly using entropy reduction or divergence between prior and posterior probability distributions.

information-gain
Insertion Sort

Insertion sort builds a sorted sequence one element at a time, offering constant auxiliary space and efficient performance on small or nearly sorted inputs.

insertion-sort
Inverted index

An inverted index maps terms or other indexed features to the documents containing them, enabling efficient full-text search, filtering, and ranked retrieval.

inverted-index
Iteration

Iteration is the repeated execution of a process, used to traverse data, refine approximations, solve computational problems, and develop software incrementally.

iteration
KD-tree

A KD-tree is a binary spatial data structure that partitions multidimensional points using axis-aligned splits to accelerate range searches and nearest-neighbor queries.

kd-tree
Knapsack Problem

The knapsack problem asks how to select items with given weights and values to maximize total value without exceeding a capacity limit.

knapsack-problem
Kolmogorov Complexity

Kolmogorov complexity measures the information in a finite object by the length of its shortest effective description.

kolmogorov-complexity
Kosaraju–Sharir Algorithm

The Kosaraju–Sharir algorithm finds the strongly connected components of a directed graph using two depth-first search passes, with linear running time for adjacency-list representations.

kosaraju-sharir-algorithm
Kosaraju's algorithm

Kosaraju's algorithm finds the strongly connected components of a directed graph in linear time using two graph traversals and reversed edges.

kosarajus-algorithm
Lambda Calculus

Lambda calculus is a formal system of functions and substitution that provides a foundation for computability, functional programming, and the relationship between programs and proofs.

lambda-calculus
Linear Search

Linear search examines elements sequentially until it finds a match or exhausts the search space, requiring linear time in the worst case.

linear-search
Linked List

A linked list is a sequential data structure whose elements are connected by references, allowing local insertion and removal without shifting neighboring elements.

linked-list
Locality-sensitive hashing

Locality-sensitive hashing is a randomized technique that maps similar objects to matching hash values with relatively high probability, enabling efficient approximate similarity search.

locality-sensitive-hashing
Log-Structured Merge Tree

A write-optimized indexing structure that buffers updates and merges sorted data across storage levels, trading cheaper ingestion for additional reading and rewriting.

log-structured-merge-tree
Loop Invariant

A loop invariant is a property of program state that holds at a designated point before and after every iteration of a loop.

loop-invariant
Lossless data compression

Lossless data compression reduces the size of digital representations while allowing exact reconstruction of the original data.

lossless-data-compression
Lossy data compression

Lossy data compression reduces the size of digital data by discarding information, trading exact reconstruction for lower storage requirements or transmission rates.

lossy-data-compression
Low-Density Parity-Check Code

A low-density parity-check code uses sparse parity constraints and iterative decoding to protect transmitted or stored information against errors.

low-density-parity-check-code
Macy Conferences

The Macy Conferences were interdisciplinary meetings held from 1946 to 1953 that helped establish cybernetics through discussions of feedback, communication, and biological and social systems.

macy-conferences
Master Theorem

The master theorem gives asymptotic bounds for divide-and-conquer recurrences by comparing nonrecursive work with the growth generated by recursive branching.

master-theorem
Mealy Machine

A Mealy machine is a finite-state computational model whose output at each step depends on both its current state and its current input.

mealy-machine
Median of medians

Median of medians is a deterministic pivot-selection method that enables selection of an element of any given rank in worst-case linear time.

median-of-medians
Merge Sort

A comparison-based sorting algorithm that divides data into smaller sequences and merges sorted sequences into a complete ordered result.

merge-sort
Minimax

Minimax is an adversarial search algorithm that selects a move by optimizing its outcome against an opponent assumed to play optimally.

minimax
Model Checking

Model checking automatically determines whether a mathematical model of a system satisfies formally specified properties by systematically analyzing its possible behaviors.

model-checking
Model of Computation

A model of computation formally specifies how computational processes operate, what they can compute, and which resources they consume.

model-of-computation
Monte Carlo Algorithm

A Monte Carlo algorithm uses randomness to achieve a bounded computational cost while allowing a controlled probability of an incorrect result.

monte-carlo-algorithm
NP-completeness

NP-completeness identifies decision problems that have efficiently verifiable solutions and are at least as hard as every problem in NP.

np-completeness
NP-hardness

NP-hardness classifies computational problems to which every problem in NP can be reduced in polynomial time.

np-hardness
P versus NP Problem

The P versus NP problem asks whether every decision problem whose solutions can be verified in polynomial time can also be solved in polynomial time.

p-versus-np-problem
PageRank

PageRank measures the importance of nodes in a directed network through the stationary distribution of a random walk with teleportation.

pagerank
Parallel computing

Parallel computing uses multiple processing resources simultaneously to execute parts of a computational workload, improving speed or enabling larger problems.

parallel-computing
Polygon Triangulation

Polygon triangulation partitions a polygonal region into nonoverlapping triangles, supporting geometric algorithms, graphics, and numerical simulation.

polygon-triangulation
Powersort

Powersort is an adaptive, stable merge-sorting method that uses run positions to choose a nearly optimal order for merging already sorted subsequences.

powersort
Prefix code

A code in which no codeword is a prefix of another, allowing concatenated codewords to be decoded without lookahead or separators.

prefix-code
Priority Queue

A priority queue is an abstract data type that retrieves elements according to priority rather than insertion order, commonly implemented using a heap.

priority-queue
Pseudocode

Pseudocode is a human-readable description of an algorithm that combines programming constructs, mathematical notation, and ordinary language without requiring executable syntax.

pseudocode
Pseudorandom Number Generator

A pseudorandom number generator is a deterministic algorithm that expands an initial state into a reproducible sequence designed to resemble random values.

pseudorandom-number-generator
PSPACE

PSPACE is the class of decision problems solvable by a deterministic computer using an amount of memory bounded by a polynomial in the input length.

pspace
Pumping Lemma

A pumping lemma gives a necessary repetition property of a class of formal languages, commonly used to prove that a language is not regular or not context-free.

pumping-lemma
Quantum Annealing

Quantum annealing uses controlled quantum fluctuations to search for low-energy states that encode optimization problems or physical models.

quantum-annealing
Quantum Circuit

A quantum circuit represents computation as an ordered network of quantum gates, state preparations, measurements, and classical control operations.

quantum-circuit
Quantum Error Correction

Quantum error correction protects quantum information by encoding it redundantly and identifying errors without measuring the stored logical state.

quantum-error-correction
Queue (Data Type)

A queue is a first-in, first-out abstract data type used to organize ordered processing, buffering, communication, and algorithmic traversal.

queue-data-type
Quickselect

Quickselect is a partition-based algorithm for finding an element of a specified rank in an unordered collection, with expected linear running time under randomized pivot selection.

quickselect
Quicksort

Quicksort is a partition-based sorting algorithm with expected \(O(n\log n)\) running time and efficient in-place implementations.

quicksort
Raft Consensus Algorithm

Raft is a leader-based consensus algorithm that maintains a replicated log across servers, enabling fault-tolerant services to agree on an ordered sequence of operations.

raft-consensus-algorithm
Randomized Algorithm

An algorithm that uses random choices during computation, with correctness, running time, or approximation quality analyzed probabilistically.

randomized-algorithm
Recursion

Recursion defines structures or computations in terms of simpler instances of themselves, providing a foundation for mathematical definitions and many algorithms.

recursion
Recursive Functions

Recursive functions formalize effective computation and define calculations through rules that refer to the functions being defined.

recursive-functions
Red–Black Tree

A red–black tree is a self-balancing binary search tree that uses color invariants to guarantee logarithmic-time search, insertion, and deletion.

red-black-tree
Reed–Solomon Code

A Reed–Solomon code protects digital information against symbol errors and erasures using polynomial arithmetic over a finite field.

reed-solomon-code
Regular Language

A regular language is a set of finite strings recognizable by a finite automaton, equivalently describable by a classical regular expression.

regular-language