BSCS Discrete Mathematics and Logic 2 — Questions and Answers
Question 1: What is a graph in discrete mathematics?
- A 2D plot of a mathematical function
- A collection of vertices and edges representing relationships (Correct answer)
- A sorted list of numbers
- A matrix of boolean values
Correct answer: A collection of vertices and edges representing relationships
A graph G = (V, E) consists of a set of vertices V and edges E representing connections between them.
Question 2: What is a tree in graph theory?
- Any graph with cycles
- A connected acyclic undirected graph (Correct answer)
- A directed graph with weighted edges
- A graph where all vertices have degree 2
Correct answer: A connected acyclic undirected graph
A tree is a connected graph with no cycles; it has exactly n−1 edges for n vertices.
Question 3: What does Big-O notation describe in the context of algorithms?
- The exact number of operations
- An upper bound on the growth rate of a function (Correct answer)
- The minimum input size required
- The memory layout of a data structure
Correct answer: An upper bound on the growth rate of a function
Big-O notation provides an asymptotic upper bound on how an algorithm's runtime or space grows relative to input size.
Question 4: How many subsets does a set with n elements have?
- n
- n²
- 2n
- 2^n (Correct answer)
Correct answer: 2^n
A set with n elements has 2^n subsets because each element can independently be included or excluded.
Question 5: What is a relation that is reflexive, symmetric, and transitive called?
- Partial order
- Total order
- Equivalence relation (Correct answer)
- Bijective mapping
Correct answer: Equivalence relation
An equivalence relation satisfies reflexivity (aRa), symmetry (aRb → bRa), and transitivity (aRb ∧ bRc → aRc).
Question 6: What is mathematical induction used for?
- Proving a statement is false by counterexample
- Proving a statement holds for all natural numbers by a base case and inductive step (Correct answer)
- Solving systems of linear equations
- Enumerating permutations of a set
Correct answer: Proving a statement holds for all natural numbers by a base case and inductive step
Mathematical induction proves P(n) for all n ≥ base by establishing P(base) and showing P(k) implies P(k+1).
BSCS Discrete Mathematics and Logic 2
What is a graph in discrete mathematics?