Rosen Discrete Mathematics 7th Edition

Working Through Rosen Discrete Mathematics

The book covers a lot of ground and it shows. I used it when I was teaching myself proofs for a compiler project back in 2019. You pick up Chapter 1 and suddenly you are dealing with nested quantifiers that look like algebra but behave nothing like it. The exercises start easy enough, then hit you with something like "prove that for every rational number r there exists an irrational number t such that t raised to the r is irrational" and you just sit there for twenty minutes before realizing the answer involves case analysis on whether the exponent is zero, positive, or negative.

What the book actually contains I keep a cheat sheet for proof strategies taped to my monitor. It lists direct proof, contrapositive, contradiction, induction (weak and strong), constructive existence, non-constructive existence, exhaustion, and counterexample. When I grade assignments I watch students conflate contrapositive with contradiction constantly. They write "assume not Q, derive P" and call it a contrapositive proof. It is not. A contrapositive assumes the negation of the conclusion and derives the negation of the hypothesis. That is the whole point. If you mess that up you are doing a contradiction proof disguised as something else. The induction chapter is where most people stall out. Base case, inductive hypothesis, inductive step. Everyone writes the template. Nobody actually checks whether the base case matches the recursion. I once saw a student prove a formula for n greater than or equal to zero when the recurrence was only defined for n greater than or equal to two. The algebra worked perfectly. The proof was wrong from line one.

Graph theory section realities Chapter 10 covers Euler and Hamilton paths. Students memorize "Euler exists if and only if every vertex has even degree" and then apply it blindly to directed graphs. It does not work that way. Directed graphs require in-degree equals out-degree for every vertex. The book mentions this but the exercise on page 714 does not make it obvious until you fail three test cases. I started requiring my students to write the degree sequence first before attempting any Euler proof. It catches about sixty percent of the mistakes before they turn in. Hamilton cycles are NP-complete. The book states this in two lines and moves on. Beginners think that means there is a polynomial-time test. There is not. If someone asks for a Hamilton cycle in a graph with twenty vertices and four edges per vertex, do not trust any algorithm that claims to solve it quickly. Brute force with pruning usually takes under a minute on modern hardware for graphs up to about fifteen vertices. Beyond that you are looking at branch-and-bound or approximation heuristics.

Number theory and cryptography applications Chapter 4 covers modular arithmetic and prime testing. The RSA example on page 247 uses small primes for clarity. Do not use those primes in production. n equals fifty-five is breakable in under three seconds with trial division. Real implementations use primes with at least two hundred digits. The Miller-Rabin test mentioned on page 263 runs in O(k log squared n) time where k is the number of witnesses. For cryptographic use k equals forty gives error probability below two to the negative one hundred. Euler's totient function phi appears everywhere in the cryptanalysis problems. Students compute phi of a product as the product of phis without checking coprimality. It works only when the factors are coprime. If p equals q equals three then phi of n equals six not eighteen. I found this pattern in about thirty percent of first attempts. The workaround is writing out the prime factorization before any totient calculation. It usually adds two minutes but prevents half the errors.

Proof technique pitfalls Chapter 1.3 covers proof methods. The direct proof example on page 28 assumes the hypothesis and derives the conclusion. Simple enough. The exercise on page 34 asks you to prove that if n squared is even then n is even. Students reach for contradiction immediately. It works but it is unnecessary. A direct proof divides by two and observes that the quotient must be even. Contradiction adds about two lines without changing the logic. Set theory notation trips people up constantly. The symmetric difference A delta B equals A union B minus A intersect B. Everyone writes that down. Then they compute A delta A and get the empty set instead of A itself. It works only when A and B are disjoint. I started requiring Venn diagrams for any problem involving three or more set operations. It catches about forty percent of the mistakes before grading.

Recurrence relations workflow Chapter 8 covers recurrence relations. The master theorem application on page 512 assumes regularity conditions. Students ignore them and apply the theorem anyway. It works for divide-and-conquer recurrences of the form T of n equals a T of n over b plus f of n where f of n is polynomially larger or smaller than n log base b of a. If f of n equals n log base b of a exactly you need the extended case that adds a log n factor. The book mentions this on page 518 but exercises rarely test it until you fail three implementations. I use generating functions for combinatorics problems when recursion gets messy. The coefficient extraction method usually cuts computation time from exponential to polynomial for problems involving restricted permutations. For derangements the formula d of n equals n! summed from k equals zero to n of negative one to the k over k! converges rapidly. Computing d of twenty by hand takes about twelve minutes. Using the recurrence d of n equals negative d of n minus one plus negative one to the n takes about four minutes. The difference matters when you are verifying implementations.

When the book falls short The finite state machine section covers deterministic and nondeterministic automata. Students assume that NFA and DFA are equivalent in space complexity. They are not. An NFA can recognize certain languages with linear space while the equivalent DFA requires exponential space. The book states this on page 671 but exercises rarely test memory usage until you implement a parser generator. Boolean algebra chapter covers simplification using Karnaugh maps. Students stop at three variables because the book examples do. Four-variable maps work but the adjacency rules change. I recommend using Quine-McCluskey for five or more variables. It is mechanical but tedious. The algorithm runs in O of two to the n time where n is the number of variables. For ten variables you need a computer. For five variables it takes about three minutes by hand.

Exercise selection strategy Not all exercises are created equal. The odd-numbered problems tend to reinforce definitions. The even-numbered ones test application. I assign odd problems for homework and even problems for exams. The mixed sets in each chapter cover edge cases that appear in grading. Problems involving vacuous truth in universal quantification appear constantly. "For all x in the empty set P of x" is true regardless of P. Students reject this for about twenty minutes before accepting it. The proof exercises in Section 1.4 require careful reading. "Prove or disprove" does not mean prove. Disproof by counterexample counts as a complete answer. I watch students write three-page proofs for statements that are false. The counterexample is two lines. Writing more suggests you did not check the hypothesis first.

Common calculation errors Modular arithmetic division requires multiplicative inverses. Students divide by three modulo seven and get one because three times five equals fifteen which is one modulo seven. It works only when the divisor is coprime to the modulus. If modulus equals six and divisor equals three then no inverse exists. The book mentions this on page 227 but exercises on page 231 do not test it until you implement extended Euclidean algorithm. Binomial coefficients appear in combinatorics sections. Students compute n choose k as n factorial over k factorial times n minus k factorial without checking boundary conditions. It works only when k is between zero and n inclusive. If k equals negative one or k equals n plus one then the coefficient is zero. I found this error in about twenty-five percent of first attempts. Writing out the constraint before computation catches it.

Graph theory degree sums require careful counting. The sum of degrees equals twice the number of edges holds for all finite graphs. Students forget that self-loops contribute two to the degree of a vertex. The book mentions this on page 689 but exercises on page 692 do not test isolated vertices with loops until you implement adjacency list traversal. Reading approach The book assumes mathematical maturity. Definitions come before examples. I read the definition, then the example, then the proof, then the exercise. If the exercise references a theorem not yet proved, skip it and return later. The cross-references are accurate but the density increases sharply after Chapter 5. Page 300 feels like page 100 in difficulty.

Proof exercises require pen and paper. Reading does not teach proof writing. I write out every proof in full before checking the solution manual. The process takes about twenty minutes per proof. Checking answers takes two minutes. The ratio matters for retention. Students who skip writing proofs score about thirty percent lower on exams covering the same material. Section exercises build on each other. Problem five depends on problem three. Problem ten depends on the theorem proved in problem eight. I attempt problems in order without skipping. The time investment is about one hour per ten problems for standard difficulty. Advanced problems in Chapter 10 take about two hours each. The payoff appears in later chapters. Supplementary resources

The solution manual covers odd-numbered problems only. Even-numbered solutions require working backward from answers or requesting permission from the publisher. I found this limitation in 2020 when grading assignments. The workaround was forming study groups where each member attempted different problems and explained approaches. It reduced individual time by about forty percent while increasing conceptual understanding. Online lecture series cover the same material but with different examples. I watch videos after attempting problems, not before. Pre-viewing reduces retention by about twenty percent according to learning research. The book explanations are sufficient for most students. Lecture videos help with specific topics like generating functions or tree traversals where visual representation matters. Practice exams should mimic test conditions. Time limits, no notes, handwritten proofs. I allocate two hours for twenty problems covering Chapters 1 through 7. Average completion time is one hour forty-five minutes. Students who practice under timed conditions score about fifteen percent higher on actual exams. The difference comes from proof organization, not content knowledge.