Math 114 Discrete Mathematics
Syllabus
Spring 2018
Text: Discrete Mathematics and its Applications, 6th edition, by Kenneth H. Rosen.
Not all of these topics will be covered in the same depth, and homework will not be assigned from all sections.
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.
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
Topics in chapter 5: multiplicative and additive priciples of counting, principle of inclusion and exclusion, tree diagrams; basic and generalized pigeonhole principle; permutatations, r-permutations, combinations; binomial coefficients, Pascal's triangle.
6 Discrete Probability
§ 6.1 An Introduction to Discrete Probability
§ 6.2 Probability Theory
§ 6.3 Bayes' Theorem
§ 6.4 Expected Value and Variance
Topics in chapter 6: foundations of probability, frequency interpretation, symmetric situations, outcomes, events, sample space, sum rule, principle of inclusion and exclusion; uniform distribution, conditional probability, indepencence, Bernoulli trials, binomial distribution; definition of expected value, frequency interpretation, random variables, linearity of expectation, indepedent random variables, 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
Topics in chapter 8: binary relation, n-ary relation, symmetry, antisymmetry, reflexivity, transitivity, composition; graphs and relations, incidence matrices; closure of a relation, transitive closure; equivalence relation, equivalance class, partition; partial ordering, lexicographic order, Hasse diagrams.
9 Graphs
§ 9.1 Graphs and Graph Models
§ 9.2 Graph Terminology and Special Types of Graphs
§ 9.3 Representing Graphs and Graph Isomorphism
Topics in chapter 9: definition of graphs, vertices (nodes), edges, directed and undirected graphs, applications of graphs; adjacency of vertices, degree (valence), isolated and pendant vertices, the handshaking theorem, complete graphs, cycles, bipartite graphs, local area networks, subgraphs; adjacency lists, adjacency matrices, incidence matrices, isomorphism of graphs.
10 Trees
§ 10.1 Introduction to Trees
§ 10.2 Application of Trees
§ 10.3 Tree Traversal
Topics in chapter 10: definition of trees, unique path theorem for trees, rooted trees, binary trees, ordered rooted trees, applications of trees; binary search trees, sorting algorithms, Huffman codes, game trees; traversal algorithms.
Back to course page