BMath Bachelor of Mathematics Number Theory and Discrete Mathematics 2

Question 1

How many subsets does a set with n elements have?

Accepted Answer

2ⁿ

Answer

n

Answer

n²

Answer

n!

Question 2

The principle of inclusion-exclusion for two sets A and B states |A ∪ B| equals:

Accepted Answer

|A| + |B| − |A ∩ B|

Answer

|A| + |B|

Answer

|A| · |B|

Answer

|A| − |B| + |A ∩ B|

Question 3

A graph is said to be connected if:

Accepted Answer

There exists a path between every pair of vertices

Answer

Every vertex has the same degree

Answer

It has no cycles

Answer

Every edge connects two vertices of different colors

Question 4

The number of ways to arrange n distinct objects in a row is:

Accepted Answer

n!

Answer

n

Answer

n²

Answer

2ⁿ

Question 5

Euler's formula for connected planar graphs states V − E + F equals:

Accepted Answer

2

Answer

0

Answer

1

Answer

3

Question 6

The recurrence T(n) = 2T(n/2) + n has solution (by the Master Theorem):

Accepted Answer

O(n log n)

Answer

O(n)

Answer

O(n²)

Answer

O(log n)