CS2100 - Discrete Mathematics for Computer Science

Meetings  

• Theme 1 : Foundations: Sets, Sequences, Logic, Proofs. - 17 meetings

  • Meeting 01 : Mon, Aug 03, 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

  • Meeting 02 : Thu, Aug 06, 10:00 am-10:50 am

  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.

  • Meeting 03 : Fri, Aug 07, 09:00 am-09:50 am

  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.

  • Meeting 04 : Mon, Aug 10, 01:00 pm-01:50 pm

  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

  • Meeting 05 : Thu, Aug 13, 10:00 am-10:50 am

  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.

  • Meeting 06 : Fri, Aug 14, 09:00 am-09:50 am

  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.

  • Meeting 07 : Mon, Aug 17, 01:00 pm-01:50 pm

  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.

  • Meeting 08 : Thu, Aug 20, 10:00 am-10:50 am

  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.

  • Meeting 09 : Fri, Aug 21, 09:00 am-09:50 am

  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.

  • Meeting 10 : Mon, Aug 24, 01:00 pm-01:50 pm

  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.html

  • Meeting 11 : Thu, Aug 27, 10:00 am-10:50 am

  Introduction 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.

  • Meeting 12 : Mon, Aug 31, 01:00 pm-01:50 pm

  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.

  • Meeting 13 : Thu, Sep 03, 10:00 am-10:50 am

  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.

  • Meeting 14 : Fri, Sep 04, 09:00 am-09:50 am

  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.

  • Meeting 15 : Mon, Sep 07, 01:00 pm-01:50 pm

  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.

  • Meeting 16 : Fri, Sep 11, 09:00 am-09:50 am

  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.

  • Meeting 17 : Mon, Sep 14, 01:00 pm-01:50 pm

  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

  Short Exam 1.

  References
  Exercises
  Reading

  Short Exam 1.
  

  References:

  None

  • Meeting 19 : Thu, Sep 10, 10:00 am-10:50 am

  Quiz 1.

  References
  Exercises
  Reading

  Quiz 1.
  

  References:

  None

  • Meeting 20 : Mon, Oct 05, 01:00 pm-01:50 pm

  Short Exam 2.

  References
  Exercises
  Reading

  Short Exam 2.
  

  References:

  None

  • Meeting 21 : Sat, Oct 17, 09:00 am-09:50 am

  Quiz 2.

  References
  Exercises
  Reading

  Quiz 2.
  

  References:

  None

  • Meeting 22 : Fri, Nov 13, 09:00 am-09:50 am

  Short Exam-3

  References
  Exercises
  Reading

  Short Exam-3
  

  References:

  None

  • Meeting 23 : Sat, Nov 21, 09:00 am-12:00 pm

  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

  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

  • Meeting 25 : Fri, Sep 18, 09:00 am-09:50 am

  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

  • Meeting 26 : Mon, Sep 21, 01:00 pm-01:50 pm

  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

  • Meeting 27 : Wed, Sep 23, 09:00 am-09:50 am

  Equivalence relations, equivalence classes, partitions.

  References
  Exercises
  Reading

  Equivalence relations, equivalence classes, partitions.
  

  References:

  None

  • Meeting 28 : Thu, Sep 24, 10:00 am-10:50 am

  Class cancelled due and moved to 30th Sept.

  References
  Exercises
  Reading

  Class cancelled due and moved to 30th Sept.
  

  References:

  None

  • Meeting 29 : Mon, Sep 28, 01:00 pm-01:50 pm

  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

  • Meeting 30 : Thu, Oct 01, 10:00 am-10:50 am

  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

  • Meeting 31 : Fri, Oct 02, 09:00 am-09:50 am

  No Class. Gandhi Jayanti Holiday.

  References
  Exercises
  Reading

  No Class. Gandhi Jayanti Holiday.
  

  References:

  None

  • Meeting 32 : Thu, Oct 08, 10:00 am-10:50 am

  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.

  • Meeting 33 : Fri, Oct 09, 09:00 am-09:50 am

  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

  • Meeting 34 : Mon, Oct 12, 01:00 pm-01:50 pm

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 35 : Thu, Oct 15, 10:00 am-10:50 am

  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

  • Meeting 36 : Fri, Oct 16, 09:00 am-09:50 am

  Problem solving session (held by Sreekanth).

  References
  Exercises
  Reading

  Problem solving session (held by Sreekanth).
  

  References:

  None

  • Meeting 37 : Mon, Oct 19, 01:00 pm-01:50 pm

  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

  Basics of Counting -- sum product rule.

  References	Section 6.1 Rosen.
  Exercises
  Reading

  Basics of Counting -- sum product rule.
  

  References:

  Section 6.1 Rosen.

  • Meeting 39 : Mon, Oct 26, 01:00 pm-01:50 pm

  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.

  • Meeting 40 : Tue, Oct 27, 09:00 am-09:50 am

  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.

  • Meeting 41 : Thu, Oct 29, 10:00 am-10:50 am

  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.

  • Meeting 42 : Fri, Oct 30, 09:00 am-09:50 am

  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.

  • Meeting 43 : Mon, Nov 02, 01:00 pm-01:50 pm

  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.

  • Meeting 44 : Thu, Nov 05, 10:00 am-10:50 am

  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.

  • Meeting 45 : Fri, Nov 06, 09:00 am-09:50 am

  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.

  • Meeting 46 : Mon, Nov 09, 01:00 pm-01:50 pm

  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.pdf

  • Meeting 47 : Thu, Nov 12, 10:00 am-10:50 am

  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
  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