Meetings

Click on the theme item for the meeting plan for that theme.Click on the meeting item for references, exercises, and additional reading related to it.

**Theme 1 : Foundations: Sets, Sequences, Logic, Proofs.**- 17 meetings- Meeting 01 : Mon, Aug 03, 01:00 pm-01:50 pm
- Meeting 02 : Thu, Aug 06, 10:00 am-10:50 am
- Meeting 03 : Fri, Aug 07, 09:00 am-09:50 am
- Meeting 04 : Mon, Aug 10, 01:00 pm-01:50 pm
- Meeting 05 : Thu, Aug 13, 10:00 am-10:50 am
- Meeting 06 : Fri, Aug 14, 09:00 am-09:50 am
- Meeting 07 : Mon, Aug 17, 01:00 pm-01:50 pm
- Meeting 08 : Thu, Aug 20, 10:00 am-10:50 am
- Meeting 09 : Fri, Aug 21, 09:00 am-09:50 am
- Meeting 10 : Mon, Aug 24, 01:00 pm-01:50 pm
- Meeting 11 : Thu, Aug 27, 10:00 am-10:50 am
- Meeting 12 : Mon, Aug 31, 01:00 pm-01:50 pm
- Meeting 13 : Thu, Sep 03, 10:00 am-10:50 am
- Meeting 14 : Fri, Sep 04, 09:00 am-09:50 am
- Meeting 15 : Mon, Sep 07, 01:00 pm-01:50 pm
- Meeting 16 : Fri, Sep 11, 09:00 am-09:50 am
- Meeting 17 : Mon, Sep 14, 01:00 pm-01:50 pm

Introduction, Musical chairs and pigeon hole principle, Friends and Strangers. <br> Administrative Announcements, grading policy. References Exercises Reading Introduction, Musical chairs and pigeon hole principle, Friends and Strangers.

Administrative Announcements, grading policy.References: None Introduction to Propositional Logic, Logical Operators -- negation, conjunction, disjunction, XOR, conditional, biconditional. Precedence of logical operators. References Section 1.1 from Rosen. Exercises Reading Introduction to Propositional Logic, Logical Operators -- negation, conjunction, disjunction, XOR, conditional, biconditional. Precedence of logical operators.References: Section 1.1 from Rosen. The conditional operator, examples of translating English sentences into compound propositions, logical equivalences, some examples of logic puzzles. References Rosen 1.2, 1.3. Exercises Reading The conditional operator, examples of translating English sentences into compound propositions, logical equivalences, some examples of logic puzzles.References: Rosen 1.2, 1.3. Predicates, definitions, examples, Existential and Universal Quantifiers, Uniqueness quantification using existential and universal quantification, Restricting domain in case of existential and universal quantification. Logical Equivalences between predicates. References Exercises Reading Predicates, definitions, examples, Existential and Universal Quantifiers, Uniqueness quantification using existential and universal quantification, Restricting domain in case of existential and universal quantification. Logical Equivalences between predicates.References: None Predicates with multiple variables. Examples. Nested Quantifiers. Order of Nesting of quantifiers. Examples where the order can be flipped and cases in which it cannot be.<br> Thinking of quantifiers as loops. References Exercises Reading Section 1.4, 1.5 Rosen. Predicates with multiple variables. Examples. Nested Quantifiers. Order of Nesting of quantifiers. Examples where the order can be flipped and cases in which it cannot be.

Thinking of quantifiers as loops.References: None Reading: Section 1.4, 1.5 Rosen. Nested Quantifiers, examples. <br> Arguments, Argument Form. Valid arguments.<br> Rules of Inference. Modus Ponens, Modus Tollens, Addition, Simplification. Why is a particular argument form valid or invalid? References Section 1.5, 1.6 of Rosen. Exercises Reading Nested Quantifiers, examples.

Arguments, Argument Form. Valid arguments.

Rules of Inference. Modus Ponens, Modus Tollens, Addition, Simplification. Why is a particular argument form valid or invalid?References: Section 1.5, 1.6 of Rosen. Rules of Inference. Arguments using these rules of inference. Examples. References Section 1.6 of Rosen. Exercises Reading Rules of Inference. Arguments using these rules of inference. Examples.References: Section 1.6 of Rosen. Proof Techniques: Direct Proof, Proof by contradiction, proof by contraposition. Examples in each case. Pitfalls in proof by enumeration. Example. References Section 1.7 of Rosen. Exercises Reading Proofs from the Book by M. Aigner and G. Ziegler. Proof Techniques: Direct Proof, Proof by contradiction, proof by contraposition. Examples in each case. Pitfalls in proof by enumeration. Example.References: Section 1.7 of Rosen. Reading: Proofs from the Book by M. Aigner and G. Ziegler. Some more examples of Proof by contrapositive, contradiction. Proof by cases, exhaustive proofs. References Section 1.7 Rosen. Exercises Reading Some more examples of Proof by contrapositive, contradiction. Proof by cases, exhaustive proofs.References: Section 1.7 Rosen. Backward reasoning: examples arithmetic and geometric mean. Game of marbles. <br> Existential proofs (non-constructive): examples. Chomp. <br> Proof strategies: checkerboard and tilings. Examples. References Play Chomp online here: <br> http://www.math.ucla.edu/~tom/Games/chomp.html Exercises Reading Backward reasoning: examples arithmetic and geometric mean. Game of marbles.

Existential proofs (non-constructive): examples. Chomp.

Proof strategies: checkerboard and tilings. Examples.References: Play Chomp online here:

http://www.math.ucla.edu/~tom/Games/chomp.htmlIntroduction to Sets, definitions, subsets, null-set, power-set, set operations, computer representation of sets. References Sections 2.1, 2.2 Rosen. Exercises Reading Introduction to Sets, definitions, subsets, null-set, power-set, set operations, computer representation of sets.References: Sections 2.1, 2.2 Rosen. Russels paradox, barber's puzzle. <br> Cardinality of sets, infinite sets, cardinality of infinite sets. <br> Detour to Cartesian Products, relations, function, one-one, onto, one-one onto functions. References Section 2.3 Rosen. Exercises Reading Russels paradox, barber's puzzle.

Cardinality of sets, infinite sets, cardinality of infinite sets.

Detour to Cartesian Products, relations, function, one-one, onto, one-one onto functions.References: Section 2.3 Rosen. Countably infinite sets, Set of integers is countable, set of positive rationals is countable, set of reals is uncountable (Cantor's diagonalization argument). References Section 2.5 Rosen. Exercises Reading Countably infinite sets, Set of integers is countable, set of positive rationals is countable, set of reals is uncountable (Cantor's diagonalization argument).References: Section 2.5 Rosen. Mathematical induction. Why it works. Well ordering principle. Examples using induction and strong induction. References Section 5.1 and 5.2 Rosen. Exercises Reading Mathematical induction. Why it works. Well ordering principle. Examples using induction and strong induction.References: Section 5.1 and 5.2 Rosen. More examples on induction. Sequences. <br> Class by Sreekanth and Parishkrati. References Section 5.2 and Section 2.4 from Rosen. Exercises Reading More examples on induction. Sequences.

Class by Sreekanth and Parishkrati.References: Section 5.2 and Section 2.4 from Rosen. Well ordering principle, proofs using WOP, example on Tournaments and existence of GCD. <br> Brief discussion on recursion and recursively defined objects. Trees. References Section 5.2 and 5.3 from Rosen. Exercises Reading Well ordering principle, proofs using WOP, example on Tournaments and existence of GCD.

Brief discussion on recursion and recursively defined objects. Trees.References: Section 5.2 and 5.3 from Rosen. Recursion, recursive functions, height of a tree, number of nodes. <br> Proving program correctness. Pre-conditions, post-conditions, loop invariants. References Section 5.4, 5.5 or Rosen. Exercises Reading Recursion, recursive functions, height of a tree, number of nodes.

Proving program correctness. Pre-conditions, post-conditions, loop invariants.References: Section 5.4, 5.5 or Rosen. **Theme 2 : Evaluation Meetings**- 6 meetings- Meeting 18 : Fri, Aug 28, 09:00 am-09:50 am
- Meeting 19 : Thu, Sep 10, 10:00 am-10:50 am
- Meeting 20 : Mon, Oct 05, 01:00 pm-01:50 pm
- Meeting 21 : Sat, Oct 17, 09:00 am-09:50 am
- Meeting 22 : Fri, Nov 13, 09:00 am-09:50 am
- Meeting 23 : Sat, Nov 21, 09:00 am-12:00 pm

Short Exam 1. References Exercises Reading Short Exam 1.References: None Quiz 1. References Exercises Reading Quiz 1.References: None Short Exam 2. References Exercises Reading Short Exam 2.References: None Quiz 2. References Exercises Reading Quiz 2.References: None Short Exam-3 References Exercises Reading Short Exam-3References: None End Sem. References Exercises Reading End Sem.References: None **Theme 3 : Relational Structures on sets**- 14 meetings- Meeting 24 : Wed, Sep 16, 09:00 am-09:50 am
- Meeting 25 : Fri, Sep 18, 09:00 am-09:50 am
- Meeting 26 : Mon, Sep 21, 01:00 pm-01:50 pm
- Meeting 27 : Wed, Sep 23, 09:00 am-09:50 am
- Meeting 28 : Thu, Sep 24, 10:00 am-10:50 am
- Meeting 29 : Mon, Sep 28, 01:00 pm-01:50 pm
- Meeting 30 : Thu, Oct 01, 10:00 am-10:50 am
- Meeting 31 : Fri, Oct 02, 09:00 am-09:50 am
- Meeting 32 : Thu, Oct 08, 10:00 am-10:50 am
- Meeting 33 : Fri, Oct 09, 09:00 am-09:50 am
- Meeting 34 : Mon, Oct 12, 01:00 pm-01:50 pm
- Meeting 35 : Thu, Oct 15, 10:00 am-10:50 am
- Meeting 36 : Fri, Oct 16, 09:00 am-09:50 am
- Meeting 37 : Mon, Oct 19, 01:00 pm-01:50 pm

Program termination. Can termination be checked by a general algorithm? Discussion on the halting problem.<br> Relations revisited. Properties of relations. Reflexive, Symmetric, Antisymmetric, Transitive. Examples. <br> References Exercises Reading Program termination. Can termination be checked by a general algorithm? Discussion on the halting problem.

Relations revisited. Properties of relations. Reflexive, Symmetric, Antisymmetric, Transitive. Examples.References: None Relations represented as matrices, diagraphs. closures of relations. Reflexive, symmetric, and transitive closures. Computing them. A naive method to compute transitive closure. Calculation of number of bit operations required for the algorithm. References Exercises Reading Relations represented as matrices, diagraphs. closures of relations. Reflexive, symmetric, and transitive closures. Computing them. A naive method to compute transitive closure. Calculation of number of bit operations required for the algorithm.References: None Warshall's algorithm for computing transitive closure. Calculation of number of bit operations for Warshall's algorithm. References Exercises Reading Warshall's algorithm for computing transitive closure. Calculation of number of bit operations for Warshall's algorithm.References: None Equivalence relations, equivalence classes, partitions. References Exercises Reading Equivalence relations, equivalence classes, partitions.References: None Class cancelled due and moved to 30th Sept. References Exercises Reading Class cancelled due and moved to 30th Sept.References: None Partial orders, examples, Hasse diagram, minimal, maximal elements, least and greatest elements, chains and antichains. References Exercises Reading Partial orders, examples, Hasse diagram, minimal, maximal elements, least and greatest elements, chains and antichains.References: None Graphs as relations, directed graphs, undirected graphs, special types of graphs, paths, cycles, trees, cliques, bipartite graphs. References Exercises Reading Graphs as relations, directed graphs, undirected graphs, special types of graphs, paths, cycles, trees, cliques, bipartite graphs.References: None No Class. Gandhi Jayanti Holiday. References Exercises Reading No Class. Gandhi Jayanti Holiday.References: None Bipartite graphs continued, Matchings in bipartite graphs. Relation between Matching and Vertex cover. Halls theorem. Proof of Halls Theorem. References Chapter 10 from Rosen. Exercises Reading Bipartite graphs continued, Matchings in bipartite graphs. Relation between Matching and Vertex cover. Halls theorem. Proof of Halls Theorem.References: Chapter 10 from Rosen. Konig's theorem and proof of it using Hall's Theorem. Coloring of graphs. Bipartite graphs are 2-colorable. Existence of a K_s implies that the chromatic number is greater than s. Greedy coloring. Introduction to Planar graphs. References Exercises Reading Konig's theorem and proof of it using Hall's Theorem. Coloring of graphs. Bipartite graphs are 2-colorable. Existence of a K_s implies that the chromatic number is greater than s. Greedy coloring. Introduction to Planar graphs.References: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None Planar graphs and properties -- Euler's formula, proof, bound on number of edges of a planar graph. Coloring of planar graphs using 6 colors. Statement of Kuratowaski's theorem (without proof). Definition of Homeomorphism. References Exercises Reading Planar graphs and properties -- Euler's formula, proof, bound on number of edges of a planar graph. Coloring of planar graphs using 6 colors. Statement of Kuratowaski's theorem (without proof). Definition of Homeomorphism.References: None Problem solving session (held by Sreekanth). References Exercises Reading Problem solving session (held by Sreekanth).References: None Class canceled. References Exercises Reading Class canceled.References: None **Theme 4 : Counting and Combinatorics**- 10 meetings- Meeting 38 : Thu, Oct 22, 10:00 am-10:50 am
- Meeting 39 : Mon, Oct 26, 01:00 pm-01:50 pm
- Meeting 40 : Tue, Oct 27, 09:00 am-09:50 am
- Meeting 41 : Thu, Oct 29, 10:00 am-10:50 am
- Meeting 42 : Fri, Oct 30, 09:00 am-09:50 am
- Meeting 43 : Mon, Nov 02, 01:00 pm-01:50 pm
- Meeting 44 : Thu, Nov 05, 10:00 am-10:50 am
- Meeting 45 : Fri, Nov 06, 09:00 am-09:50 am
- Meeting 46 : Mon, Nov 09, 01:00 pm-01:50 pm
- Meeting 47 : Thu, Nov 12, 10:00 am-10:50 am

Basics of Counting -- sum product rule. References Section 6.1 Rosen. Exercises Reading Basics of Counting -- sum product rule.References: Section 6.1 Rosen. Pigeon Hole principle and applications of pigeon hole principle to various problems. References Section 6.2. Exercises Reading Pigeon Hole principle and applications of pigeon hole principle to various problems.References: Section 6.2. Permutations and Combinations, Binomial theorem and identities. Proofs using combinatorial arguments. References Section 6.3 and 6.4 Rosen. Exercises Reading Permutations and Combinations, Binomial theorem and identities. Proofs using combinatorial arguments.References: Section 6.3 and 6.4 Rosen. Permutations and combinations with repetition. Generating permutations and combinations. Algorithms for the same. References Section 6.5 and 6.6 Rosen. Exercises Reading Permutations and combinations with repetition. Generating permutations and combinations. Algorithms for the same.References: Section 6.5 and 6.6 Rosen. Introduction to discrete probability. Examples. Independence and conditional probability. References Section 7.1 and 7.2 of Rosen. Exercises Reading Introduction to discrete probability. Examples. Independence and conditional probability.References: Section 7.1 and 7.2 of Rosen. Examples of independent events. Probabilistic reasoning. Monty Hall 3 Door puzzle. References Section 7.2 Rosen. Exercises Reading Examples of independent events. Probabilistic reasoning. Monty Hall 3 Door puzzle.References: Section 7.2 Rosen. Random variables, expectation, linearity of expectation. Examples. Hatcheck Problem, Number of inversions in a permutation. References Section 7.2 and 7.4 Rosen. Exercises Reading Random variables, expectation, linearity of expectation. Examples. Hatcheck Problem, Number of inversions in a permutation.References: Section 7.2 and 7.4 Rosen. Advanced Counting techniques: modelling problems with recurrences relations. Towers of Hanoi, Fibonacci, Catalan numbers. References Section 8.1 of Rosen. Exercises Reading Advanced Counting techniques: modelling problems with recurrences relations. Towers of Hanoi, Fibonacci, Catalan numbers.References: Section 8.1 of Rosen. Catalan Numbers: Balanced Parenthesis, Number of rooted full binary trees, Diagonal Avoiding paths. Recursive formulation. References See some useful lecture notes on Catalan Numbers: <br> http://mathcircle.berkeley.edu/BMC6/pdf0607/catalan.pdf Exercises Reading Catalan Numbers: Balanced Parenthesis, Number of rooted full binary trees, Diagonal Avoiding paths. Recursive formulation.References: See some useful lecture notes on Catalan Numbers:

http://mathcircle.berkeley.edu/BMC6/pdf0607/catalan.pdfCatalan Numbers -- proof of closed form formula. Equivalence to number of mountain ranges with up and down strokes and the number of ways to parentheize. References Exercises Reading Catalan Numbers -- proof of closed form formula. Equivalence to number of mountain ranges with up and down strokes and the number of ways to parentheize.References: None