Math 55 - Discrete Mathematics -- [4 units]
Course Format: Three hours of lecture and two hours of discussion/workshop per week; at the discretion of the instructor, an additional hour of discussion/workshop or computer laboratory 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. (F,SP)
Textbook: Kenneth H. Rosen, Discrete Mathematics and Its Applications, McGraw Hill, custom UC Berkeley paperback 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.3, and part of 2.4 on cardinality) Algorithms, halting problem (Section 3.1), also discuss undecidability in lectures
Week 3: Division algorithm, modular arithmetic, primes, GCD (Sections 3.4-3.5)
Week 4: Euclidean algorithm, modular exponentiation, solving conguences, Chinese Remainder Theorem, applications to cryptography (Sections 3.6-3.7)
Week 5: Induction and recursion, recursive algorithms (Sections 4.1-4.4; revisit 2.4 for summations)
Week 6: Counting, pigeon hole principle, permutations and combinations, binomial coefficients, distributions, Stirling numbers (Sections 5.1-5.5)
Week 7: Discrete probability theory, conditional probability, independence, random variables (Sections 6.1-6.2)
Week 8: Bayes' Theorem and applications (Section 6.3) Expected value, variance, Chebyshev's inequality (Section 6.4)
Week 9: Recurrence relations and generating functions (Sections 7.1-7.2 and Examples 10-15 in 7.4)
Week 10: Inclusion-exclusion, derangements, formula for Stirling numbers (Sections 7.5, 7.6)
Week 11: Relations, directed graphs, transitive closure, equivalence relations, set partitions, partial orders (Section 8.1, part of 8.3 on digraphs, 8.4-8.6)
Week 12: Graphs, isomorphism, connectivity (Sections 9.1-9.4)
Week 13: Trees, spanning trees, minimum-weight spanning trees (Sections 10.1, 10.4-10.5)
Week 14 and 15: At the instructor’s discretion
Additional topics of the instructor's choice to be incorporated at appropriate points to complete the full semester.
Other Material: The instructor may cover further topics (e.g., advanced counting techniques, error-correcting codes, graphs and trees, binary relations).