Logic & Computation
A contradiction created by defining a barber who shaves only those who don’t shave themselves.
What is a paradox?
This search algorithm checks the middle element and divides the list repeatedly.
What is binary search?
An experiment with exactly two possible outcomes.
What is a Bernoulli trial?
The prime numbers less than or equal to 10. (List them)
What are 2, 3, 5, and 7?
This function encodes sequences by turning terms into coefficients of a power series.
What is a generating function?
A function that is both one-to-one and onto.
The time complexity of a binary search in Big-O notation.
What is O(log n)?
A probability distribution must have total probabilities that sum to this.
What is 1?
The set of numbers found by multiplying an integer by all positive integers less than it.
What are factorials?
The number the stopwatch reads 20 seconds before it reads 15.
What is 55?
A mathematical truth that must hold at the start, during, and end of a loop.
What is a loop invariant?
The worst-case time complexity for a linear search through n items.
What is O(n)?
The definition that says probability = favorable outcomes / total outcomes. (Answer as What is Name's Definition)
What is Laplace’s definition?
The prime factorization of 4,096.
What is 2^12?
The number the stopwatch reads 70 seconds after it reads 24.
What is 34?
This progression is defined by a common ratio, not a common difference.
What is a geometric progression?
The algorithm that finds the greatest common divisor, not the least common multiple.
What is the Euclidean algorithm?
A permutation where no object is in its original position.
What is a derangement?
How many numbers greater than 1 and below 5 are prime and an answer to n! (where n is a positive integer)
What is 1?
The cardinality of the set intersection of numbers which are below 5, prime, and Fibonacci numbers.
What is 2? |{2, 3}|
A type of function that maps natural numbers to rational numbers without missing any.
What is a countable function?
The asymptotic time complexity of the following code
square ← 0
for i from 1 to n do
square ← square + n
What is O(n)
A randomized algorithm that may give an incorrect answer with low probability.
What is a Monte Carlo algorithm?
The primes less than or equal to the square root of 100.
What are 2, 3, 5, and 7?
The name of the classic algorithm used to find all primes below a given number.
What is the Sieve of Eratosthenes?