12 Discrete Structures and Algorithms

A progressive guide to Boolean logic, circuits, algorithm design and correctness, asymptotic analysis, and the foundations of computational complexity.

and Logic

Boolean variables take values in $\{0,1\}$ , where $0$ represents false and $1$ represents true. provides rules for manipulating these values and simplifying expressions.

Core operations

NOT: $\lnot A$ or $\overline{A}$ , true when $A$ is false.
AND: $A\land B$ or $AB$ , true when both inputs are true.
OR: $A\lor B$ or $A+B$ , true when at least one input is true.
XOR: $A\oplus B$ , true when exactly one input is true.

Useful identities include identity, domination, idempotence, complement, double negation, commutativity, and distributivity. De Morgan’s laws are especially important:

\overline{A+B}=\overline{A}\,\overline{B}, \qquad \overline{AB}=\overline{A}+\overline{B}.

For example, distributivity and the identity law simplify an expression as follows:

A+AB=A(1+B)=A.

The simplification shows that the original expression always has the same value as $A$ , even though it contains an additional term.

Takeaway: Boolean identities establish logical equivalence while often reducing the size of a logical expression or circuit.

Propositional Circuits

A represents a Boolean function as a directed acyclic network. Wires carry values, gates perform Boolean operations, and the output gives the result of the computation. A circuit with $n$ inputs and $m$ outputs defines

f:\{0,1\}^{n}\to\{0,1\}^{m}.

For example,

f(A,B,C)=(A\land B)\lor\lnot C

outputs $1$ when both $A$ and $B$ are true or when $C$ is false. A complete truth table for three inputs has $2^{3}=8$ rows.

Expressions and circuit forms

An expression can be converted into a circuit by replacing each operation with a corresponding gate. A circuit can be converted back into an expression by tracing the signals from inputs toward the output.

A sum-of-products expression is an OR of AND terms, such as

(A\land\lnot B)\lor(\lnot A\land C).

A product-of-sums expression is an AND of OR terms. Truth tables can be used systematically to construct either form. NAND and NOR are universal gates because either gate type alone can be combined to implement NOT, AND, and OR.

Two circuits are equivalent if they produce the same output for every input. This can be shown by comparing truth tables, simplifying their expressions, or proving that they have the same logical meaning.

Takeaway: Truth tables provide exhaustive verification, while Boolean simplification and universal gates support practical circuit construction.

Algorithms and Search

An is a finite, precisely specified procedure that transforms input into output. It should state its input and output, use unambiguous and mechanically executable steps, terminate, and have a correctness argument.

Linear search

Given an array $A[1\dots n]$ and a target $x$ , linear search examines entries from left to right. It returns the first matching position and returns NOT-FOUND if no entry matches. In the worst case, it checks all $n$ entries, so its running time is $O(n)$ .

Binary search

Binary search requires a sorted array. It compares the target with the middle element and discards the half that cannot contain the target. After $k$ iterations, at most

\frac{n}{2^{k}}

entries remain. Reducing the interval to approximately one entry requires about $\log_{2}n$ iterations, giving running time $O(\log n)$ .

The sortedness condition is essential. Without it, discarding half of the array is not justified, so the binary-search reasoning fails.

Takeaway: Choosing an requires matching its method to the input’s structure and verifying that its preconditions hold.

Correctness, Invariants, and Induction

Correctness requires more than producing plausible results. An is correct when it terminates and produces the required output for every valid input.

A formal specification commonly includes:

a precondition describing what must be true before execution;
a postcondition describing what must be true after successful execution; and
a termination argument.

For an that finds the maximum element of an array, a precondition is that the array is nonempty, expressed as $n\geq 1$ . The postcondition is that the returned value is an array element and is at least as large as every array element.

Invariants and induction

A is maintained throughout a loop. For linear search, after positions $1$ through $i-1$ have been checked, an appropriate invariant is that $x$ does not occur in those checked positions unless the has already returned its location.

The proof pattern is:

Initialization: establish the invariant before the first iteration.
Maintenance: show that one iteration preserves the invariant.
Termination: use the invariant and the stopping condition to derive the postcondition.

Recursive algorithms are commonly proved by induction on input size. The proof must establish a base case, prove the recursive step assuming correctness for smaller inputs, and show progress toward the base case. For example,

\operatorname{sum}(n)= \begin{cases} 0,&n=0,\\ n+\operatorname{sum}(n-1),&n>0 \end{cases}

terminates for nonnegative $n$ because each recursive call decreases $n$ .

Takeaway: Correctness combines a precise specification, an argument that each step preserves what matters, and a justification that execution ends.

Growth of Functions

Efficiency is described by how a cost function grows as the input size $n$ increases. gives an asymptotic upper bound, while big- $\Omega$ gives an asymptotic lower bound and big- $\Theta$ gives a matching upper and lower bound.

For eventually nonnegative functions, $f(n)=O(g(n))$ means that there are constants $c>0$ and $n_{0}$ such that

0\leq f(n)\leq c g(n)

for every $n\geq n_{0}$ . The statement $f(n)=\Theta(g(n))$ means both $f(n)=O(g(n))$ and $f(n)=\Omega(g(n))$ .

For example,

3n^{2}+7n+4=\Theta(n^{2}),

because the quadratic term dominates the linear and constant terms for large $n$ . Common growth rates, from generally slower to faster, are

1,\quad \log n,\quad n,\quad n\log n,\quad n^{2},\quad n^{3},\quad 2^{n},\quad n!.

Consequently, an $O(n\log n)$ is generally more scalable than an $O(n^{2})$ . Practical performance can still depend on constant factors, memory use, input structure, and implementation details.

Takeaway: Asymptotic notation compares long-run growth while abstracting away machine-specific constants and lower-order terms.

studies the time and space resources required to solve problems as a function of input length. Input length is important: an integer $N$ represented in binary uses $\Theta(\log N)$ bits, not $\Theta(N)$ bits.

A decision problem has a yes-or-no answer. The class $\mathrm{P}$ contains decision problems solvable by a deterministic in polynomial time, such as $O(n)$ , $O(n^{2})$ , or $O(n^{10})$ . The class $\mathrm{NP}$ contains decision problems for which a proposed yes-answer, called a certificate, can be verified in polynomial time. Therefore,

\mathrm{P}\subseteq\mathrm{NP}.

Whether $\mathrm{P}=\mathrm{NP}$ remains an open question.

Reductions and difficulty

A from $A$ to $B$ , written

A\leq_{p}B,

transforms every instance of $A$ into an instance of $B$ in polynomial time while preserving the yes-or-no answer. If $A\leq_{p}B$ and $B$ has a polynomial-time , then $A$ also has one.

A problem is when it belongs to $\mathrm{NP}$ and every problem in $\mathrm{NP}$ can be reduced to it in polynomial time. To prove that a problem $B$ is , show both that $B\in\mathrm{NP}$ and that a known problem reduces to $B$ .

Complexity and correctness answer different questions. Correctness asks whether the always produces the required result; complexity asks how its resource use grows with input size.

Takeaway: Complexity classes and reductions provide a framework for comparing problem difficulty, but efficient resource use never substitutes for a proof of correctness.

Boolean Algebra and Logic