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 (3 lectures). Counting functions, subsets and permutations. Estimation of factorials and binomial coefficients. Lower bound for sorting algorithms.

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

Graphs (9 lectures). 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.

Bipartite graphs (3 lectures). Characterization Of Bipartite Graphs. Matchings,Hall’s Marriage Theorem, Kőnig’s theorem. Edge-colouring of bipartite graphs.

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

Orderings (6 lectures). Partial orders and Hasse diagram. Lattices. Linear extension, chains and antichains. Scheduling. Mirsky’s theorem and Erdős–Szekeres theorem.

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

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

Textbook

  1. Invitation to Discrete Mathematics by Jiří Matoušek and Jaroslav Nešetřil (2nd Edition) Oxford University Press (ISBN-13:978-0198570424)

Reference

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

Metadata

Proposing Faculty : Deepak Rajendraprasad Stream : Computer Science and Engineering Programme : B.Tech Proposing date: Approved date: Proposal type: Offerings: