Instructors: Prof. Rana Barua and Dr. Shion Samaddar Chaudhury
Course Objective:
This is one of the foundational classes in the CS curriculum. It is a direct or indirect prerequisite to courses in Algorithms, Theory of Computation, Compilers, Artificial Intelligence, Data Security, Computer Graphics, Operating Systems, Cryptology, etc. The class has two major themes.
(a) Mathematical Reasoning: You will learn logic and proof techniques so you can show that a mathematical statement is true.
(b) Discrete Structures: You will learn important mathematical structures – used to represent objects and their relationships – in Computer Science. These discrete structures include sets, functions and relations, graphs, etc.
Both skills are important for designing algorithms and doing research in Cryptology.
Syllabus:
- The Foundations – Logic and Proofs: Propositional logic, Predicates and Quantifiers, Rules of Inference, Proof methods and strategies.
- Combinatorics: Sets, Functions, Relations, Equivalence relation, Partitions, PO Set, Lattice; Basics of counting, Pigeonhole principle, Permutation, Combination, Binomial and Multinomial Theorem, Generating permutation and combination, Inclusion-Exclusion and its application; Recurrence relation, Solving linear recurrence relation, Generating functions; Basic Number theory, Divisibility, Congruence, GCD, Euclidean Algorithm, Extended Euclidean Algorithm, Chinese Remainder theorem, RSA.
- Graph Theory: Graphs and di-graphs, Basic terminologies (clique, independent set, vertex cover, degree, regular, complement), Graph models, Isomorphism, Representation of graphs, Connectivity, Eulerian paths and circuits, Hamiltonian paths and circuits, Knight’s Tour; Graph traversal, Topological Sorting, Shortest path algorithms, Tree, Counting trees (Prufer Code), Minimal Spanning Trees, Planar graphs, Euler’s Formula, Kuratowski’s Theorem, Five-color Theorem, Bi-partite Matching, Halls Theorem, Stable Matching, Matching in any graph, Tutte’s Theorem, Coloring of graphs, Chromatic Number, Brooks Theorem, Vizing’s Theorem, Art Gallery Problem.
References:
[1] K. H. Rosen: Discrete Mathematics and Its Applications (8th Edition), McGraw Hill, 2019.
[2] N. L. Biggs: Discrete Mathematics, Clarendon Press, 1985.
[3] C. L. Liu: Elements of Discrete Mathematics, McGraw Hills, 1985.
[4] J. A. Bondy, U. S. R. Murty: Graph Theory, Graduate texts in mathematics 244, Springer, 2008.
[5] D. West: Introduction to Graph Theory, Prentice Hall, 2000.
[6] R. Diestel: Graph Theory, Graduate texts in mathematics 173, Springer-Verlag Berlin Heidelberg, 2017.
[7] B. Bollobas: Modern Graph Theory, Graduate texts in mathematics, Springer, 2002.