# Math 55

### Math 55 - Discrete Mathematics -- [4 units]

**Course Format: **Three hours of lecture and two hours of discussion per week.

**Prerequisites: **Mathematical
maturity appropriate to a sophomore math class. 1A-1B recommended.

**Credit Option: **Students
will receive no credit for 55 after taking Computer Science 70.

**Description: **Logic,
mathematical induction sets, relations, and functions. Introduction to graphs,
elementary number theory, combinatorics, algebraic structures, discrete
probability theory.

**Textbook: **Rosen,** Discrete
Mathematics and its Applications, 8th edition**

**Outline of the Course:**

**Week 1:** Propositional logic, quantifiers, rules of inference, proof techniques (Chapter 1)

**Week 2:** Sets, functions, countability and uncountable sets (Sections 2.1-2.5)

**Week 3:** Division algorithm, modular arithmetic, primes, GCD (Sections 4.1-4.3)

**Week 4:** Euclidean algorithm, modular exponentiation, solving congruences, Chinese Remainder Theorem, applications to cryptography (Sections 4.4-4.6)

**Week 5:** Induction and recursion, recursive algorithms (Sections 5.1-5.4; revisit 2.4 for summations)

**Week 6:** Counting, pigeon hole principle, permutations and combinations, binomial coefficients, distributions, Stirling numbers (Sections 6.1-6.5)

**Week 7:** Discrete probability theory, conditional probability, independence, random variables (Sections 7.1-7.2)

**Week 8:** Bayes' Theorem and applications (Section 7.3) Expected value, variance, Chebyshev's inequality (Section 7.4)

**Week 9:** Recurrence relations and generating functions (Sections 8.1-8.2 and Examples 10-15 in 8.4)

**Week 10:** Inclusion-exclusion, derangements, formula for Stirling numbers (Sections 8.5, 8.6)

**Week 11:** Relations, directed graphs, transitive closure, equivalence relations, set partitions, partial orders (Section 9.1, part of 9.3 on digraphs, 9.4-9.6)

**Week 12:** Graphs, isomorphism, connectivity (Sections 10.1-10.4)

**Week 13:** Trees, spanning trees, minimum-weight spanning trees (Sections 11.1, 11.4-11.5)

Additional topics of the instructor's choice to be incorporated at appropriate points to complete the full semester.