-
Elementary logic
-
Propositions
[R]: ; 1-13, 30-42, 81-86
-
Predicates and quantifiers
[R]: 46-48, 49-58, 67-72, 74-75, 93-95
-
Proofs
-
A few proof techniques
[R]: 99-108; [chomp]
-
A few proof strategies
[R]: 111-123
-
Well-ordered induction
[R]: 427-428; [more]
-
Using the principle of infinite descent
[note]; [sylgall]
-
Mathematical induction
[R]: 395-410, 419-427, 439-443, 444-445
-
Number theory --- covered for grad students
-
Greatest common divisor
[B]: 17, 20-24, 29-30, 132-133
-
Prime numbers
[B]: 39-42, 46-48, 239
-
Modular arithmatic
[B]: 63-67, 71-72
-
Linear congruences
[B]: 33-34, 76-77, 79-81
-
More on congruences
[B]: 150-151, 163-164, 171-172; [CLRS]: 955
-
Primality testing
[B]: 88-90, 91, 93-95; [CLRS]: 956
-
Relations
-
A few properties
[R]: 622-629, 654-655, 657
-
Equivalence relations
[R]: 665-672; [more]
-
Partial ordering
[R]: 677-687, 690-692
-
Dilworth's and Sperner's theorems
[note]
-
Functions
-
Introduction
[R]: 185-188
-
Cardinality of sets
[R]: 225-230
-
Floor and ceiling
[R]: 195-198; [note] --- AR
-
Ackermann's function
[R]: 448 exer 50-54, 56, 62
-
Asymptotic growth of functions
[R]: 270-282
-
Partial recursive functions
[R]: 204-208
-
Counting
-
A few basic rules
[R]: 470-481
-
Permutations and combinations
[R]: 497-504, 516-522
-
Erdos-Ko-Rado theorem
[wiki]
-
Combinatorial arguments
[AZ]: 164-165; [R]: 507-514
-
The pigeonhole principle
[R]: 488-494
-
The principle of inclusion-exclusion
[R]: 605-606, 608-613
-
Occupancy problems
[R]: 522-525
-
Using generating functions
[R]: 583-592, 596, 600 exer 45
-
Discrete probability --- covered for grad students
-
The sample space and events
[F]: 7-24, 33, 35-36, 43, 98-102, 106-107
-
Conditional probability
[F]: 114-125
-
Stochastic independence
[F]: 125-128
-
Random variables
[F]: 212-220; [more]
-
Expectation of a random variable
[F]: 220-223, 293-301, 344-349; [MR]: 84-85
-
Popular distributions
[F]: parts of 146-169, 43-44, 223-224, 228-229
-
A few tail bounds
[MR]: 45-47; [KT]: 758-762
-
Probabilistic method
[note]
-
Recurrences
-
Setting up recurrence relations
[R]: 211-214, 542-549
-
Solving linear recurrence relations
[R]: 557-568
-
Recurrence-tree method
[CLRS]: 88-103
-
Solving with generating functions
[R]: 594-596
-
A few special numbers
[note]
-
Graph theory
-
Introductory terminology
[R]: 704-708, 718-719, 721-722, 730-732; [W]: 1-6
-
The degree-sum formula
[R]: 719-721; [AZ]: 124, 170, 173, 175, 235-236
-
Walks
[R]: 749-757; [W]: 20-23, 29, 71
-
Trees
[R]: 826, 828-830, 833-836; [W]: 67-69, 72
-
Spanning trees
[R]: 870-872, 884; [W]: 25
-
Connectivity
[W]: 152-154, 161, 163-164
-
Eulerian tours
[R]: 764-770; [W]: 26-29
-
Hamiltonian tours
[R]: 770-775; [W]: 288-289
-
Graph isomorphism
[R]: 741-744, 757-759; [W]: 6-11
-
Planar graphs
[R]: 792-801; [pick's]; [crnum]; [szetro]
-
Vertex coloring
[R]: 723, 803-810; [W]: 191-196
-
[R]: Discrete Mathematics and its Applications by Kenneth H. Rosen, Eighth (Indian) Edition.
-
[B]: Elementary Number Theory by David Burton, Seventh Edition.
-
[W]: Introduction to Graph Theory by Douglas B. West, Second Edition.
-
[F]: An Introduction to Probability Theory and its Applications by Willam Feller, Third Edition.
-
AR stands for additional reading (no lecture delivered but included in syllabus).