BMath Bachelor of Mathematics Number Theory and Discrete Mathematics 2 — Questions and Answers
Question 1: How many subsets does a set with n elements have?
- n
- n²
- 2ⁿ (Correct answer)
- n!
Correct answer: 2ⁿ
Each element is either included or excluded from a subset, giving 2 choices per element and 2ⁿ total subsets.
Question 2: The principle of inclusion-exclusion for two sets A and B states |A ∪ B| equals:
- |A| + |B|
- |A| + |B| − |A ∩ B| (Correct answer)
- |A| · |B|
- |A| − |B| + |A ∩ B|
Correct answer: |A| + |B| − |A ∩ B|
Inclusion-exclusion corrects for double-counting: |A ∪ B| = |A| + |B| − |A ∩ B|.
Question 3: A graph is said to be connected if:
- Every vertex has the same degree
- There exists a path between every pair of vertices (Correct answer)
- It has no cycles
- Every edge connects two vertices of different colors
Correct answer: There exists a path between every pair of vertices
Connectivity means any two vertices can be linked by a path, so the graph forms one piece rather than isolated components.
Question 4: The number of ways to arrange n distinct objects in a row is:
- n
- n²
- 2ⁿ
- n! (Correct answer)
Correct answer: n!
There are n choices for the first position, n−1 for the second, and so on, giving n! = n × (n−1) × … × 1 total permutations.
Question 5: Euler's formula for connected planar graphs states V − E + F equals:
- 0
- 1
- 2 (Correct answer)
- 3
Correct answer: 2
Euler's formula V − E + F = 2 relates vertices V, edges E, and faces F (including the outer face) of any connected planar graph.
Question 6: The recurrence T(n) = 2T(n/2) + n has solution (by the Master Theorem):
- O(n)
- O(n log n) (Correct answer)
- O(n²)
- O(log n)
Correct answer: O(n log n)
By the Master Theorem Case 2 with a = 2, b = 2, f(n) = n = n^(log_2 2), the solution is T(n) = O(n log n).
BMath Bachelor of Mathematics Number Theory and Discrete Mathematics 2
How many subsets does a set with n elements have?