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 |