Discrete Mathematics and Applications

These flashcards cover terminology and concepts related to discrete mathematics and its applications, including algorithms, proofs, counting principles, and sequences.

Algorithm

A finite set of precise instructions for performing a computation or solving a problem.

Pigeonhole Principle

If there are more pigeons than pigeonholes, then at least one pigeonhole must contain at least two pigeons.

Recursion

Defining an object in terms of itself, commonly used for sequences and mathematical functions.

Mathematical Induction

A technique for proving the validity of statements that are true for all positive integers, consisting of a base case and an inductive step.

Sum Rule

If A and B are disjoint, then |A ∪ B| = |A| + |B|.

Product Rule

If a procedure can be broken down into separate tasks, the total number of ways to do the procedure is the product of the number of ways to do each task.

Base Case (in induction)

The case in a proof by induction that establishes the truth for the initial value.

Inductive Step

The step in a proof by induction that shows if the statement holds for an arbitrary case k, then it holds for k + 1.

Time Complexity

A measure of how the execution time of a process grows with the size of the input.

Space Complexity

A measure of how the amount of memory required by an algorithm grows with the size of the input.

Big-O Notation

A mathematical notation to describe the upper limit of the performance (time or space) of an algorithm.

Recursive Definition

Definition that expresses a term in terms of itself along with base cases.

Structural Induction

A method of proof used to show that a statement holds for recursively defined sets.

Counting Principle

A foundational technique in combinatorics that allows for finding the number of ways to choose or arrange elements.

Geometric Sequence

A sequence of numbers where each term is found by multiplying the previous term by a fixed, non-zero number called the 'common ratio'.

Arithmetic Sequence

A sequence where each term after the first is found by adding a constant to the previous term.

Permutation

An arrangement of all or part of a set of objects, where the order of arrangement is significant.

Combination

A selection of items from a larger pool where the order does not matter.

Subsequence

A sequence derived from another by deleting some elements without changing the order of the remaining elements.

Loop Invariant

An assertion that holds true before and after each iteration of a loop, used to prove the correctness of algorithms.