Library

No glossary terms available for this book.

No discussion questions available for this book.

Chapter 2: Logic and Proofs

What is the primary focus of propositional logic?

The study of sets and their elements
The study of functions and their properties
The study of logical statements and their truth values
The study of geometric shapes and their dimensions

Which of the following is NOT a logical connective in propositional logic?

THERE EXISTS
OR
AND
NOT

What is a tautology in propositional logic?

A proposition that is neither true nor false
A proposition that is true under all possible assignments of truth values
A proposition that is true only under certain assignments of truth values
A proposition that is false under all possible assignments of truth values

Which proof technique involves showing that the negation of a statement leads to a contradiction?

Proof by Contrapositive
Proof by Cases
Proof by Contradiction
Direct Proof

What is the base case in mathematical induction?

Assuming that the statement is true for an arbitrary natural number k
Showing that the statement is true for the initial value
Concluding that the statement is true for all natural numbers
Showing that the statement is true for k + 1

Which of the following is a quantifier in predicate logic?

IMPLIES
OR
AND
FOR ALL

What is a free variable in predicate logic?

A variable that is used to denote a specific object
A variable that is not bound by a quantifier
A variable that is bound by a quantifier
A variable that can take any value

Which proof technique involves considering different cases and showing that the statement is true for each case?

Proof by Contradiction
Direct Proof
Proof by Contrapositive
Proof by Cases

What is the inductive step in mathematical induction?

Showing that the statement is true for a specific value
Showing that the statement is true for the initial value
Assuming that the statement is true for an arbitrary natural number k and showing that it is true for k + 1
Concluding that the statement is true for all natural numbers

Which of the following is NOT a key concept in predicate logic?

Logical Equivalences
Quantifiers
Truth Tables
Predicates

Chapter 3: Combinatorics

According to the Addition Principle, if a task can be performed in 5 ways and another independent task can be performed in 3 ways, then the number of ways to perform both tasks is:

15
25
10
8

The Multiplication Principle states that if a task can be performed in 4 ways and another independent task that depends on the first task can be performed in 6 ways, then the number of ways to perform both tasks is:

30
10
12
24

The number of permutations of 7 distinct objects taken 3 at a time is given by:

P(7, 3) = 3! / 7!
P(7, 3) = 3! / (7-3)! = 3! / 4!
P(7, 3) = 7! / 3!
P(7, 3) = 7! / (7-3)! = 7! / 4!

The number of combinations of 8 distinct objects taken 4 at a time is given by:

C(8, 4) = 4! / (8! * (8-4)!) = 4! / (8! * 4!)
C(8, 4) = 8! / 4!
C(8, 4) = 8! / (4! * (8-4)!) = 8! / (4! * 4!)
C(8, 4) = 4! / 8!

The binomial coefficient C(10, 3) represents the number of ways to:

Arrange 10 elements from a set of 3 elements in a specific order
Choose 3 elements from a set of 10 elements without regard to order
Choose 10 elements from a set of 3 elements without regard to order
Arrange 3 elements from a set of 10 elements in a specific order

Which of the following is NOT a property of binomial coefficients?

Multiplication
Symmetry
Addition
Pascal's Identity

Generating functions are used to:

Subtract numbers
Find closed-form expressions for sequences
Multiply numbers
Add numbers

The generating function for the sequence 1, 2, 3, 4, ... is:

1 / (1 - x)
1 + 2x + 3x^2 + 4x^3 + ...
1 - 2x + 3x^2 - 4x^3 + ...
1 * 2 * 3 * 4 * ...

Chapter 4: Graph Theory

What is the degree of a vertex in a graph?

The total number of vertices in the graph.
The length of the shortest path from the vertex to another vertex.
The total number of edges in the graph.
The number of edges incident to the vertex.

Which of the following is NOT a graph traversal algorithm?

Dijkstra's Algorithm
Depth-First Search (DFS)
Breadth-First Search (BFS)
Binary Search

In an undirected graph, if there is an edge between vertices A and B, what does this imply?

A and B are the same vertex.
A can reach B and B can reach A.
A can reach B but B cannot reach A.
There is no connection between A and B.

Which theorem states that any planar graph can be colored with at most four colors?

Planar Graph Theorem
The Four Color Theorem
Brook's Theorem
Euler's Theorem

What is the chromatic number of a graph?

The smallest number of colors needed to color the graph.
The total number of edges in the graph.
The total number of vertices in the graph.
The length of the longest path in the graph.

Which representation of a graph uses a collection of unordered lists to describe the set of neighbors of a vertex?

Edge List
Adjacency List
Adjacency Matrix
Incidence Matrix

What is a cycle in a graph?

A path that is the shortest path between two vertices.
A path that contains a loop.
A path that starts and ends at the same vertex without repeating any other edges or vertices.
A path that starts and ends at different vertices.

Which of the following is a technique used to color the vertices of a graph such that no two adjacent vertices share the same color?

Graph Traversal
Graph Matching
Graph Partitioning
Graph Coloring

In a directed graph, if there is a directed edge from vertex A to vertex B, what does this imply?

A and B are the same vertex.
A can reach B and B can reach A.
There is no connection between A and B.
A can reach B but B cannot reach A.

Which of the following is NOT a key term in graph theory?

Edge
Graph Density
Path
Vertex

Chapter 5: Number Theory

What is the greatest common divisor (GCD) of 48 and 60?

12
60
24
15

Which of the following is NOT a prime number?

19
17
21
23

What is 15 mod 4?

2
0
3
1

Which of the following is a solution to the Diophantine equation x^2 + y^2 = z^2?

(3, 4, 5)
(1, 2, 3)
(2, 3, 4)
(1, 1, 1)

What is the remainder when 73 is divided by 5?

1
3
2
4

Which of the following is the fundamental theorem of arithmetic?

Every integer greater than 1 is either a prime number itself or can be factorized into prime numbers, and this factorization is unique, up to the order of the factors.
The product of two prime numbers is always a prime number.
The sum of two prime numbers is always an even number.
The difference of two prime numbers is always a prime number.

What is the value of gcd(36, 48) using the Euclidean algorithm?

36
12
24
18

Which of the following is a Diophantine equation?

x + y = 5
x^3 + y^3 = z^3
x^2 + 2xy + y^2 = 1
x^2 + y^2 = 10

What is the prime number theorem?

The number of primes less than a given number n is approximately n/log(n).
The sum of all prime numbers is infinite.
The difference between consecutive prime numbers tends to infinity.
There are infinitely many prime numbers.

Which of the following is NOT a type of number theory problem?

Finding the GCD of two integers
Finding the area of a circle
Proving the existence of infinitely many prime numbers
Solving the Diophantine equation x^2 + y^2 = z^2

Chapter 6: Recurrence Relations

What is the general form of a recurrence relation?

a_n = f(n)
a_n = f(a_n-1, a_n-2, ..., a_n-k)
a_n = a_n-1 + a_n-2
a_n = a_n + 1

Which method is used to solve linear recurrence relations?

Newton's method
Gaussian elimination
Bisection method
Characteristic equation method

What is the characteristic equation for a linear recurrence relation of the form a_n = c_1a_n-1 + c_2a_n-2 + ... + c_k a_n-k?

x^k = c_1x^k-1 + c_2x^k-2 + ... + c_k
x^k = 0
x^k - c_1x^k-1 - c_2x^k-2 - ... - c_k = 0
x^k + c_1x^k-1 + c_2x^k-2 + ... + c_k = 0

Which of the following is NOT a technique for solving non-linear recurrence relations?

Gaussian elimination
Fixed-point theory
Iteration and simulation
Numerical methods

In which field are recurrence relations commonly used to analyze algorithms?

Biology
Economics
Computer science
Physics

What is the primary challenge in solving non-linear recurrence relations?

Lack of a general method for solution
Complexity of the characteristic equation
Difficulty in finding initial conditions
Limited applications

Which of the following is a correct statement about the roots of the characteristic equation in solving linear recurrence relations?

The roots are always real and positive
The roots determine the general form of the solution
The roots are always imaginary
The roots are always zero

What is the purpose of the initial condition or base case in solving recurrence relations?

To simplify the recurrence relation
To find the characteristic equation
To solve the recurrence relation without any method
To determine a unique solution

Chapter 7: Algorithms and Complexity

What is an algorithm in the context of computer science?

A step-by-step procedure or formula for solving a problem, designed to be executed by a computer.
A method for storing data.
A type of programming language.
A hardware component of a computer.

Which of the following is NOT a type of algorithm analysis?

Time Complexity
Space Complexity
Algorithm Synthesis
Performance Metrics

What does Big O notation describe in the context of algorithm analysis?

The lower bound of the running time or space complexity.
The memory usage of an algorithm.
The average running time or space complexity.
The upper bound of the running time or space complexity.

Which of the following is an example of an NP-complete problem?

The Traveling Salesman Problem
Calculating the factorial of a number
Sorting a list of numbers
Finding the shortest path in an unweighted graph

What is the primary goal of algorithm analysis?

To debug existing algorithms.
To design new algorithms.
To optimize code for better readability.
To predict performance and compare different algorithms.

Which asymptotic notation describes both the upper and lower bounds of the running time or space complexity?

Big O notation (O)
Little o notation (o)
Big Omega notation (Ω)
Big Theta notation (Θ)

What does it mean for a problem to be NP-complete?

It is a problem that can be solved in constant time.
It can be solved in polynomial time.
It is in the class of NP and is also NP-hard, meaning all other problems in NP can be reduced to it.
It is easy to solve and has a simple algorithm.

Which of the following is a characteristic of sorting algorithms?

They arrange data in a specific order.
They generate random numbers.
They perform arithmetic operations.
They encrypt data.

What is the purpose of asymptotic notation in algorithm analysis?

To count the number of lines of code in an algorithm.
To describe the running time or space complexity of an algorithm.
To measure the physical size of an algorithm.
To analyze the syntax of an algorithm.

Which of the following is NOT a category of algorithm complexity?

Resource Complexity
Space Complexity
Time Complexity
Algorithm Efficiency

Chapter 8: Boolean Algebra

What is the result of the Boolean operation NOT 1?

False
True
1
0

What is the result of the Boolean operation 1 AND 0?

True
1
0
False

What is the result of the Boolean operation 1 OR 0?

0
1
True
False

Which of the following is NOT a basic Boolean operation?

XOR
AND
NOT
OR

What is the truth value of the Boolean expression P AND (Q OR NOT P) when P is 1 and Q is 0?

True
1
0
False

Which of the following is a correct truth table for the Boolean function f(P, Q) = P OR Q?

P Q f(P, Q) 0 0 0 0 1 0 1 0 0 1 1 0
P Q f(P, Q) 0 0 0 0 1 1 1 0 1 1 1 1
P Q f(P, Q) 0 0 1 0 1 1 1 0 1 1 1 0
P Q f(P, Q) 0 0 1 0 1 0 1 0 0 1 1 1

What is the Boolean expression for the K-map with the following 1s: 0000, 0001, 0010, 0100, 1000, 1001, 1010, 1100?

A OR B OR C OR D
A OR B OR C AND NOT D
A AND B AND C AND NOT D
A AND B AND C AND D

Which of the following is a common application of Boolean algebra in digital circuits?

Data Storage
Memory
Logic Gates
Arithmetic Operations

What is the result of the Boolean operation NOT (P AND Q) when P is 1 and Q is 0?

True
False
1
0

Which of the following is a correct truth table for the Boolean function f(P, Q) = P AND NOT Q?

P Q NOT Q f(P, Q) 0 0 1 1 0 1 0 0 1 0 1 0 1 1 0 1
P Q NOT Q f(P, Q) 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1
P Q NOT Q f(P, Q) 0 0 1 0 0 1 0 1 1 0 1 0 1 1 0 1
P Q NOT Q f(P, Q) 0 0 1 0 0 1 0 0 1 0 1 1 1 1 0 0

Chapter 9: Advanced Counting Techniques

Which principle is used to find the number of elements in the union of multiple sets?

Pigeonhole Principle
Inclusion-Exclusion Principle
Recursive Counting
Counting with Constraints

According to the Pigeonhole Principle, if 15 items are put into 5 containers, then at least one container must contain how many items?

4 items
3 items
2 items
5 items

Which technique involves breaking down a counting problem into smaller subproblems?

Pigeonhole Principle
Inclusion-Exclusion Principle
Recursive Counting
Counting with Constraints

If you need to count the number of ways to arrange 5 objects in a row with the constraint that no two adjacent objects are the same, which technique would you use?

Recursive Counting
Pigeonhole Principle
Inclusion-Exclusion Principle
Counting with Constraints

The Inclusion-Exclusion Principle formula for three sets A, B, and C is given by:

|A ∪ B ∪ C| = |A| + |B| + |C| + |A ∩ B ∩ C|
|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C|
|A ∪ B ∪ C| = |A| + |B| + |C|
|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|

The Pigeonhole Principle states that if n items are put into m containers, with n > m, then at least one container must contain at least how many items?

1 item
3 items
4 items
2 items

Which of the following is NOT a technique mentioned in the chapter?

Recursive Counting
Divide and Conquer
Pigeonhole Principle
Inclusion-Exclusion Principle

If you are counting the number of ways to distribute 10 different items into 3 different boxes, which technique would you NOT use?

Pigeonhole Principle
Recursive Counting
Inclusion-Exclusion Principle
Counting with Constraints

The ceiling function, denoted by ⌈x⌉, rounds x up to the nearest:

integer
decimal
negative number
fraction

In the context of the Inclusion-Exclusion Principle, what does the term 'intersections of the sets' refer to?

Elements that belong to more than one set
The total number of sets
Elements that belong to exactly one set
Elements that do not belong to any set

Chapter 10: Discrete Probability

What is the probability of an event A, denoted by P(A), in discrete probability?

The ratio of favorable outcomes to total outcomes
A measure of the likelihood that event A will occur
The complement of event A
The number of outcomes in event A

Which of the following is NOT a property of probability?

Normalization: P(Ω) = 1
Additivity: P(A ∪ B) = P(A) + P(B) for mutually exclusive events A and B
Non-negativity: P(A) ≥ 0 for any event A
Probability can be negative

What does the Probability Mass Function (PMF) P(X = x) represent?

The probability that a discrete random variable X is exactly equal to some value x
The probability that a discrete random variable X is less than or equal to x
The spread of values of a discrete random variable X
The average value of a discrete random variable X

Which of the following is an example of a discrete random variable?

The time it takes for a customer to arrive at a service center
The weight of a randomly selected item
The number of heads in a series of coin tosses
The temperature in a room

What is the expected value E(X) of a discrete random variable X with PMF P(X = x)?

E(X) = ∑(x - E(X))^2 * P(X = x)
E(X) = ∑x * P(X = x)
E(X) = ∑P(X = x)
E(X) = ∑x^2 * P(X = x)

What does the variance Var(X) of a discrete random variable X measure?

The probability that the random variable takes a specific value
The average value of the random variable
The spread of its possible values
The complement of the expected value

Which function gives the probability that a discrete random variable X will take a value less than or equal to x?

Probability Mass Function (PMF)
Variance
Expected Value
Cumulative Distribution Function (CDF)

If events A and B are mutually exclusive, what is P(A ∪ B)?

P(A) / P(B)
P(A) - P(B)
P(A) * P(B)
P(A) + P(B)

What is the value of P(Ω), where Ω is the sample space containing all possible outcomes?

-1
0
1
∞

Which of the following is a measure of the central tendency of a random variable?

Cumulative Distribution Function (CDF)
Expectation (or Expected Value)
Variance
Probability Mass Function (PMF)

Readings

No readings available.

Gallery

No Image Available

Ada Lovelace

No Image Available

Alan Turing

No Image Available

Bell Labs

No Image Available

Charles Babbage

No Image Available

Claude Shannon

No Image Available

Donald Knuth

No Image Available

Euclid

No Image Available

George Boole

No Image Available

Google

No Image Available

IBM

No Image Available

Institute for Advanced Study

No Image Available

Leonhard Euler

No Image Available

Microsoft Research

No Image Available

MIT

No Image Available

Paul Erdős

No Image Available

Pierre de Fermat

No Image Available

Princeton University

No Image Available

Richard Karp

No Image Available

Silicon Valley

No Image Available

Stanford University

No Image Available

Stephen Cook

You must log in to view news articles.

Mathematical Concepts: Discrete Mathematics

Chapter 2: Logic and Proofs

Chapter 3: Combinatorics

Chapter 4: Graph Theory

Chapter 5: Number Theory

Chapter 6: Recurrence Relations

Chapter 7: Algorithms and Complexity

Chapter 8: Boolean Algebra

Chapter 9: Advanced Counting Techniques

Chapter 10: Discrete Probability

Readings

Gallery

Ada Lovelace

Alan Turing

Bell Labs

Charles Babbage

Claude Shannon

Donald Knuth

Euclid

George Boole

Google

IBM

Institute for Advanced Study

Leonhard Euler

Microsoft Research

MIT

Paul Erdős

Pierre de Fermat

Princeton University

Richard Karp

Silicon Valley

Stanford University

Stephen Cook