Discrete Mathmatics Notes & PPT

Discrete Math
Instructor : Zeph Grunschlag

Topics	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

Discrete Structure
Instructor: Manfred Huber
Textbook: Mathematical Structures for Computer Science 6th edition
Download slides from here

Class	Readings	Lecture Topics
2	1.1, Notes	Statements and Symbolic Representation
3	1.2, Notes	Propositional Logic
4	1.3, Notes	Quantifiers, Predicates, and Validity
5	1.4, Notes	Predicate Logic
6		Formal Logic continued
7	2.1, Notes	Proof Techniques
8	2.1	Proof Techniques
9	2.2, Notes	Induction
10	2.4, Notes	Recursion and Recurrence Relations
11	3.1, Notes	Sets
12	3.2, 3.3, Notes	Counting
13	3.4, Notes	Permutations and Combinations
15		Combinatorics continued
16	4.1, Notes	Relations
17	4.2	Relations and Topological Sorting
18	4.4, Notes	Relations & Functions
19	Notes	Functions
20		Orders of Magnitude
21	4.6, Notes	Matrices

DISCRETE MATHEMATICS PPT

INSTRUCTOR: Ruay-Shiung Chang

Textbook: Discrete and Combinatorial Mathematics:
An Applied Introduction, by Ralph Grimaldi, 4th edition

SLIDES:

1. Fundamental Principle of Counting (PowerPoint File)
2. Fundamentals of Logic (PowerPoint File)
3. Set Theory (PowerPoint File)
4. Properties of the Integers: Mathematical Induction (PowerPoint File)
5. Relations and Functions (PowerPoint File)
6. Languages: Finite State Machines (PowerPoint File)
7. Relations: The Second Time Around (PowerPoint File)
8. The principle of Inclusion and Exclusion (PowerPoint File)
9. Generating Functions (PowerPoint File)
10. Recurrence Relations (PowerPoint File)
11. An Introduction to Graph Theory (PowerPoint File) 

Discrete Mathematics

Topic	Reading	Slides
Propositional Logic		lec 1
Propositions, Quantifiers	Notes:   Ch 1	lec 2
Quanifiers and Predicates	Notes:   Ch 2	lec 3
Proof Techniques	Notes:   Ch 3	lec 4
Sets	Notes:   Ch 4	lec 5
More Sets	Notes:   Ch 4	lec 6
Functions	Notes:   Ch 4	lec 7
Algorithms and Complexity	Notes:   Ch 4.1 - 4.12	lec 8
Summations and Hotel Infinity	Notes:   Ch 6	lec 9
Summations and Hotel Infinity	Notes:   Ch 4.15, 6.2-6.3	lec 10
Infinite Cardinality, Induction	Notes:   Ch 6	lec 11
Strong Induction and Recursive Definitions	Notes:   Ch 7	lec 12
Inductive definitions, Algorithms	Notes:   Ch 7	lec 13
Algorithms, Counting	Notes:   Ch 8	lec 14
Permutations, Combinations, and PHP		lec 15
Binomial Theorem, Generalized Permutations and   Combinations		lec 16
more counting and Probability		lec 17
Probability		lec 18
Expectation and Variance		lec 19
Recurrences		lec 20
Annihilators		lec 21
Annihilators, etc.	recurrences   handout	lec 22
Divide and Conquer Recurrences	recurrences   handout	lec 23
Relations		lec 24
Equivalence Relations		lec 25
Partial Orders		lec 26
Graphs		lec 27

Lecture notes.
        * Sets
        * Relations
        * Functions and Algorithms
        * Logic and Propositional Calculus
        * Vectors and Matrices
        * Counting and combinatorial problems
        * Probabilities
        * Graph Theory
        * Properties of Integers
        * Algebraic Systems
        * Ordered sets and Lattices
        * Languages, grammers and mac