Applied MathematicsTextbook

Mathematics for Computer Science

Not rated yetRate 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.

FormatExternal access
LanguageEnglish
SubjectApplied Mathematics
LevelNot specified
No. of pages—
PublishedNot specified

Free reading is available at the official source. Opens in a new tab.

Mathematics for Computer ScienceFree

About 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.

Consult the official source and full text.

About access & copyright

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 policy

Explore 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

Be the first to rate

No ratings yet

0%0%
0%0%
0%0%
0%0%
0%0%

Share your thoughts

Your review helps other students choose the right resources.

Rate this book

How helpful was this book?No sign-up needed. Your rating appears instantly.