# COL202: Discrete Mathematical Structures

# II semester: 2024-25

# Amitabha Bagchi

**Registration note:** COL202 in this semester is open to all students. The registration cap is 100. In case of over-registration, preference will be given to senior students over junior students (since juniors will have more opportunities to register this course in the future). In case there is still over-registration, students will be randomly deregistered. *No special requests for registration will be entertained over email*. Probation students note that your faculty advisor can directly register you in the course through the ERP system, you do not need my permission for this.

All registrants **must read**:

### Timings and Venues

#### Lecture

TBA

#### Tutorial

TBA

### 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 counterexample; proof by
contraposition; proof by contradiction; mathematical induction;
strong induction; recursive mathematical definitions; well
orderings.
- Basics of counting: Counting arguments; pigeonhole
principle; permutations and combinations; inclusion-exclusion,
recurrence relations, generating functions.
- 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.
- Advanced probability: Tail inequalities.
- Intro to graph theory.

### Texts

The primary textbooks for this class will be:

[LLM10] E. Lehman, F. T. Leighton, and A. R. Meyer. Mathematics for Computer Science, Lecture notes from Fall 2010, MIT Open Courseware.

[LLM18] E. Lehman, F. T. Leighton, and A. R. Meyer. Mathematics for Computer Science, June 2018, MIT Open Courseware.
### Other Texts

- [BSD05] K. Bogart, S. Drysdale, C. Stein.
**Discrete Math for Computer Science Students.**

For the purposes of this class the book has been mirrored locally.
- [GKP94] R. L. Graham, D. E. Knuth, O. Patashnik. Concrete Mathematics: A foundation for computer science, 2nd ed. Pearson, 1994. (Available in the Central Library and in affordable Indian edition).
- [Die16] Reinhard Diestel. Graph Theory, 5e, 2016.
- [SAK02] S. Arun-Kumar. Introduction to Logic for Computer Science (WWW draft), IIT Delhi, September 2002.
- [Gallier08] Jean Gallier. Discrete Mathematics for Computer Science: Some Notes. arXiv:0805.0585, 2008.
- [Wilf94] Herbert S. Wilf. generatingfunctionology, Academic Press, 1994.
- [Goemans15] Michael Goemans. Generating functions, Lecture Notes for {\em Principles of Discrete Mathematics}, MIT, 2015.
- [MV08] Jiri Matousek and Jan Vondrak. The Probabilistic Method: Lecture Notes, Charles University, 2008.

### Miscellaneous

### Course calendar

TBA

### Tutorials

#### Tutorial sheets

TBA

### Evaluation

### Policies

Amitabha Bagchi