Mathematics for Computer Science
Not rated yetRate this bookMathematics for Computer Science by Eric Lehman, F. Thomson Leighton, and Albert R. Meyer develops proof, discrete structures, counting, probability, and recurrence analysis. This guide follows the twenty-one chapters of the May 18, 2015 MIT text and emphasizes constructing arguments that can be checked step by step.
Free reading is available at the official source. Opens in a new tab.
FreeAbout this book
Mathematics for Computer Science by Eric Lehman, F. Thomson Leighton, and Albert R. Meyer develops proof, discrete structures, counting, probability, and recurrence analysis. This guide follows the twenty-one chapters of the May 18, 2015 MIT text and emphasizes constructing arguments that can be checked step by step.
How to study this book
Write complete definitions before using a theorem, and separate an example from a proof. For each solution, identify the claim, assumptions, method, and conclusion. Test conjectures with small cases or code when useful, but explain why the argument covers all permitted cases. Keep a record of counterexamples to overly broad claims.
Chapter-wise explanations and study tasks
Chapter 1 — What Is a Proof?
Propositions, predicates, axioms, implications, cases, and contradiction establish the structure of mathematical arguments. A convincing proof must make its logical dependencies visible.
Study task: Write a short implication proof and identify the assumption used at each step.
Chapter 2 — Well Ordering
The well-ordering principle provides a way to reason through a least counterexample or minimal element. Check that the set under discussion satisfies the required conditions.
Study task: Prove a simple integer claim by assuming a least counterexample and deriving a smaller one.
Chapter 3 — Logical Formulas
Logical notation makes connectives and quantifiers precise. The order and scope of quantifiers can change a claim completely, especially when forming its negation.
Study task: Translate a quantified statement into plain language and construct its exact negation.
Chapter 4 — Mathematical Data Types
Sets, relations, functions, and related structures supply precise objects for later arguments. A definition should determine what is allowed rather than rely on an intuitive picture alone.
Study task: Define a relation on a small set and test the properties relevant to your intended classification.
Chapter 5 — Induction
Induction connects a starting case with a general step. Strong induction and related forms require a clearly stated hypothesis and a step that actually reaches every intended case.
Study task: Prove a sequence property and explain why its base cases are sufficient.
Chapter 6 — Recursive Data Types
Recursive definitions organize objects and support structural induction. Distinguish the rule for constructing an object from a claim about every object constructed by that rule.
Study task: Define a recursive structure and prove one property by structural induction.
Chapter 7 — Infinite Sets
Infinite-set comparisons use precise mappings and distinguish different notions of size. A familiar finite intuition may fail when applied to infinite collections.
Study task: Construct a countability argument and contrast it with a diagonal-style obstruction.
Chapter 8 — Number Theory
Divisibility, modular arithmetic, and related integer tools support rigorous analysis of discrete problems. State the conditions under which an inverse, congruence manipulation, or theorem is valid.
Study task: Solve a small modular problem and justify the conditions that permit each algebraic step.
Chapter 9 — Directed Graphs and Partial Orders
Directed relationships and order structures describe dependencies and constraints. Translate an application into a graph before applying an ordering or path argument.
Study task: Model a small task-dependency problem and explain whether a valid execution ordering exists.
Chapter 10 — Communication Networks
Network models connect structural properties with communication behavior. A claim about routing or congestion depends on the graph and the demands imposed on it.
Study task: Analyze a small network under a specified communication pattern and identify a bottleneck.
Chapter 11 — Simple Graphs
Undirected graph concepts support reasoning about adjacency, paths, connectivity, and other discrete relationships. Check whether the graph model preserves the feature of the application you are studying.
Study task: Formulate and prove a small graph claim, then test whether it remains true after removing an assumption.
Chapter 12 — Planar Graphs
Planarity imposes constraints on how graphs can be embedded without crossings. Distinguish a drawing with crossings from a proof that no crossing-free drawing exists.
Study task: Apply a planar-graph bound to a candidate graph and explain what the result establishes.
Chapter 13 — Sums and Asymptotics
Summation techniques and asymptotic notation organize the size and growth of expressions. Bounds need their domains and constants, and a leading-term intuition is not a complete proof.
Study task: Bound a sum above and below and derive an asymptotic classification.
Chapter 14 — Cardinality Rules
Counting requires a clear description of the objects and how cases overlap or correspond. Product, sum, and other counting principles can fail when distinct cases are not actually disjoint.
Study task: Count a constrained collection in two ways and reconcile the answers.
Chapter 15 — Generating Functions
Generating functions encode sequences as coefficients and turn some counting relationships into algebra. The coefficient interpretation must remain explicit throughout the manipulation.
Study task: Build a generating function for a small counting problem and extract a specified coefficient.
Chapter 16 — Probability Spaces
Events and probability spaces formalize uncertainty in discrete models. Define outcomes and their weights before applying event operations or bounds.
Study task: Construct a finite sample space and compute an event probability directly and through a counting argument.
Chapter 17 — Conditional Probability
Conditioning changes the relevant probability model, while independence is a specific relationship requiring justification. Avoid confusing a conditional probability with its reverse.
Study task: Use a small table to compare two reversed conditional probabilities and explain their difference.
Chapter 18 — Random Variables
Random variables turn outcomes into numerical quantities, supporting distributions and expectation. Linearity of expectation can be useful without assuming independence, but other manipulations need additional conditions.
Study task: Define indicator variables for a counting problem and compute the expected total.
Chapter 19 — Deviation from the Mean
Deviation bounds connect average behavior with the chance of large departures. Different bounds use different assumptions and can vary greatly in usefulness.
Study task: Compare two applicable bounds for a stated variable and explain why neither is automatically an exact probability.
Chapter 20 — Random Walks
Random walks connect repeated random changes with hitting and long-run questions. Specify boundaries, transition behavior, and the quantity of interest before deriving a result.
Study task: Analyze a small bounded random walk and check one predicted quantity with simulation.
Chapter 21 — Recurrences
Recurrences describe a quantity through smaller instances and require base conditions. A plausible growth guess must be checked against the recurrence and justified by a valid method.
Study task: Formulate a recurrence for a simple algorithm and prove a proposed bound with explicit base cases.
Applied assignment
Create a discrete-mathematics portfolio with one proof, one graph model, one counting problem, one probability calculation, and one recurrence analysis. For each, state definitions, present the argument, check a small instance, and provide a counterexample showing why an assumption matters. Use code only as a check, not as a replacement for proof.
Suggested reading plan
Study Chapters 1–7 for proof and mathematical structures, 8–12 for integer and graph applications, 13–15 for growth and counting, 16–20 for probability, and 21 for recurrences. Revisit an earlier proof after each block and improve its precision.
Questions for reflection
- Does the argument prove the general claim or only illustrate it?
- Which assumption prevents the counterexample?
- Are the counting model and probability model describing the same outcomes?
Edition and source notes
The linked MIT text identifies Lehman, Leighton, and Meyer and a revision dated May 18, 2015. This guide follows its twenty-one chapters, including Recurrences at the end. The supplementary exercises are original study prompts and do not provide official problem-set solutions.
This page provides book information and study material. Full-text access is provided by the original publisher or authorised source; a listing does not grant permission to republish the book.
Read our Library Access & Copyright policyExplore the contents
Check the chapters covered in this edition.
Visit the official source
See reading, preview or purchase options.
Save for later
Keep this textbook in your saved collection.
Reader ratings & reviews
Share your thoughts
Your review helps other students choose the right resources.
