Discrete Math Lecture Notes PPT

Discrete Math

Instructor : Zeph Grunschlag


Lecture Download
Introduction: course policies; Overview, Logic,   Propositions ppt
Tautologies, Logical Equivalences ppt
Predicates and Quantifiers: “there exists” and   “for all” ppt
Sets: curly brace notation, cardinality, containment,   empty set {, power set P(S), N-tuples and Cartesian product. Set Operations:   set operations union and disjoint union, intersection, difference,   complement, symmetric difference ppt
Functions: domain, co-domain, range; image, pre-image;   one-to-one, onto, bijective, inverse; functional composition and   exponentiation; ceiling and floor. Sequences, Series, Countability:   Arithmetic and geometric sequences and sums, countable and uncountable sets,   Cantor’s diagonilation argument. ppt
Big-Oh, Big-Omega, Big-Theta: Big-Oh/Omega/Theta notation,   algorithms, pseudo-code, complexity. ppt
Integers: Divisors Primality Fundamental Theorem of   Arithmetic. Modulii: Division Algorithm, Greatest common divisors/least   common multiples, Relative Primality, Modular arithmetic, Caesar Cipher, ppt
Number Theoretic Algorithms: Euclidean Algorithm for GCD;   Number Systems: Decimal, binary numbers, others bases; ppt
RSA Cryptography: General Method, Fast Exponentiation,   Extended Euler Algorithm, Modular Inverses, Exponential Inverses, Fermat’s   Little Theorem, Chinese Remainder Theorem ppt
Proof Techniques. ppt
Induction Proofs: Simple induction, strong induction,   program correctness ppt
Recursion: Recursive Definitions, Strings, Recursive   Functions. ppt
Counting Fundamentals: Sum Rule, Product Rule,   Inclusion-Exclusion, Pigeonhole Principle Permutations. ppt
r-permutations: P(n,r), r-combinations:   C(n,r), Anagrams, Cards and Poker; Discrete probability: NY   State Lotto, Random Variables, Expectation, Variance, Standard Deviation. ppt
Stars and Bars. ppt
Recurrence Relations: linear recurrence relations with   constant coefficients, homogeneous and non-homogeneous, non-repeating and   repeating roots; Generelized Includsion-Exclusion: counting onto functions,   counting derangements ppt
Representing Relations: Subsets of Cartesian products,   Column/line diagrams, Boolean matrix, Digraph; Operations on Relations:   Boolean, Inverse, Composition, Exponentiation, Projection, Join ppt
Graph theory basics and definitions: Vertices/nodes,   edges, adjacency, incidence; Degree, in-degree, out-degree; Degree,   in-degree, out-degree; Subgraphs, unions, isomorphism; Adjacency matrices.   Types of Graphs: Trees; Undirected graphs; Simple graphs, Multigraphs,   Pseudographs; Digraphs, Directed multigraph; Bipartite; Complete graphs,   cycles, wheels, cubes, complete bipartite. ppt
Connectedness, Euler and Hamilton Paths ppt
Planar Graphs, Coloring ppt
Reading Period. Review session TBA. ppt