**Code:**CS2020 |

**Category:**PMT |

**Credits:**3-0-0-3

# Learning Objectives

The objective of this course is to cover some of the topics that lie at the foundation of many areas of Computer Science and Engineering. Areas like Algorithm Design and Analysis, Operating Systems, Compilers, Databases and Networks make extensive use of counting techniques and graph theory â€“ the major topics covered in this course.

# Learning Outcomes

The student should be able to identify a variety of problems studied in computer science as questions about graphs, partial orders or other discrete structures. The student should be able to apply the techniques learned here to analyse such questions.

# Syllabus:

**Basic counting** Counting functions, subsets and permutations. Estimation
of factorials and binomial coefficients. Lower bound for sorting
algorithms. (3 lectures)

**Combinatorial Principles** Inclusionâ€“exclusion principle, Bijective
proof, Double counting, Pigeonhole principle, Method of distinguished
element, Twelvefold way. Lower bound for merging algorithms. (6 lectures).

**Graphs** Graphs as models of interaction. Graph isomorphism, subgraphs,
subgraph isomorphism. Degree sequences, Havelâ€“Hakimi algorithm.
Eulerian graphs and Eulerian digraphs. Hamiltonian cycles and Diracâ€™s
Theorem. Computational complexity of these problems (without proofs).
Triangle-free graphs and Mantelâ€™s theorem. (9 lectures).

**Bipartite graphs** Characterization Of Bipartite Graphs.
Matchings,Hallâ€™s Marriage Theorem, KĹ‘nigâ€™s theorem. Edge-colouring of
bipartite graphs. (3 lectures).

**Planar graphs** Eulerâ€™s formula. Vertex colouring of planar graphs, Six
colour theorem and Five colour theorem. (3 lectures).

**Orderings** Partial orders and Hasse diagram. Lattices. Linear extension,
chains and antichains. Scheduling. Mirskyâ€™s theorem and ErdĹ‘sâ€“Szekeres
theorem. (6 lectures).

**Generating Functions** Combinatorial Applications Of Polynomials.
Sequences and Generating functions. Fibonacci and Catalan numbers. Integer
partitions (6 lectures).

**Probabilistic Methods** Proofs by counting. Finite probability spaces and
random variables over them. Basic probabilistic method and method of
expectation. Coupon collector problem. Birthday paradox. (6 lectures).

# Textbook

- Invitation to Discrete Mathematics by JiĹ™Ă MatouĹˇek and Jaroslav NeĹˇetĹ™il (2nd Edition) Oxford University Press (ISBN-13:978-0198570424)

# Reference

- Discrete Mathematics by Norman L. Biggs (2nd Edition, 2002), Oxford University Press (ISBN- 13: 978-0198507178)
- Discrete Mathematics and Applications by Kenneth Rosen (7th Edition, 2012), McGraw-Hill Education (ISBN-13: 978-0073383095)

# Past Offerings

- Offered in Jan-May, 2023 by Jasine Babu
- Offered in Jan-May, 2022 by Satyadev Nandakumar
- Offered in Jan-May, 2021 by Deepak, Krithika
- Offered in Jan-May, 2020 by Jasine
- Offered in Jan-May, 2019 by Deepak

# Course Metadata

Item | Details |
---|---|

Course Title | Discrete Mathematics for Computer Science |

Course Code | CS2020 |

Course Credits | 3-0-0-3 |

Course Category | PMT |

Proposing Faculty | Deepak Rajendraprasad |

Approved on | Senate 6 of IIT Palakkad |

Course prerequisites | CS2010 Logic for Computing |

Course status | old |