12 Discrete Structures and Algorithms Free Online FlashCards

Why are NAND and NOR called universal gates?

NAND and NOR are universal gates: either gate type alone can implement NOT, AND, and OR.

What is an algorithm?

An algorithm is a precisely specified finite procedure that transforms input into output and produces a prescribed result.

What precondition makes binary search valid?

Binary search requires a sorted array; this lets it discard half of the remaining interval after each comparison.

When is an algorithm correct?

An algorithm is correct when it produces the required output for every valid input and terminates.

What are the three steps of a loop-invariant proof?

A loop-invariant proof uses initialization, maintenance, and termination to connect a persistent statement to the desired postcondition.

What must a recursive correctness proof establish?

A recursive correctness proof verifies a base case, a recursive step using smaller inputs, and progress toward the base case.

What are De Morgan’s laws in Boolean algebra?

De Morgan’s laws state $\overline{A+B}=\overline A\,\overline B$ and $\overline{AB}=\overline A+\overline B$.

How many rows does a complete truth table with $n$ inputs have?

A circuit with $n$ input variables has $2^n$ possible input combinations, so its complete truth table has $2^n$ rows.

What does $f(n)=\Theta(g(n))$ mean?

$f(n)=\Theta(g(n))$ means both $f(n)=O(g(n))$ and $f(n)=\Omega(g(n))$; the functions have the same asymptotic order.

How many bits are needed to represent $N$ in binary?

A binary representation of the integer $N$ requires $\Theta(\log N)$ bits, not $\Theta(N)$\\) bits.

Simplify $A+AB$.

The expression simplifies to $A$, because $A+AB=A(1+B)=A$.

What is a sum-of-products expression?

A sum-of-products expression is an OR of AND terms, such as $(A\land\lnot B)\lor(\lnot A\land C)$.