Concepts
5,907Terms and methods explained by more than one lecturer. Each opens at the minute it is taught.
Theory & Algos
21- NP-completeA problem is NP-complete if it is in NP and it is NP-hard.
- Approximation algorithmAlgorithms that run in polynomial time and find solutions that are guaranteed to be close to the optimal or satisfy a large fraction of constraints rather than being exact.
- InductionA proof technique where one proves a base case and that implies to conclude the proposition holds for all natural numbers.
- AssociativityThe property where grouping of elements in a binary operation does not change the result.
- Decision treeThe representation of a Boolean function represented as a binary tree where internal nodes are labeled by variables and leaves are labeled by numbers.
- Modular arithmeticA system of arithmetic for integers where numbers wrap around after reaching a certain value called the modulus.
- ConfigurationA complete description of the state of a Turing machine, including the current state, the tape contents, and the head position.
- Diffie-Hellman key exchangeA cryptographic protocol that allows two parties to establish a shared secret over an insecure channel.
- CryptographyThe art and science of scrambling and encrypting information so that it can be transmitted securely.
- EncodingThe process of mapping mathematical objects into strings of bits or alphabet characters so they can be operated on by algorithms.
- Post-quantum cryptographyCryptographic algorithms that are secure against a cryptanalytic attack by a quantum computer.
- RelaxationThe fundamental operation in shortest path algorithms where we continually reduce estimated path distance values down to the true shortest path length.
- EncryptionThe art and tool of hiding information by transforming a plain message into an encrypted message using keys.
- Brute-force attackAn attack method that systematically tries all possible keys until the correct one is found.
- Asymmetric cryptographyA cryptographic model where encryption and decryption use different keys, specifically a public key for encryption and a private key for decryption.
- RingAn algebraic structure extending groups by adding multiplication, though not all elements necessarily have a multiplicative inverse.
- Round functionThe repeating function applied for 80 rounds in SHA-1, consisting of additions, bit shifts, and Boolean functions.
- Symmetric cryptographyA cryptographic scheme where the same secret key is used for both encryption and decryption.
- Table doublingA dynamic array resizing strategy where the array capacity is doubled whenever it runs out of space.
- Random access machineThe algorithmic model we really work in when we do algorithms, where memory access is random.
- Stable marriage problemThe problem of finding a stable matching between two equally-sized sets of elements given preference lists for each element.