| Date | Topic | Reference |
|---|---|---|
| Jan 13 | Introduction to course, Simple examples of Pigeon Hole principle + Administrative announcements | None |
| Jan 14 | Example of Pigeon Hole principle continued | None |
| Jan 16 | Introduction to Logic, Propositions, basic operators, negation, conjunction, disjunction, exclusive OR | Sec. 1.1 [KR] |
| Jan 17 | Implication operator, translating English sentences into formulae | Sec. 1.2 [KR] |
| Jan 18 (extra class) | Double-Implication, Inverse, Converse, Contrapositive, Precedence Rules for opertors, Logical Equivalences, Logic Puzzles (Knights and Knaves) | Sec. 1.3 [KR] |
| Jan 20 | Predicates, Examples, Quantifiers, Domain of variables, What happens when domain is empty? Quantifiers with restricted domains | Sec. 1.4 [KR] |
| Jan 21 | No class. | None. |
| Jan 23 | Predicates and Quantifiers: examples, Translating English sentences to logical formulas and vice versa. There exists exactly one quantifier. | Sec. 1.4 [KR] |
| Jan 24 | Tutorial 1 | None |
| Jan 27 | Logical Equivalences, definition, examples, non-examples. Proving a logical equivalence, disproving a logical equivalence. | Sec. 1.4 [KR], see Ex. 19. |
| Jan 28 | Free variable and bound variables, scope of quantifiers, examples. Equivalences again. Translating English sentences to logical formulas, identifying correct / incorrect conclusions. | Sec. 1.4 [KR] |
| Jan 30 | Nested quantifiers, examples. Order of quantifiers. Argument and Argument forms. Example argument forms. Why are some forms valid versus some invalid? | Sec. 1.5, 1.6 [KR] |
| Jan 31 | Rules of inference and examples. | Sec. 1.6 [KR] |
| Feb 3 | Resolution, Universal / Existential Generalization / Instantiation and examples. | Sec. 1.6 [KR] |
| Feb 4 | Introduction to Proofs, direct proof, proof by contrapositive, proof by contradiction. | Sec. 1.7 [KR] |
| Feb 6 | Examples of proof by contradiction, Euclids proof for infinitely many primes, sqrt(2) is irrational. | Sec. 1.7 [KR], Proofs from the Book |
| Feb 7 | Tutorial 2 | None |
| Feb 10 | Existential proofs, Proof by cases examples, Two player games, winning strategies | Sec. 1.8 [KR] |
| Feb 11 | Chomp : two player game, special cases, n*n, 2*n | Sec. 1.8 [KR] |
| Feb 13 | Chomp continued : player 2 does not have a winning strategy | Sec. 1.8 [KR] |
| Feb 14 | Tutorial 2 -- discussion | None |
| Feb 17 | Quiz 1 | None |
| Feb 18 | Quiz 1 -- discussion; Introduction to Sets. | None |
| Feb 20 | Sets, empty set, universal set, can a universal set exist? Russels paradox. | Section 2.1 [KR] |
| Feb 21 | Responses to Russels paradox, basic set operations -- union, intersection, power set, examples. | Section 2.2 [KR] |
| Feb 24 | Cartesian product, relations, reflexive, symmetric, antisymmetric and transitive relations. Can a relation be both symmetric and antisymmetric? Examples, non-examples | Section 9.1 [KR] |
| Feb 25 | Relations continued, basic counting, number of reflexive, symmetric and antisymmetric relations | |
| Feb 27 | Relations and functions, examples, non-examples | Section 9.1 [KR] |
| Feb 28 | Tutorial 3 | None |
| March 2 | Cardinality of Infinite Sets using functions, cardinality of positive odd integers and positive integers | Section 2.5 [KR] |
| March 3 | Cardinality of Infinite Sets continued, countably infinite sets, cross product of positive integers, introduction to diagonalization, set of reals is uncountable | Section 2.5 [KR] |
| March 5 | Alternate definition of infinite sets. A bijection from A \cup {b} to A. Hilberts Grand Hotel Example. Towards uncomputable functions. | None |
| March 6 | The set of all (C) programs, its cardinality. Example of an uncomputable program. Halting Problem. | None |
| March 9 | No class | None |
| March 10 | Non Instructional Day (Holi) | None |
| March 12 | The technique of proof by Induction, Examples, Induction Trap "All horses are of the same color". | Section 5.1 [KR] |
| March 13 | Proof by Induction, Examples: Odd Pie fight, tiling a square board with triominoes, Proving a stronger induction hypothesis. | Section 5.1 [KR] |
| March 16 | Strong Induction and Principle of Well-ordering. Examples on Tournaments. Difference between proof using Induction and Strong Induction | Section 5.2 [KR] |
| March 17-19 | No Class | None |
| March 20 | Recursion, examples, proving bounds using induction, some important recursive functions. | Section 5.3 [KR] Slides |
| March 23 | Recursion continued, recursive sets, lists and binary trees, recursive sequences. | Section 5.3 [KR] Slides |
| March 24 | Counting, Basic Counting techniques, sum, product, subtraction and division rules. Examples. | Section 6.1 [KR] Slides |
| March 26 | Pigeonhole principle and applications. | Section 6.2 [KR] Slides |
| March 30 | Permutations and Combinations. | Section 6.3 [KR] Slides |
| March 31 | Combinatorial Proofs | Section 6.4[KR] Slides |
| April 2 | Permutations and Combinations with repetitions | Section 6.5[KR] Slides Handout |
| April 3 | Principle of Inclusion Exclusion | Section 8.5[KR] Slides Handout |
| April 6 | Principle of Inclusion Exclusion: Applications | Section 8.5[KR] Slides Handout |
| April 7 | Application of recurrences: Catalan numbers | Section 8.1[KR] Slides Handout |
| April 9 | Solving recurrences: Substitution Method | Section 8.2[KR] Slides Handout |
| April 10 | Tutorial 5 | Tut5 |
| April 13 | Solving recurrences: Linear Homogeneous Recurrences of degree two with constant coefficients. | Section 8.2[KR] Slides Handout |
| April 14 | Solving recurrences: Linear Homogeneous Recurrences with constant coefficients. | Section 8.2[KR] Slides Handout |
| April 16 | Solving recurrences: Linear Non-Homogeneous Recurrences with constant coefficients. Comparing Functions | Section 8.2[KR] Slides Handout Comparing-Functions.pdf |
| April 17 | Structured Sets: Closures of properties. | Section 9.4[KR] Slides Handout |
| April 20 | Structured Sets: Equivalence Relations and Partial Orders. | Section 9.5,9.6[KR] Slides Handout |
| April 21 | Structured Sets: Posets and Lattices. | Section 9.6[KR] Slides Handout |
| April 23 | Structured Sets: Semi-groups, Monoids and Groups. | Section 11.1, 11.2 of C. L . Liu Slides Handout |
| April 24 | Structured Sets: Groups, Subgroups and Genrators. | Section 11.3, 11.4 of C. L . Liu Slides Handout |
| April 27 | Structured Sets: Lagrange's Theorem and proof. | Section 11.3 of C. L . Liu Slides Handout |