CSL105: Discrete Mathematical Structures
I semester: 2005-06
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.
Additional Notes
- 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