Data Structures & Algorithms — Complete Review

Notes
Lecture-style revision document | complexity, data structures, sorting, searching and algorithmic reasoning

Chapter 1 — Foundations
Discrete mathematics studies mathematical objects that are separate or countable rather than
continuously varying. Important objects include sets, propositions, relations, functions, graphs, trees, and
integers. From an algorithmic perspective, the key question is how the procedure behaves as the input
grows.

A proposition is a declarative statement that is either true or false. Logical connectives include negation,
conjunction, disjunction, implication, and biconditional. Truth tables provide a systematic way to evaluate
compound propositions. From an algorithmic perspective, the key question is how the procedure
behaves as the input grows.

An implication p → q is false only when p is true and q is false. The contrapositive, ¬q → ¬p, is logically
equivalent to p → q. From an algorithmic perspective, the key question is how the procedure behaves as
the input grows.

Worked examples and review points

Example: If p means 'n is even' and q means 'n² is even', then p → q is true for every integer n. A proof
can be built directly from the definition of an even integer.

Review: distinguish implication from its converse. The converse q → p does not automatically follow from
p → q.
Chapter 2 — Sets
A set is a collection of distinct objects. The notation x ∈ A means x belongs to A. A subset relation A ⊆ B
means every element of A is also an element of B. From an algorithmic perspective, the key question is
how the procedure behaves as the input grows.

Union collects elements belonging to at least one set, while intersection collects elements belonging to
both. The difference A − B contains elements in A that are not in B. The power set P(A) contains every
subset of A. From an algorithmic perspective, the key question is how the procedure behaves as the
input grows.

Set identities such as De Morgan's laws can be verified using membership arguments or truth tables.
From an algorithmic perspective, the key question is how the procedure behaves as the input grows.

Worked examples and review points

Example: If A={1,2,3} and B={3,4,5}, then A∪B={1,2,3,4,5}, A∩B={3}, and A−B={1,2}.

Practice: determine P({a,b,c}) and verify that it has 2³=8 elements.

A relation R on A is a subset of A×A. Reflexivity, symmetry, antisymmetry, and transitivity are key
properties used to classify relations. From an algorithmic perspective, the key question is how the
procedure behaves as the input grows.

Equivalence relations divide a set into equivalence classes. Partial orders describe relationships where
elements can be compared according to specified rules. From an algorithmic perspective, the key
question is how the procedure behaves as the input grows.

Worked examples and review points

Example: f(x)=2x on the integers is injective. Whether it is surjective depends on the chosen codomain.

Practice: test the relation 'has the same parity as' on the integers for reflexivity, symmetry, and
transitivity.
Chapter 4 — Counting
The product rule states that if a process has n■ choices at the first stage and n■ choices at the second
stage, then there are n■n■ total outcomes. From an algorithmic perspective, the key question is how the
procedure behaves as the input grows.

Permutations count ordered arrangements. Combinations count selections where order does not matter.
Factorials and binomial coefficients connect these two ideas. From an algorithmic perspective, the key
question is how the procedure behaves as the input grows.

The pigeonhole principle says that placing more than n objects into n boxes guarantees at least one box
contains at least two objects. From an algorithmic perspective, the key question is how the procedure
behaves as the input grows.

Worked examples and review points

Example: The number of ways to choose three students from ten is C(10,3)=120.

Practice: explain why among 13 people at least two must have birthdays in the same month.
Chapter 5 — Probability Connections
Finite probability spaces assign probabilities to outcomes whose total is one. Conditional probability
describes the probability of an event after information about another event is known. From an algorithmic
perspective, the key question is how the procedure behaves as the input grows.

Independence means that learning one event occurred does not change the probability of the other.
Bayes' theorem provides a method for reversing conditional probabilities. From an algorithmic
perspective, the key question is how the procedure behaves as the input grows.

Counting methods can be used to compute probabilities when outcomes are equally likely. From an
algorithmic perspective, the key question is how the procedure behaves as the input grows.

Worked examples and review points

Example: When selecting two cards without replacement, the probability of the second event depends on
the first event, illustrating conditional probability.

Review: distinguish mutually exclusive events from independent events; mutually exclusive
nonzero-probability events cannot be independent.
Chapter 6 — Recurrence Relations
A recurrence relation defines a sequence by referring to previous terms. Initial conditions are needed to
determine a particular sequence. From an algorithmic perspective, the key question is how the procedure
behaves as the input grows.

Linear homogeneous recurrences with constant coefficients can often be solved using a characteristic
equation. Repeated roots require additional terms such as nr■. From an algorithmic perspective, the key
question is how the procedure behaves as the input grows.

Recurrences also arise naturally in algorithm analysis, where the cost of an algorithm is expressed in
terms of the cost for smaller inputs. From an algorithmic perspective, the key question is how the
procedure behaves as the input grows.

Worked examples and review points

Example: Fibonacci numbers satisfy F■=F■■■+F■■■ with F■=0 and F■=1.

Practice: write the first six terms of a■=2a■■■+1 with a■=0 and identify a pattern.
Chapter 7 — Graph Theory
A graph consists of vertices and edges. Graphs can be directed or undirected, weighted or unweighted.
Degree measures the number of incident edges in an undirected graph. From an algorithmic perspective,
the key question is how the procedure behaves as the input grows.

The handshaking lemma states that the sum of all vertex degrees equals twice the number of edges.
Paths and cycles describe movement through graphs. From an algorithmic perspective, the key question
is how the procedure behaves as the input grows.

Euler paths use every edge exactly once, while Hamiltonian paths use every vertex exactly once. These
concepts solve different classes of problems. From an algorithmic perspective, the key question is how
the procedure behaves as the input grows.

Worked examples and review points

Example: A connected graph in which every vertex has even degree has an Euler circuit.

Practice: for a graph with 15 edges, calculate the total degree across all vertices.
Chapter 8 — Trees
A tree is a connected undirected graph with no cycles. A tree with n vertices has exactly n−1 edges.
Removing any edge disconnects a tree. From an algorithmic perspective, the key question is how the
procedure behaves as the input grows.

Rooted trees provide hierarchical representations. Binary trees restrict each node to at most two children.
Traversals include preorder, inorder, and postorder. From an algorithmic perspective, the key question is
how the procedure behaves as the input grows.

Spanning trees connect all vertices of a connected graph using the minimum number of edges. Minimum
spanning trees are important in network design. From an algorithmic perspective, the key question is how
the procedure behaves as the input grows.

Worked examples and review points

Example: A tree with 20 vertices must have 19 edges.

Review: in a binary search tree, inorder traversal visits keys in sorted order when the ordering property is
maintained.
Chapter 9 — Algorithms and Proof
An algorithm is a finite sequence of well-defined steps for solving a problem. Correctness proofs
establish that an algorithm produces the intended result. From an algorithmic perspective, the key
question is how the procedure behaves as the input grows.

Mathematical induction is useful for proving statements indexed by positive integers. A proof usually has
a base case and an inductive step. From an algorithmic perspective, the key question is how the
procedure behaves as the input grows.

Complexity analysis studies how resource requirements grow with input size. Big-O notation gives an
asymptotic upper bound. From an algorithmic perspective, the key question is how the procedure
behaves as the input grows.

Worked examples and review points

Example: To prove a formula for the sum of the first n integers, verify n=1 and then show that validity for
n implies validity for n+1.

Practice: explain the difference between correctness and efficiency in algorithm design.
Chapter 10 — Revision Problems
1. Prove that the sum of two even integers is even. 2. Determine whether a given relation is an
equivalence relation. 3. Count arrangements under restrictions. 4. Solve a simple recurrence. 5.
Determine degrees in a graph. From an algorithmic perspective, the key question is how the procedure
behaves as the input grows.

Suggested method: first identify the relevant definition, then translate the problem into mathematical
notation, and finally justify every step. From an algorithmic perspective, the key question is how the
procedure behaves as the input grows.

Before an exam, review definitions first. Many discrete mathematics questions become much easier once
the correct definition or theorem is recognized. From an algorithmic perspective, the key question is how
the procedure behaves as the input grows.

Worked examples and review points

Self-check: Can you explain why an equivalence relation produces a partition? Can you state the
handshaking lemma? Can you distinguish a permutation from a combination?

Final note: write complete arguments rather than relying only on numerical answers.