# Amitabha Bagchi

### Topics

• Basic logic: Propositional logic: logical connectives; truth tables; normal forms (conjunctive and disjunctive); validity; predicate logic; limitations of predicate logic, universal and existential quantification; modus ponens and modus tollens. Proof techniques: Notions of implication, converse, inverse, contrapositive, negation, and contradiction; the structure of formal proofs; direct proofs; proof by couunterexample; proof by contraposition; proof by contradiction; mathematical induction; strong induction; recursive mathematical definitions; well orderings.
• Fundamental structures; Functions (surjections, injections, inverses, composition); relations (reflexivity, symmetry, transitivity, equivalence relations); sets (Venn diagrams, complements, Cartesian products, power sets); pigeonhole principle; cardinality and countability.
• Basics of counting: Counting arguments; pigeonhole principle; permutations and combinations; inclusion-exclusion, recurrence relations, generating functions.
• Introduction to group theory.
• Introduction to graph theory.

### Course Texts

The primary text book for this class will be:
K. Bogart, S. Drysdale, C. Stein. Discrete Math for Computer Science Students.
Available online.

For the purposes of this class the book has been mirrored locally. You can either download the entire book or you can choose to download it chapterwise:
For Graph Theory, an excellent text available free online (though in unprintable format) is Graph Theory by Reinhard Diestel.

For topics not covered in this text, notes or references will be provided in the Additional Notes section below.

• Notes on cardinality and infinite sets (ps, pdf.) Lecture 2 from Christian Scheideler's 2001 class on Complexity Theory.
Note: Additional notes on Set Theory including the proof of Zorn's Lemma have been photocopied and given to the SCOOPs xerox shop. Please collect them from there.
• Notes on partial orders, well orders and the principle of well ordered induction (ps, pdf.) Lecture 38 from Jonathan Pila's 2004-05 class on Discrete Mathematics.
• Intro to probability theory. (ps, pdf.)
A list of useful reference texts (students are not required to own or consult these.)
• C. L. Liu. Elements of Discrete Mathematics.
• Alan Tucker. Applied Combinatorics.
• R. L. Graham, D. E. Knuth, O. Patashnik. Concrete Mathematics.

### Tutorial Sheets and Exam Papers

• Tutorial Sheet 1. Propositional Logic. (ps, pdf.) Posted 1st August 2005.
• Tutorial Sheet 2. Sets and Mathematical Induction. (ps, pdf.) Posted 7th August 2005.
• Tutorial Sheet 3. Set Theory. (ps, pdf.) Posted 15th August 2005. Important: I have posted a major clarification to the statement of Zorn's Lemma and the solution to Problem 1 (ps, pdf.) Please take a look at this, it will help you solve problem 1 of homework 3. Posted 21st August 2005.
• Tutorial Sheet 4. Pigeonhole Principle. (ps, pdf.) Posted 23rd August 2005.
• Tutorial Sheet 5. Generating Functions. (ps, pdf.) Posted 29th August 2005.
• Tutorial Sheet 6. Recurrences. (ps, pdf.) Posted 13th September 2005.
• Tutorial Sheet 7. Graph Theory: Paths and Cycles. (ps, pdf.) Posted 20th September 2005.
• Tutorial Sheet 8. Graph Theory: continued. (ps, pdf.) Posted 27th September 2005. Correction: In the first line of Problem 3 "smallest" has been replaced by "largest." Posted 1st October 2005. Note: The proof of Vizing's theorem discussed in class is available online.
• Tutorial Sheet 9. Graph Theory: Matchings. (ps, pdf.) Posted 25th October 2005.
• Tutorial Sheet 10. Graph Theory: Connectivity. (ps, pdf.) Posted 7th November 2005.
• Tutorial Sheet 11. Discrete Probability: Sudoku. (ps, pdf.) Posted 14th November 2005. New version posted on 15th November 2005 after Rohit pointed out an error in the earlier version.
• Tutorial Sheet 12. Discrete Probability. (ps, pdf.) Posted 21st November 2005.

### Homework Assignments

• Homework 1. (ps, pdf.) Posted 5th August 2005. Due: 12th August 2005 at the start of class.
• Homework 2. (ps, pdf.) Posted 12th August 2005. Due: 19th August 2005 at the start of class. Modified 19th August 2005.
• Homework 3. (ps, pdf.) Posted 19th August 2005. Due: 26th August 2005 at the start of class.
• Homework 4. (ps, pdf.) Posted 9th September 2005. Due: 15th September 2005 at the start of class.
• Homework 5. (ps, pdf.) Posted 15th September 2005. Due: 22nd September 2005 at the start of class.
• Homework 6. (ps, pdf.) Posted 27th September 2005. Due: 4th October 2005 at the start of class.
• Homework 7. Solve Minor II. Write all proofs completely and in a well organized manner. Homeworks will be graded on understanding and presentation. Posted 21st October 2005. Due: 28th October 2005 at the start of class.
• Homework 8. (ps, pdf.) Posted 27th October 2005. Due: 8th November 2005 at the start of class.
• Homework 9. (ps, pdf.) Posted 10th November 2005. Due: 18th November 2005 at the start of class.
• Homework 10 and 11. (ps, pdf.) Posted 20th November 2005. Due: 29th November 2005 before 11 AM. Slip it under my office door if there is no class that day.
The marks obtained in this homework will be divided up into two as follows.
• Case 1. If you score k >= 5 out of 10: Your two homework scores will be 5 and k-5.
• Case 2. If you score k < 5 out of 10: Your two homework scores will be k and 0.

Note: The TAs have put up an evaluation page explaining their grading policies. Please check that for clarifications regarding graded homeworks before you approach the TAs with regrading requests.

### Evaluation

• 35%: homework assignments. Only the best seven will be counted.
• 20%: quizzes. Only the best four will be counted.
• 10%: I Minor Exam.
• 10%: II Minor Exam.
• 25%: Major Exam.

Amitabha Bagchi