Big Oh
Number Theory
Crypto
Automata Theory
Entropy
100
The best possible algorithmic complexity
What is constant time, O(1)?
100
The purpose of the Euclidean Algorithm
What is finding the greatest common divisor of two integers?
100
The two main weaknesses of cryptosystems
What are (1) human knowledge about the scheme and (2) patterns from the plaintext preserved in the ciphertext?
100
The set of strings on an alphabet that an automaton A accepts, noted L(A)
What is its language?
100
The amount of information contained in the answer to a binary question with equally likely options
What is one bit?
200
The complexity of sequential search (iteration over a list of size n one time)
What is linear time, O(n)?
200
The effect of the mod operator, in the case of
a mod b
What is divide a by b and return the remainder?
200
The cryptosystem with the maximum possible security
What is the one-time pad?
200
The difference between DFAs and NFAs
What is the output of the transition function (one state vs a set of states, resulting in deterministic behavior vs nondeterministic behavior)?
200
The equation used to find the information content of an event, x, given its probability, p(x)
What is
-log_2 (p(x))
?
300
The complexity of an algorithm that reduces the search space by half with each step
What is logarithmic time, O(log n)?
300
GCD(5n, 20n)
What is 5n?
300
An example of a modern cryptographic system which is SYMMETRIC, since it uses the same key to both encrypt and decrypt
What is AES (Advanced Encryption Standard)?
300
The name for the languages accepted by DFAs and NFAs
What are the regular languages?
300
Another name for the average information content of an ensemble (a collection of events and their probabilities)
What is entropy?
400
The complexity of the following algorithm:
for i in range (a):
for j in range (a):
foo(i,j)
What is quadratic time?
O(n^2)
400
The indication that the Euclidean algorithm has terminated
What is a remainder of 0?
400
The type of cryptosystem which can both encrypt and sign messages, providing security for the message and confidence in the sender
What is asymmetric (public key) cryptography, e.g. RSA?
400
The terminal state for the string "FERVOR" in this automaton
What is q1?
400
The entropy of a fair coin
What is 1 bit?
500
The meaning of the "n" in a big-oh complexity such as O(log n)
What is the size of the input to the algorithm?
500
GCD(abc, bcd) given a,d share no common factors?
What is bc?
500
The reason it is safe to publicly share the value n for an RSA exchange.
What is the difficulty of factoring the product of two large primes?
500
The components of a Turing Machine that DFA and NFAs lack
What are the tape and tape head?
500
The entropy of the following "spinner"
What is 1.75 bits?
600
The big-oh performance of most 'optimal' sorting algorithms.
What is O(n*log(n))?
600
GCD(456, 123)
What is 3?
600
The final, shared secret between Alice and Bob if they perform the Diffie Hellman Key exchange with the following setup:
p = 11, g = 2, a = 9, b = 4
What is 9?
600
The language accepted by this automaton
What are all binary strings that start with 1?
600
The name of the mathematician/computer scientist who first defined the bit
Claude Shannon