Basic counting principle: Pigeonhole principle, inclusion - exclusion principle, recurrence relations, generating functions. Fundamentals of logic, set theory, language, and finite state machines.

Undirected and direct graphs, modelling with graphs, trial and cycle- Eulerian trial and Hamilton cycle, connectivity and trees. Graph algorithms: BFS, DFS, shortest path, optimal spanning trees, matching, job assignment problem, optimal transportation through flows in networks

Same as Reference

1. Liu, C. L., Elements of Discrete Mathematics, 2nd Ed., Tata McGraw-Hill (2000).

2. Grivaldi, R. P. and Ramana, B. V., Discrete and Combinatorial mathematics, Pearson (2008).

3. Graham, R. L., Knuth, D. E., and Patashnik, O., Concrete Mathematics, 2nd Ed., Addison- Wesley (1994).

4. Rosen, K. H., Discrete Mathematics and its Applications, 6th Ed., Tata McGraw-Hill (2007).

Course Outcomes (COs):

CO1: Familiarize with counting principles

CO2: Learn concepts like, pegion hole principle, exclusion inclusion principle, recursive equations

CO3: Apply these concepts to specific problems

CO4: Familiarize with various of types graphical models, concepts of walk, trail, path, cycles. Then to learn, connected graph, tree, spanning tree, Eulerian trail, Hamiltonian path.

CO5: Learn various algorithms related to spanning tree, shortest path, Halls marriage theorem. Also, learn about their applications for optimization problems in real-life.