|
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
readme
|
|
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
|
|
