Which Boolean identity correctly simplifies the complement of an AND expression?
12 Discrete Structures and Algorithms Online Quiz Questions
Use this free practice quiz with 20 questions to review 12 Discrete Structures and Algorithms, test your knowledge, and prepare for your next test or exam.
A propositional circuit has three independent Boolean input variables. How many rows are required for its complete truth table?
- A
3
- B
6
- C
8
- D
9
Which precondition is essential for the usual binary-search step that discards half of the remaining array?
- A
The array is sorted.
- B
The array contains no duplicate values.
- C
The target is at the first or last position.
- D
The array has exactly 2k elements.
True or false: Every problem in P is also in NP.
- A
True
- B
False
True or false: During linear search, the loop invariant proves before every iteration that the target is absent from the entire array.
- A
True
- B
False
What is the technical term for a condition that must be true before an algorithm executes?
Using Theta notation, classify the asymptotic growth of 3n2+7n+4.
In a standard loop-invariant proof, the first step is , which shows the invariant holds initially. The second step is , which shows that one iteration preserves it.
In the definition of NP, a proposed yes-answer that can be checked in polynomial time is called a .
Select all gate types that the material identifies as universal gates.
- A
NAND
- B
XOR
- C
NOR
- D
AND
Select all statements that are consistent with the material’s distinction between algorithm correctness and complexity analysis.
- A
Whether the algorithm produces the required result
- B
How resource use grows with input size
- C
Whether the algorithm uses a particular programming language
- D
Whether machine-specific constants are being abstracted away when comparing asymptotic growth
Compare linear search and binary search on an array of length n. Explain the worst-case time bound of each algorithm and state the precondition that makes binary search’s bound valid.
Suppose there is a polynomial-time reduction A≤pB. Which conclusion follows if problem B has a polynomial-time algorithm?
- A
If A≤pB, a fast algorithm for A automatically solves B.
- B
If A≤pB and B is solvable in polynomial time, then A is solvable in polynomial time.
- C
If A≤pB, then A and B must have identical inputs.
- D
If A≤pB, then B is necessarily in P regardless of the status of A.
Which Boolean expression is equivalent to A+AB?
- A
A+B
- B
A
- C
AB
- D
B
True or false: Binary search can correctly discard half of the remaining search interval after each comparison in an arbitrary unsorted array.
- A
True
- B
False
For the circuit f(A,B,C)=(A∧B)∨¬C, what output is produced when A=1, B=0, and C=0?
- A
0, because the AND gate receives a zero
- B
0, because ¬C=0
- C
1, because ¬C=1
- D
1, because both A and B are true
What is the tight asymptotic classification of 3n2+7n+4? Enter your answer in standard Big-Theta notation.
Which statement is a suitable loop invariant for linear search after positions 1 through i−1 have been checked?
- A
The target occurs at position i.
- B
Every position from i through n has already been checked.
- C
The target does not occur in positions 1 through i−1, unless the algorithm has already returned.
- D
The array is sorted through position i−1.
How many rows are required for a complete truth table with five Boolean input variables?
Ignoring constant factors and lower-order effects, which algorithm is generally more scalable for large inputs: one running in O(nlogn) time or one running in O(n2) time?
- A
An O(nlogn) algorithm
- B
An O(n2) algorithm
- C
They must have identical running times
- D
Neither bound gives any information about scalability
Related study packs and tools
2 Limits and Continuity
A progressive guide to interpreting, calculating, and applying limits, asymptotes, continuity, and the Intermediate Value Theorem.
02/14 2. Linear Equations and Applications
A progressive guide to solving linear equations, rearranging formulas, using proportions and percents, and modeling everyday applications with equations.
4 Polar Coordinates
A progressive guide to converting, graphing, differentiating, and integrating polar curves, with emphasis on symmetry, intersections, area, and arc length.
05 Multiple Integrals
A medium-difficulty quiz on double and triple integrals, including regions of integration, applications, density, average value, moments, and integral setup.
5 Sequences
A 14-question quiz on sequences, sequence limits, monotonicity, boundedness, convergence criteria, the Squeeze Theorem, limit laws, and recursive sequences. Questions progress from foundational understanding to applied reasoning.
5 Sequences
A structured guide to defining sequences, evaluating their limits, and proving convergence or divergence using limit laws, bounds, monotonicity, the Squeeze Theorem, and recursive methods.
5 Vector Spaces
A structured guide to vector spaces, subspaces, spans, independence, bases, dimension, and coordinates, with definitions, tests, examples, and a unified problem-solving workflow.
7 Eigenvalues and Eigenvectors
A progressive guide to identifying eigenvalues and eigenvectors, computing eigenspaces, comparing algebraic and geometric multiplicities, and determining when a matrix can be diagonalized.
7 Power Series and Taylor Series
A 14-question assessment on power series, convergence, term-by-term operations, Taylor and Maclaurin series, polynomial approximation, and error bounds. The questions progress from foundational interpretation to applied convergence and approximation problems.
7 Power Series and Taylor Series
A progressive guide to representing functions with power and Taylor series, determining convergence, manipulating series, and controlling approximation error.
09/14 9. Rational Expressions and Functions
A structured guide to simplifying rational expressions, solving rational equations, analyzing rational functions, graphing their key features, and applying them to rates, work, and cost models.
12 Applications of Multivariable Calculus
A connected guide to modeling geometry, motion, mass, fields, work, flux, and optimization with the main tools of multivariable calculus.