|
2Date |
Topics
|
Readings
|
Notable |
|
T 1/2
|
L1. Introduction and Overview. Basic set theory
|
|
Course Contract
|
|
Th 1/22
|
L2. Operations on Sets. Russel's Paradox
|
1.1, 1.2
|
|
|
T 1/27
|
L3. Sequences, Strings, Cardinality, Countability,
Cantor's Diagonalization and Uncountability.
Functions: domain, co-domain, range, image,
pre-image, one-to-one, onto, bijective, inverse,
functional composition and exponentiation, ceiling
and floor
|
1.3, 5.1
|
|
|
Th 1/29
|
L4. Number Theory I: Divisors, Primality,
Fundamental Theorem of Arithmetic, Division
Algorithm, Greatest common divisors/least common
multiples, Relative Primality, Euclidean Algorithm
|
1.4
|
|
|
T 2/3
|
L5. Number Theory II: Modular Arithmetic, Number
Systems: Decimal, Binary, Arbitrary Bases, Simple
Ciphers
|
|
|
|
Th 2/5
|
L6. Matrices and Mathematical Structures: Matrix
Operations, Boolean Matrices
|
1.5, 1.6
|
HW1
|
|
T 2/10
|
L7. Logic: Propositions Tautologies, Logical
Equivalences Predicates and Quantifiers: "there
exists" and "forall"
|
2.1, 2.2
|
|
|
Th 2/12
|
L8. Proof Techniques I: Modus Ponens, Indirect,
Contradiction
|
2.3
|
|
|
T 2/17
|
L9. Proof Techniques II: Simple, Strong and
Structural Induction. Program Correctness
|
2.4
|
|
|
Th 2/19
|
L10. Catch-up
|
|
HW2
|
|
T 2/24
|
L11. Permutations: r-permutations
nPr, Counting Anagrams.
Permutation functions. General mono-alphebetic
ciphers.
|
3.1, 5.4
|
QUIZ 1 Covers first two homeworks.
|
|
Th 2/26
|
L12. Combinations: r-combinations
nCr, Counting Poker
Hands
|
3.2
|
|
|
T 3/2
|
L13. Pigeonhole Principle
|
3.3
|
|
|
Th 3/4
|
L14. Discrete Probability: Events, Probability
Spaces, Expectation, Lotteries
|
3.4
|
|
|
T 3/9
|
L15. Simple Recurrence Relations: backtracking and
general solutions to linear homogeneous recurrences
|
3.5
|
HW3
|
|
Th 3/11
|
|
|
MIDTERM covers topics in first three homeworks
|
|
T 3/16
|
SPRING BREAK No class
|
|
No class
|
|
Th 3/18
|
SPRING BREAK No class
|
|
No class
|
|
T 3/23
|
L16. Relations and Partitions: Relational Databases,
Quotients, Digraphs, Relational Matrices, as Subsets
of Cartesian Products, Digraphs
|
4.1, 4.2
|
|
|
Th 3/25
|
L17. Relation Paths and Properties. Connection
with Matrix Operations.
|
4.3, 4.4
|
|
|
T 3/30
|
L18. Equivalence Relations, Equivalence Classes
|
4.5
|
|
|
Th 4/1
|
L19. Catch-up
|
|
HW4
|
|
T 4/6
|
L20. Complexity of Algorithms and the Growth of
Functions: Big-Oh, Big-Omega, Big-Theta
|
5.2, 5.3
|
|
|
Th 4/8
|
L21. Groups: Permutation Groups, Additive and
Multiplicative Groups of Integers, Dihedral Group,
Abelian Groups
|
9.4
|
|
|
T 4/13
|
L22. Rings and Fields: Ring of Integers, Finite
Modular Fields, Fermat's Little Theorem, Chinese
Remainder Theorem
|
9.6
|
|
|
Th 4/15
|
L23. Public Key Cryptography: RSA Encryption,
Diffie-Hellman Key Exchange
|
11.3
|
QUIZ 2 Covers homeworks 3 and 4
|
|
T 4/20
|
L24. Graphs: Vertices/Nodes, Edges, Adjacency,
Degree, Subgraphs, Quotient Graphs, Components,
nions, Bipartite; Complete Graphs, Linear Graphs,
Cycles, Wheels, Cubes, Complete Bipartite
|
8.1, 8.2
|
|
|
Th 4/22
|
L25. Graph Theoretic Problems: Euler and Hamilton
Paths, Graph Isomorphism, Planarity, Coloring
|
8.3, 8.6
|
|
|
T 4/27
|
L26. Catch-up
|
|
HW5
|
|
Th 4/29
|
FINAL LECTURE
|
|
|
|
T 5/4
thru Th
5/6
|
Reading Period.
|
Pick-up last homework
|
Pick-up last homework
|
|
|
FINAL EXAM to be announced
|
|
|
|
