CS1200 - Discrete Mathematics for Computer Science

Meetings  

• Theme 1 : Description: How to describe sets? - 23 meetings

  • Meeting 01 : Thu, Jan 17, 11:00 am-11:50 am

  Administrative announcements.

  References
  Exercises
  Reading

  Administrative announcements.
  

  References:

  None

  • Meeting 02 : Fri, Jan 18, 10:00 am-10:50 am

  Introduction to propositional logic. Propositions. Compound propositions. Truth table.

  References
  Exercises
  Reading

  Introduction to propositional logic. Propositions. Compound propositions. Truth table.
  

  References:

  None

  • Meeting 03 : Mon, Jan 21, 08:00 am-08:50 am

  Implication and double implication. Logical equivalence. Admin: TA introduction

  References
  Exercises
  Reading

  Implication and double implication. Logical equivalence. Admin: TA introduction
  

  References:

  None

  • Meeting 04 : Tue, Jan 22, 01:00 pm-01:50 pm

  Tautology and contradiction. Example translations from English and vice versa.

  References
  Exercises
  Reading

  Tautology and contradiction. Example translations from English and vice versa.
  

  References:

  None

  • Meeting 05 : Thu, Jan 24, 11:00 am-11:50 am

  Lecture cancelled.

  References
  Exercises
  Reading

  Lecture cancelled.
  

  References:

  None

  • Meeting 06 : Fri, Jan 25, 10:00 am-10:50 am

  Arguments and argument forms. Validity of an argument .

  References
  Exercises
  Reading

  Arguments and argument forms. Validity of an argument .
  

  References:

  None

  • Meeting 07 : Mon, Jan 28, 08:00 am-08:50 am

  Inference rules. Example argument.

  References
  Exercises
  Reading

  Inference rules. Example argument.
  

  References:

  None

  • Meeting 08 : Tue, Jan 29, 01:00 pm-01:50 pm

  Tutorial.

  References
  Exercises
  Reading

  Tutorial.
  

  References:

  None

  • Meeting 09 : Thu, Jan 31, 11:00 am-11:50 am

  Predicate logic. Syntax and semantics. Domain of interpretation.

  References
  Exercises
  Reading

  Predicate logic. Syntax and semantics. Domain of interpretation.
  

  References:

  None

  • Meeting 10 : Fri, Feb 01, 10:00 am-10:50 am

  Validity. Examples. Equivalence in predicate logic.

  References
  Exercises
  Reading

  Validity. Examples. Equivalence in predicate logic.
  

  References:

  None

  • Meeting 11 : Mon, Feb 04, 08:00 am-08:50 am

  Inference rules for predicate logic. Arugments and Argument forms in predicate logic. Examples. Notion of proofs.

  References
  Exercises
  Reading

  Inference rules for predicate logic. Arugments and Argument forms in predicate logic. Examples. Notion of proofs.
  

  References:

  None

  • Meeting 12 : Tue, Feb 05, 01:00 pm-01:50 pm

  Tutorial

  References
  Exercises
  Reading

  Tutorial
  

  References:

  None

  • Meeting 13 : Thu, Feb 07, 11:00 am-11:50 am

  Proof techniques. Direct proof. Proof by contrapositive.

  References
  Exercises
  Reading

  Proof techniques. Direct proof. Proof by contrapositive.
  

  References:

  None

  • Meeting 14 : Fri, Feb 08, 10:00 am-10:50 am

  Proof by contradiction. Proof of equivalences. Fallacies. Exhaustive proofs. Cases. Existential proofs

  References
  Exercises
  Reading

  Proof by contradiction. Proof of equivalences. Fallacies. Exhaustive proofs. Cases. Existential proofs
  

  References:

  None

  • Meeting 15 : Mon, Feb 11, 08:00 am-08:50 am

  More examples of proofs.

  References
  Exercises
  Reading

  More examples of proofs.
  

  References:

  None

  • Meeting 16 : Tue, Feb 12, 01:00 pm-01:50 pm

  Short Exam 1

  References
  Exercises
  Reading

  Short Exam 1
  

  References:

  None

  • Meeting 17 : Thu, Feb 14, 11:00 am-11:50 am

  Principle of mathematical induction. Induction examples.

  References
  Exercises
  Reading

  Principle of mathematical induction. Induction examples.
  

  References:

  None

  • Meeting 18 : Fri, Feb 15, 10:00 am-10:50 am

  Strong mathematical induction.

  References
  Exercises
  Reading

  Strong mathematical induction.
  

  References:

  None

  • Meeting 19 : Mon, Feb 18, 08:00 am-08:50 am

  Quiz - 1

  References
  Exercises
  Reading

  Quiz - 1
  

  References:

  None

  • Meeting 20 : Tue, Feb 19, 01:00 pm-01:50 pm

  Well ordering principle (WOP). WOP is equivalent to SMI. Defining sets using predicates. Russell's paradox.

  References
  Exercises
  Reading

  Well ordering principle (WOP). WOP is equivalent to SMI. Defining sets using predicates. Russell's paradox.
  

  References:

  None

  • Meeting 21 : Thu, Feb 21, 11:00 am-11:50 am

  Quick recap of sets and functions: injective, surjective and bijective functions. Notions of carnality of sets.

  References
  Exercises
  Reading

  Quick recap of sets and functions: injective, surjective and bijective functions. Notions of carnality of sets.
  

  References:

  None

  • Meeting 22 : Fri, Feb 22, 10:00 am-10:50 am

  Cardinality of infinite sets. Countable sets. Set of real numbers is uncountable.

  References
  Exercises
  Reading

  Cardinality of infinite sets. Countable sets. Set of real numbers is uncountable.
  

  References:

  None

  • Meeting 23 : Mon, Feb 25, 08:00 am-08:50 am

  More examples of countable and uncountable sets. Set of all strings. Power set of natural numbers.

  References
  Exercises
  Reading

  More examples of countable and uncountable sets. Set of all strings. Power set of natural numbers.
  

  References:

  None

• Theme 2 : Quantitative: Size of sets - 21 meetings

  • Meeting 24 : Tue, Feb 26, 01:00 pm-01:50 pm

  Tutorial

  References
  Exercises
  Reading

  Tutorial
  

  References:

  None

  • Meeting 25 : Thu, Feb 28, 11:00 am-11:50 am

  Relation between countable sets and Mathematical Induction. Finite sets: Size of finite sets. Introduction to counting.

  References
  Exercises
  Reading

  Relation between countable sets and Mathematical Induction. Finite sets: Size of finite sets. Introduction to counting.
  

  References:

  None

  • Meeting 26 : Fri, Mar 01, 10:00 am-10:50 am

  Basic principles for counting: Product rule. Sum rule. Principle of inclusion exclusion. Examples.

  References
  Exercises
  Reading

  Basic principles for counting: Product rule. Sum rule. Principle of inclusion exclusion. Examples.
  

  References:

  None

  • Meeting 27 : Mon, Mar 04, 08:00 am-08:50 am

  Proof of general inclusion exclusion. Permutation and combinations. Binomial theorem. Multinomial generalization.

  References
  Exercises
  Reading

  Proof of general inclusion exclusion. Permutation and combinations. Binomial theorem. Multinomial generalization.
  

  References:

  None

  • Meeting 28 : Tue, Mar 05, 01:00 pm-01:50 pm

  Tutorial

  References
  Exercises
  Reading

  Tutorial
  

  References:

  None

  • Meeting 29 : Thu, Mar 07, 11:00 am-11:50 am

  Combinatorial Identities. Double counting.

  References
  Exercises
  Reading

  Combinatorial Identities. Double counting.
  

  References:

  None

  • Meeting 30 : Fri, Mar 08, 10:00 am-10:50 am

  Counting via bijections.

  References
  Exercises
  Reading

  Counting via bijections.
  

  References:

  None

  • Meeting 31 : Mon, Mar 11, 08:00 am-08:50 am

  Recurrence relations.

  References
  Exercises
  Reading

  Recurrence relations.
  

  References:

  None

  • Meeting 32 : Tue, Mar 12, 01:00 pm-01:50 pm

  Short Exam 2

  References
  Exercises
  Reading

  Short Exam 2
  

  References:

  None

  • Meeting 33 : Thu, Mar 14, 11:00 am-11:50 am

  Solving linear recurrences - 1

  References
  Exercises
  Reading

  Solving linear recurrences - 1
  

  References:

  None

  • Meeting 34 : Fri, Mar 15, 10:00 am-10:50 am

  Solving linear recurrences - 2

  References
  Exercises
  Reading

  Solving linear recurrences - 2
  

  References:

  None

  • Meeting 35 : Mon, Mar 18, 08:00 am-08:50 am

  Solving Recurrences (contd). Generating functions.

  References
  Exercises
  Reading

  Solving Recurrences (contd). Generating functions.
  

  References:

  None

  • Meeting 36 : Tue, Mar 19, 01:00 pm-01:50 pm

  Generating Functions - 1

  References
  Exercises
  Reading

  Generating Functions - 1
  

  References:

  None

  • Meeting 37 : Thu, Mar 21, 11:00 am-11:50 am

  No instructions day

  References
  Exercises
  Reading

  No instructions day
  

  References:

  None

  • Meeting 38 : Fri, Mar 22, 10:00 am-10:50 am

  Tutorial

  References
  Exercises
  Reading

  Tutorial
  

  References:

  None

  • Meeting 39 : Mon, Mar 25, 08:00 am-08:50 am

  Quiz 2

  References
  Exercises
  Reading

  Quiz 2
  

  References:

  None

  • Meeting 40 : Tue, Mar 26, 01:00 pm-01:50 pm

  Tutorial

  References
  Exercises
  Reading

  Tutorial
  

  References:

  None

  • Meeting 41 : Thu, Mar 28, 11:00 am-11:50 am

  Structured Sets. Relations. Reflexivity, Symmetry, Antisymmetry and Transitivity. Representing relations using graphs and matrices. Counting the number of reflexive, symmetric relations.

  References
  Exercises
  Reading

  Structured Sets. Relations. Reflexivity, Symmetry, Antisymmetry and Transitivity. Representing relations using graphs and matrices. Counting the number of reflexive, symmetric relations.
  

  References:

  None

  • Meeting 42 : Fri, Mar 29, 10:00 am-10:50 am

  Composition of relations. R is transitive if and only if R^n is contained in R for every n. Closure of relations. Reflexive closure, Symmetric closure, Transitive closure. Graph view.

  References
  Exercises
  Reading

  Composition of relations. R is transitive if and only if R^n is contained in R for every n. Closure of relations. Reflexive closure, Symmetric closure, Transitive closure. Graph view.
  

  References:

  None

  • Meeting 43 : Mon, Apr 01, 08:00 am-08:50 am

  Lecture had to be cancelled due to scheduling issues in view of slot exchange.

  References
  Exercises
  Reading

  Lecture had to be cancelled due to scheduling issues in view of slot exchange.
  

  References:

  None

  • Meeting 44 : Tue, Apr 02, 01:00 pm-01:50 pm

  Applications of PHP - 1

  References
  Exercises
  Reading

  Applications of PHP - 1
  

  References:

  None

• Theme 3 : Structure: Combinatorial and Algebraic structures on sets - 12 meetings

  • Meeting 45 : Thu, Apr 04, 11:00 am-11:50 am

  Applications of PHP - 2

  References
  Exercises
  Reading

  Applications of PHP - 2
  

  References:

  None

  • Meeting 46 : Fri, Apr 05, 10:00 am-10:50 am

  Structured sets. Permutation under composition. Definition of a group. Examples.

  References	Herstein's book on "Abstract algebra" Also see an excellent set of notes at: http://abstract.ups.edu/download/aata-20120811.pdf
  Exercises
  Reading

  Structured sets. Permutation under composition. Definition of a group. Examples.
  

  References:

  Herstein's book on "Abstract algebra" Also see an excellent set of notes at: http://abstract.ups.edu/download/aata-20120811.pdf

  • Meeting 47 : Mon, Apr 08, 08:00 am-08:50 am

  More examples of groups. Basic properties. Subgroups. Cyclic groups.

  References	Herstein's book on "Abstract algebra" Also see an excellent set of notes at: http://abstract.ups.edu/download/aata-20120811.pdf
  Exercises
  Reading

  More examples of groups. Basic properties. Subgroups. Cyclic groups.
  

  References:

  Herstein's book on "Abstract algebra" Also see an excellent set of notes at: http://abstract.ups.edu/download/aata-20120811.pdf

  • Meeting 48 : Tue, Apr 09, 01:00 pm-01:50 pm

  On the size of subgroups. Lagrange's theorem.

  References	Herstein's book on "Abstract algebra" Also see an excellent set of notes at: http://abstract.ups.edu/download/aata-20120811.pdf
  Exercises
  Reading

  On the size of subgroups. Lagrange's theorem.
  

  References:

  Herstein's book on "Abstract algebra" Also see an excellent set of notes at: http://abstract.ups.edu/download/aata-20120811.pdf

  • Meeting 49 : Thu, Apr 11, 11:00 am-11:50 am

  Proof of Lagrange's theorem (contd). More on equivalence classes.

  References	Herstein's book on "Abstract algebra" Also see an excellent set of notes at: http://abstract.ups.edu/download/aata-20120811.pdf
  Exercises
  Reading

  Proof of Lagrange's theorem (contd). More on equivalence classes.
  

  References:

  Herstein's book on "Abstract algebra" Also see an excellent set of notes at: http://abstract.ups.edu/download/aata-20120811.pdf

  • Meeting 50 : Fri, Apr 12, 10:00 am-10:50 am

  Partial orders. Definition and examples.

  References
  Exercises
  Reading

  Partial orders. Definition and examples.
  

  References:

  None

  • Meeting 51 : Sat, Apr 13, 09:30 am-11:00 am

  Tutorial

  References
  Exercises
  Reading

  Tutorial
  

  References:

  None

  • Meeting 52 : Mon, Apr 15, 08:00 am-08:50 am

  Partially ordered sets. Zorn's Lemma. Chains and Antichains. Dilworth's theorem.

  References
  Exercises
  Reading

  Partially ordered sets. Zorn's Lemma. Chains and Antichains. Dilworth's theorem.
  

  References:

  None

  • Meeting 53 : Tue, Apr 16, 01:00 pm-01:50 pm

  Tutorial

  References
  Exercises
  Reading

  Tutorial
  

  References:

  None

  • Meeting 54 : Mon, Apr 22, 08:00 am-08:50 am

  Proof of Dilworth's theorem. Lattices. Examples. More properties of lattices.

  References
  Exercises
  Reading

  Proof of Dilworth's theorem. Lattices. Examples. More properties of lattices.
  

  References:

  None

  • Meeting 55 : Tue, Apr 23, 01:00 pm-01:50 pm

  Tutorial

  References
  Exercises
  Reading

  Tutorial
  

  References:

  None

  • Meeting 56 : Thu, Apr 25, 11:00 am-11:50 am

  Short Exam 3

  References
  Exercises
  Reading

  Short Exam 3
  

  References:

  None