Course Code: CS201
Course Name: Discrete Mathematics
Prerequisites: NIL
Syllabus: Set theory - sets, relations, partially ordered sets, functions, countability. Logic: formulae, interpretations, methods of proof, soundness and completeness in propositional and predicate logic. Combinatorics: permutations, combinations, partitions, recurrences, generating functions. Catalan, Fibonacci, harmonic and Stirling numbers. Graph Theory: paths, connectivity, subgraphs, isomorphism, trees, complete graphs, bipartite graphs, matchings, colourability, planarity, digraphs. Lattices and Boolean algebras.
Texts: 1. K. H. Rosen, Discrete Mathematics & its Applications, 6th Ed., Tata McGraw-Hill, 2007.
2. E. Lehman, F. T. Leighton, A. R. Meyer, Mathematics for Computer Science, Available under the Creative Commons Attribution-ShareAlike 3.0 license, https://courses.csail.mit.edu/6.042/spring17/mcs.pdf.
References: 1. R. C. Penner, Discrete Mathematics: Proof Techniques and Mathematical Structures, World Scientific, 1999.
2. J. P. Tremblay and R. P. Manohar, Discrete Mathematics with Applications to Computer Science, Tata McGraw-Hill, 1997.
3. R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, 2nd Ed., Addison-Wesley, 1994.
4. M. Bona, A Walk Through Combinatorics An Introduction to Enumeration and Graph Theory, 2nd Edition, World Scientific, 2006.
5. M. Aigner, G. M. Ziegler Proofs from the Book, Springer, 2000.
6. R. J. Wilson, Introduction to Graph Theory, 4th Edition, Prentice Hall, 1996.