Text: Discrete Mathematics and its Applications, 6th edition, by Kenneth H. Rosen.

1 The Foundations: Logic and Proofs

§ 1.1 Logic
§ 1.2 Propositional Equivalences
§ 1.3 Predicates and Quantifiers
§ 1.4 Nested Quantifiers
§ 1.5 Rules of Inference
§ 1.6 Intruduction to Proofs
§ 1.7 Proof Methods and Strategy

Topics in chapter 1: proposition, truth value, negation, logical operators, compound proposition, truth table, disjuction, conjunction, exclusive or, implication, converse, contrapositive, bit, Boolean variable, bit operation, bit string, bitwise operation; tautology, contradiction, contingency, logical equivalnce, propsitional function De Morgan's laws; predicates, existential quantifier, universal quantifier; nested quantifiers, free & bound variables; rules of inference; theorem, conjecture, proof, lemma, corollary, fallacy, circular reasoning (begging the question), vacuous & trivial proof, direct & indirect proof; proof by cases, counterexample.

2 Basic Structures: Sets, Functions, Sequences, and Summations

§ 2.1 Sets
§ 2.2 Set Operations
§ 2.3 Functions
§ 2.4 Sequences and Summations

Topics in chapter 2: set, axiom, paradox, element, empty set, set equality, subset, finite & infinite set, cardinality, power set,products of sets; union, intersection, disjoint sets, set difference, set complement, symmetric difference, Venn diagrams; function, domain, codomain, image, preimage, range, onto function, 1-1 function, 1-1 correspondence, inverse function, composition, floor, ceiling; sequence, string, summation notation, product notation, countable & uncountable set.

3 The Fundamentals: Algorithms, the Integers, and Matrices

§ 3.1 Algorithms
§ 3.2 The Growth of Functions
§ 3.3 Complexity of Algorithms
§ 3.4 The Integers and Division
§ 3.5 Primes and Greatest Common Divisors
§ 3.6 Integers and Algorithms
§ 3.7 Applications of Number theory

Topics in chapter 3: algorithm, searching algorithm, linear search algorithm, binary search algorithm, time complexity, space complexity, worst-case time complexity, average-case time complexity; divisibility, prime & composite number, Mersenne prime, greatest common divisor, relatively prime, pairwise relatively prime integers, least common multiple, remainder & modulus, encryption & decryption, binary representation, hexadecimal represention, linear combination, inverse modulo n, linear congruence, pseudoprime, private and public key encryption; Euclidean algorithm

4 Induction, and Recursion

§ 4.1 Mathematical Induction
§ 4.3 Recursive Definitions and Structural Induction
§ 4.4 Recursive Algorithms

Topics in chapter 4: mathematical induction; recursive defined functions, sets, and structures; recursive algorithms; iteration.

5 Counting

§ 5.1 The Basics of Counting
§ 5.2 The Pigeonhole Principle
§ 5.3 Permutations and Combinations
§ 5.4 Binomial Coefficients

6 Discrete Probability

§ 6.1 An Introduction to Discrete Probability
§ 6.2 Probability Theory
§ 6.3 Bayes' Theorem
§ 6.4 Expected Value and Variance

8 Relations

§ 8.1 Relations and Their Properties
§ 8.3 Representing Relations
§ 8.4 Closures of Relations
§ 8.5 Equivalence Relations
§ 8.6 Partial Orderings

Back to course page