Discrete Mathematics Lectures PPT
based on k.rosen
Click on the blue colored links to download the lectures.
Topics
|
Lecture
Download
|
Introduction: course policies; Overview, Logic, Propositions
| |
Tautologies, Logical Equivalences
| |
Predicates and Quantifiers: "there exists" and "for all"
| |
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
| |
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.
| |
Big-Oh, Big-Omega, Big-Theta: Big-Oh/Omega/Theta notation, algorithms, pseudo-code, complexity.
| |
Integers:
Divisors Primality Fundamental Theorem of Arithmetic. Modulii:
Division Algorithm, Greatest common divisors/least common multiples,
Relative Primality, Modular arithmetic, Caesar Cipher,
| |
Number Theoretic Algorithms: Euclidean Algorithm for GCD; Number Systems: Decimal, binary numbers, others bases;
| |
RSA
Cryptography: General Method, Fast Exponentiation, Extended Euler
Algorithm, Modular Inverses, Exponential Inverses, Fermat's Little
Theorem, Chinese Remainder Theorem
| |
Proof Techniques.
| |
Induction Proofs: Simple induction, strong induction, program correctness
| |
Recursion: Recursive Definitions, Strings, Recursive Functions.
| |
Counting Fundamentals: Sum Rule, Product Rule, Inclusion-Exclusion, Pigeonhole Principle Permutations.
| |
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.
| |
Stars and Bars.
| |
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
| |
Representing
Relations: Subsets of Cartesian products, Column/line diagrams,
Boolean matrix, Digraph; Operations on Relations: Boolean, Inverse,
Composition, Exponentiation, Projection, Join
| |
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.
| |
Connectedness, Euler and Hamilton Paths
| |
Planar Graphs, Coloring
| |
Reading Period. Review session TBA.
|
No comments :
Post a Comment