The goal in the inductive step is usually to show:

A set is a:

The symbol ∈ means:

The empty set is denoted by:

The cardinality of a set is its:

If every element of A is also in B, then A is:

A proper subset means:

The union A ∪ B contains elements that are:

The intersection A ∩ B contains elements that are:

Two sets are disjoint if:

The complement of A contains elements:

The set difference A – B contains elements:

The power set of A is the set of:

If a set has n elements, its power set has:

Venn diagrams are useful for:

Ordered pairs are important in defining:

A Cartesian product A × B consists of:

A function from A to B assigns:

The set A in f: A → B is called the:

The set B in f: A → B is called the:

The actual outputs of a function form the:

A function is one-to-one if:

A function is onto if:

A bijection is a function that is:

An inverse function exists only if the function is:

The composition (g ∘ f)(x) means:

The identity function on set A maps each element to:

A recursive function is defined using:

In computer science, recursion usually requires:

A sequence is:

An arithmetic sequence has:

A geometric sequence has:

A mapping is another term commonly used for:

If f(a)=f(b) implies a=b, then f is:

If for each y in B there exists x in A with f(x)=y, then f is:

The floor of 3.9 is:

The ceiling of 3.1 is:

A partition of a set divides it into:

Russell's set paradox motivated careful treatment of:

Finite sets are especially important in CS because many structures are:

Characteristic functions represent sets using:

The symmetric difference A △ B contains elements:

The cardinality formula for two sets is |A ∪ B| =

A countably infinite set has:

Which of the following is countably infinite?

A function from a finite set A to itself that is one-to-one must also be:

The image of subset S under function f is:

Preimage of T under f is:

Many database queries rely heavily on:

A relation from A to B is any subset of:

Binary relations are represented naturally by:

A relation on set A is reflexive if:

A relation is symmetric if:

A relation is antisymmetric if:

A relation is transitive if:

An equivalence relation must be:

A partial order must be:

Equivalence relations partition a set into:

The equivalence class of a under relation R is:

Congruence modulo n is an example of:

The divisibility relation on positive integers is a:

A poset stands for:

In a Hasse diagram, edges usually show:

A maximal element in a poset is one that:

A greatest element in a poset is one that:

A minimal element in a poset is one that:

A least element in a poset is one that:

A lattice is a poset in which every pair has:

The least upper bound is also called:

The greatest lower bound is also called:

A total order is a partial order where:

Recurrence relations define terms using:

The Fibonacci sequence satisfies:

To solve a recurrence uniquely, we usually need:

The recurrence an = an-1 + d defines a:

The recurrence an = r an-1 defines a:

A closed form gives:

Strong induction differs from ordinary induction because it assumes:

Well-ordering principle states that every nonempty set of natural numbers has:

Proof by cases is useful when:

Counterexamples are used to show a statement is:

In software verification, invariants are properties that remain:

Loop invariants are often proved using:

The transitive closure of relation R adds pairs needed to make R:

The reflexive closure of relation R adds:

A relation matrix uses rows and columns to indicate:

Warshall's algorithm computes:

An equivalence relation on a database domain can help identify:

If a relation is reflexive and symmetric but not transitive, it is:

In partial orders, incomparable elements are those for which:

A chain in a poset is a subset where:

An antichain in a poset is a subset where:

Recursive definitions are useful in CS for defining:

An algorithm described recursively often has an implementation using:

Mastering proofs helps in discrete structures because it supports:

The sum 1 + 2 + … + n is often proved by:

A recurrence of the form an = c for all n defines a:

The degree of rigor required in discrete math proofs is important for:

The relation 'is ancestor of' on people is typically:

The relation '=' on any set is:

A recursive algorithm must avoid infinite recursion by having:

A prime number is an integer greater than 1 with:

An integer a divides b if:

The greatest common divisor of 12 and 18 is:

The least common multiple of 4 and 6 is:

Euclidean algorithm is used to find:

If gcd(a,b)=1, then a and b are called:

Fundamental theorem of arithmetic states that every integer greater than 1 can be written as:

A number is even if it is divisible by:

A number is odd if it can be written as:

If a divides b and b divides c, then:

Modular arithmetic deals with remainders after division by:

17 mod 5 equals:

Two integers a and b are congruent modulo n if:

The notation a ≡ b (mod n) means:

In cryptography, modular arithmetic is important because:

A sequence defined by an = n^2 is:

The sum of first n terms of an arithmetic sequence depends on:

The sum of a geometric series with ratio r (|r|<1 in infinite case) depends on:

Factorial of n, written n!, equals:

0! is defined as:

The number of ways to arrange n distinct objects is:

A permutation considers:

A combination considers:

The number of r-combinations from n objects is:

The number of r-permutations from n distinct objects is:

The binomial coefficient nCr counts:

Pascal's identity relates binomial coefficients as:

The binomial theorem expands:

The inclusion-exclusion principle is used to:

For two sets, |A ∪ B| equals:

The pigeonhole principle states that if more than n objects are placed into n boxes, then:

A common application of pigeonhole principle is proving:

If 13 people are in a room, at least two were born in the same:

The number of binary strings of length n is:

A probability value always lies between:

If all outcomes are equally likely, probability of event E is:

The probability of the complement of event E is:

If events A and B are mutually exclusive, then P(A ∪ B) =

If events A and B are independent, then:

Conditional probability P(A|B) means:

Bayes' theorem is useful for:

Expected value in probability is:

A random variable in discrete math usually maps outcomes to:

The number of subsets of an n-element set is:

How many 3-letter strings can be formed from 26 letters if repetition is allowed?

How many ways can 5 distinct books be arranged on a shelf?

How many ways can 2 objects be chosen from 5 distinct objects?

The handshake problem with n people where everyone shakes hands once gives:

Parity arguments are based on whether integers are:

An absurd result such as an integer being both even and odd often indicates:

The sum of first n positive odd numbers is:

The number of functions from an n-element set to a k-element set is:

The number of one-to-one functions from an r-element set to an n-element set (r≤n) is:

Combinatorial reasoning is important in CS for analyzing:

Statistics in discrete structures often summarize:

The mean of values is:

Variance measures:

An algorithm is a:

An algorithm should terminate after:

Correctness of an algorithm means it:

Pseudocode is used to:

Linear search works by:

Binary search requires the data to be:

Binary search repeatedly:

Worst-case time complexity of linear search is:

Worst-case time complexity of binary search is:

Sorting arranges data according to:

Bubble sort repeatedly:

Selection sort repeatedly places:

Insertion sort builds:

Merge sort uses the strategy of:

Quick sort partitions the array around a:

Worst-case complexity of bubble sort is:

Worst-case complexity of merge sort is:

Merge sort is stable if:

Binary search is an example of:

The best data structure for breadth-first exploration of states is often a:

Depth-first processes are commonly implemented using:

Algorithm complexity is often expressed using:

O(n^2) grows compared to O(n log n) as n becomes large:

An invariant in sorting is:

A stable sort preserves:

A comparison-based sort cannot do better in worst case than:

Recursive algorithms often use stack memory because of:

An iterative procedure typically uses:

Algorithm analysis helps compare:

Searching a linked list efficiently with binary search is generally:

A graph consists of:

A simple graph has:

In an undirected graph, an edge {u,v} means:

The degree of a vertex in an undirected graph is:

In a directed graph, the number of incoming edges is:

A path is:

A cycle is a path that:

A graph is connected if:

A connected acyclic graph is called a:

The sum of degrees of all vertices in an undirected graph equals:

A planar graph can be drawn:

Euler's formula for a connected planar graph is:

Graph coloring assigns:

The chromatic number of a graph is:

A bipartite graph can be colored with at most:

A complete graph on n vertices is denoted by:

A complete graph Kn has how many edges?

A subgraph contains:

A walk may:

A trail is a walk with no repeated:

A simple path has no repeated:

An Euler circuit uses:

A connected graph has an Euler circuit iff every vertex has:

A Hamiltonian path visits:

A Hamiltonian cycle is a cycle that visits:

Dijkstra's algorithm finds:

Breadth-first search on an unweighted graph finds:

Depth-first search is useful for:

A spanning tree of a connected graph contains:

A minimum spanning tree is defined for:

Kruskal's algorithm builds a minimum spanning tree by:

Prim's algorithm grows a minimum spanning tree from:

An adjacency matrix of a graph is especially convenient for:

An adjacency list is usually memory-efficient for:

Topological sorting applies to:

A tree is a connected graph with:

A rooted tree is a tree with:

In a rooted tree, the parent of a node is:

A leaf in a tree is a vertex with:

The level or depth of a node is its distance from the:

The height of a rooted tree is:

A binary tree is a rooted tree where each node has at most:

A full binary tree is one in which every internal node has:

A complete binary tree fills levels:

Preorder traversal visits:

Inorder traversal of a binary tree visits:

Postorder traversal visits:

Level-order traversal is commonly implemented using a:

Expression trees are useful for representing:

A subtree of a node consists of:

A forest is:

Removing the root from a rooted tree yields:

For any tree with n vertices, the number of edges is:

A tree with one root and branching choices naturally models:

File systems and organization charts are often modeled using:

A spanning tree of a graph helps remove:

Decision trees in computing represent:

The children of a node are:

The siblings of a node are nodes that share the same:

Traversals are important because they define systematic ways to:

A balanced binary search tree generally supports search in:

Depth-first traversal of a tree is naturally expressed using: