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

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

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

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

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

5 Counting

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

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

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

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

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