| Date | Summary | Video Recordings | Reference Reading | Lecture Notes | Recitations | Assignments |
| Lecture 1
(Tues Sept 14) |
Introduction, propositions, theorems and proofs Fundamental Theorem of Arithmetic proof by contradiction and contrapositive proved sqrt two and sqrt prime are irrational |
1.1, 1.2 | Rosen 1.1-1.7 Cummings 5.1-5.5 Grimaldi 2.1-2.5 | Lecture 1 | ||
| Lecture 2
(Tues Sept 16) |
Logic, truth tables, quantifiers, sets
revisit proof by contradiction and contrapositive Euclids proof for the infinitude of primes divisors, sum of geometric series, the Cantor set |
2.1, 2.2 |
Cummings 7.1-7.5 Grimaldi 3.1-3.3 |
Lecture 2 | ||
| Lecture 3
(Tues Sept 21) |
Open and closed sets, binary and ternary representations geometric progressions and properties of the Cantor set a new definition of functions, field axioms |
3.1, 3.2, 3.3, 3.4 | Rosen 2.3-2.5 D'Angelo and West Ch 1 | Lecture 3 | ||
| Lecture 4
(Thurs Sept 23) |
Injections, surjections, bijections, function composition cardinality, constructing a bijection from N to Z the Stern-Brocot tree, properties and the rational numbers Q binary matrix representation of the Stern-Brocot tree |
4.1, 4.2 | Rosen 2.3-2.5 Graham & Knuth 4.5 D'Angelo Ch 4 | Lecture 4 | Recitation 1 Logic, quantifiers, proofs, sets, series Problems from Rosen: 1.1: 28, 31, 1.3: 4, 22, 1.4: 50 1.7: 3, 17, 1.8: 30, 2.2: 4, 2.4: 31 | |
| Lecture 5
(Tues Sept 28) |
Stern's diatomic series and array for a bijection from N+ to Q+ rational approximations, the Archimedian property proving the density of rational numbers Cantor's diagonalization argument for uncountability of R |
5.1, 5.2 | Rosen 2.3-2.5 Graham and Knuth 4.5 D'Angelo & West 4 | Lecture 5 | Recitation 2 Injections, surjections, bijections, countability Problems from Rosen: 2.3: 3, 7, 10, 21, 26, 44a 2.4: 35, 36 and 2.5: 3, 28 |
Homework 1 Solution |
| Lecture 6
(Thurs Sept 30th) |
Stating and proving the principle of induction examples of proof by ordinary induction covering any 2nx2n chessboard missing a square with L-shaped trominoes |
6.1, 6.2 | Rosen Ch 5 Cummings Ch 4 D'Angelo & West 3 | Lecture 6 | ||
| Lecture 7
(Tues Oct 5th) |
The principle of strong induction examples of proof by strong induction |
7 | Rosen Ch 5 Cummings Ch 4 D'Angelo & West 3 | Lecture 7 | ||
| Lecture 8
(Thurs Oct 7th) |
Proving the Fundamental Theorem of Arithmetic Euclids Lemma, Gauss's Lemma, Bezouts Identity The Well Ordering Principle The Euclidean and Extended Euclidean Algorithms |
8.1, 8.2 | Rosen Ch 4 | Lecture 8 | Recitation 3 Ordinary and Strong Induction Problems from Rosen: 5.1: 4, 5, 7, 28, 32, 36 5.2: 12 |
Practice Exam 1 Solution |
| Lecture 9
(Tues Oct 12th) |
Review for Exam 1 |
9 | Rosen 1, 2, 4, 5 | |||
| Lecture 10
(Thurs Oct 14th) |
Exam 1 |
Exam 1 Solution |
||||
| Lecture 11
(Tues Oct 19th) |
Relations, equivalence relations, congruence classes directed graphs, Hasse diagrams, residues |
11.1 , 11.2 | Rosen Ch 9, 4.4 - 4.6 | Lecture 11 | Lecture 12
(Thurs Oct 21st) |
Properties of relations, congruence classes, groups modular inverses, a roadmap to solving linear congruences |
12.1 , 12.2 | Rosen Ch 9, 4.4 - 4.6 | Lecture 12 | Recitation 4 Relations, Equivalence Relations, Congruence Classes |
Homework 2 Solution |
Lecture 13
(Tues Oct 26th) |
Solving linear congruences, systems of linear congruences Chinese Remainder Theorem Fermat's Little Theorem, two proofs (direct and via counting necklaces) |
13 | Rosen 4.4 - 4.6 | Lecture 13 | Lecture 14
(Thurs Oct 28th) |
Fermat Primality Test, pseudoprime numbers Euler's Totient function, examples Euler's generalization of Fermat's Theorem and proof sketch Landau notation, the RSA Algorithm |
14 | Rosen Ch 3, 4.4 - 4.6 | Lecture 14 | Lecture 15
(Thurs Nov 4th) |
RSA Algorithm example, Binomial Theorem, polynomial derivatives Pascal's Triangle, Luca's Theorem and Pascal (mod p) Wilson's Theorem and proof |
15.1 , 15.2 | Rosen Ch 3, 4.4 - 4.6 | Lecture 15 | Lecture 16
(Tues Nov 9th) |
Review for Exam 2 | 16.1 , 16.2 | Rosen Ch 3, 4.4 - 4.6 | Recitation 5 Modular Arithmetic, CRT Fermat's Theorem and Binomial Theorem examples |
Practice Exam 2 Solution |
Exam 2
(Thurs Nov 11th) |
Exam 2 | Exam 2 Solution |
Lecture 17
(Tues Nov 16th) |
Tower of Hanoi, recurrence relations the characteristic equation and polynomial solving linear homogeneous recurrence relations |
17 | Rosen Ch 8.1-8.2 | Lecture 17 | Lecture 18
(Thurs Nov 18th) |
linear homogeneous recurrence relation examples Gaussian elimination, non-homogeneous recurrence relations divide and conquor recurrence relations |
18 | Rosen Ch 8 | Lecture 18 | Homework 3 Solution |
Lecture 19
(Tues Nov 23rd) |
Divide and conquor recurrence relations binary search, recursion trees, complexity master theorem and proof sketch using generating functions to solve recurrence relations Inclusion-Exclusion principle, probability axioms |
19.1 , 19.2 | Rosen Ch 8, 7.1-7.2 | Lecture 19 | Recitation 6 Recurrence Relations Problems from Rosen: 8.1: 8a, 8.2: 3d, 3g, 28 |
Thanksgiving
(Thurs Nov 25th) |
Lecture 20
(Tues Nov 30th) |
Probability Axioms conditional, pairwise and mutual independence Bernoulli trials and the Binomial distribution random variables and probability mass functions conditional, joint and marginal probabilities sums of independent RVs, the central limit theorem Gaussian integral and normal distribution, Bayes theorem expectations, uniform, geometric and poisson distributions |
20 | Rosen Ch 7 | Lecture 20 | Homework 4 | Lecture 21
(Thurs Dec 2nd) |
Expectation and variance examples negative binomial, poisson, geometric and hypergeometric distributions calculating moments of negative binomial and poisson random variables |
21 | Rosen Ch 7 | Lecture 21 | Lecture 22
(Tues Dec 7th) |
Review for Exam 3 | 22 | Rosen Ch 7 | Practice Exam 3 Solution |
Lecture 23
(Thurs Dec 9th) |
Exam 3 | Rosen Ch 7 | Exam 3 Solution |
[back home]