Exhaustive Search and Optimization

These flashcards cover key terms and definitions related to exhaustive search and optimization, algorithms, and the greatest common divisor problem.

Exhaustive Search

A brute-force approach to combinatorial problems that generates all elements of the problem domain to find a desired element.

Candidate Solution

An object of the same data type as a problem output that may or may not be a correct output.

Acceptable Solution

A candidate solution that comprises a correct output for a given problem instance.

Verifier Algorithm

An algorithm that verifies whether a candidate solution is acceptable for a given problem instance.

Time Complexity

A measure of the amount of time an algorithm takes to complete as a function of the length of the input.

Exhaustive Optimization

A method that seeks to find the optimal candidate by keeping track of the best solution observed.

Greatest Common Divisor (GCD) Problem

The problem of finding the greatest positive integer that divides two given integers without leaving a remainder.

Integer Factorization

The process of breaking an integer into a product of smaller integers, specifically its prime factors.

Powerset

The set of all possible subsets of a set, including the empty set.

Permutations

Different arrangements of a set of elements where the order matters.

Greedy Method

An algorithmic paradigm that builds a solution piece by piece, always choosing the next piece that offers the most immediate benefit.

Johnson-Trotter Algorithm

An algorithm for generating all permutations of a sequence by exchanging adjacent elements.

Binary GCD Algorithm

A method that uses repeated subtraction and division by 2 to find the greatest common divisor.

Proper Exhaustive Search

An exhaustive search that returns the first correct candidate object.

Exhaustive Search Time Complexity

Exhaustive Optimization Time Complexity

GCD standard / Euclid Time Complexity

GCD Euclidean Time Complexity

GCD Lehmer’s algorithm Time Complexity

GCD Binary GCD algorithm Time Complexity

Generating pairs Time Complexity

Subset generating Time Complexity

John-Trotter Permutation algoirthm Time Complexity