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 (Sections 1.1-1.6)
Week 2: Proof techniques and proof writing (Sections 1.7-1.8)
Week 3: Sets, functions, countability and uncountable sets (Sections 2.1-2.5)
Week 4: Division algorithm, modular arithmetic, primes, GCD (Sections 4.1-4.3)
Week 5: Euclidean algorithm, modular exponentiation, solving congruences, Chinese Remainder Theorem (Sections 4.3-4.4)
Week 6: Induction and recursion, recursive algorithms (Sections 5.1-5.4; revisit 2.4 for summations)
Week 7: Counting, pigeon hole principle, permutations and combinations, binomial coefficients, distributions, generalized permutations and combinations (Sections 6.1-6.5)
Week 8: Discrete probability theory, conditional probability, independence, random variables (Sections 7.1-7.2)
Week 9: Bayes' Theorem and applications (Section 7.3) Expected value, variance, Chebyshev's inequality (Section 7.4)
Week 10: Recurrence relations (Sections 8.1-8.2), Inclusion-exclusion (Section 8.5)
Week 11: Relations, transitive closure, equivalence relations, set partitions, partial orders (Sections 9.1, 9.4-9.6)
Week 12: Graphs, isomorphism, connectivity (Sections 10.1-10.4)
Week 13: Optional topics: Cryptography (Section 4.6), Generating functions (Section 8.4), Applications of inclusion-exclusion (Section 8.6), Trees (Section 11.1), Spanning trees (Section 11.4), More on proof techniques or any of the topics in Weeks 1-12
Note: Optional topics may be incorporated at appropriate points in the semester, at the instructor's choice.