MCA 202: Discrete Mathematics
Syllabus
Overview: Counting, pigeonhole principle, generating functions, recurrence relations, linear
recurrence relations with constant coefficients, homogenous solutions, particular solutions,
total solutions, solution by the method of generating functions.
Growth of Functions: Asymptotic notations, monotonicity, comparison of standard functions
 floors and ceilings, polynomials, exponentials, logarithms and factorials, summations:
summation formulas and properties, bounding summations, approximation by integrals.
Graph Theory: Basic terminology, multigraphs and weighted graphs, paths and circuits,
searching techniques: BFS, DFS and their applications, shortest paths in weighted graphs,
Eulerian paths and circuits, Hamiltonian paths and circuits, Traveling Salesperson problem,
planar graphs, trees and rooted trees, prefix codes, minimal spanning trees, cut sets, directed
graphs.
Mathematical Logic: Propositions, connectives, conditionals and biconditionals, well formed
formulas, tautologies, equivalence of formulas, duality law, normal forms, inference theory for
propositional calculus; predicate calculus: predicates, free and bound variables, inference
theory of predicate calculus.
Introduction to algebraic structures groups, lattices and boolean algebra.
References
 C.L. Liu, Elements of Discrete Mathematics,
McGrawHill Pub. Co., 1977.
 D.E. Knuth, The Art of Computer Programming(3rd ed.), Vol. 1, Addison Wesley, 1997.
 R.L. Graham, D.E. Knuth, O. Patashnik, Concrete Mathematics(2nd ed.), Addison
Wesley, 1994.
Lecture Notes of 2012
