Discrete Mathematics

Course Objective:

The primary objective of the course is that students should learn a particular set of mathematical facts and how to apply them. In particular, this course should be able to teach the students how to think logically and mathematically. The students will be able to understand mathematical reasoning in order to read, comprehend, and construct mathematical arguments which serves as the foundation for the subsequent discussions of methods of proof. They should be able to perform combinatorial analysis to solve counting problems and analyze algorithms, not on applying formulae. The students would be able to work with discrete structures, such as sets, permutations, relations, graphs, which are the abstract mathematical structures used to represent discrete objects and relationships between these objects. They will also be able to perform the mathematical portions of various algorithms, which include the specification of the algorithm, the verification that it works properly, and the analysis of the computer memory and time required to perform it. Discrete mathematics has many applications to computer science and data networking in this text, as well as applications to such diverse areas as chemistry, biology, linguistics, geography, business, and the Internet. Students of this course will learn to solve such applications by modeling them with discrete mathematics.

Detailed Syllabus:

1. The Foundations – Logic and Proofs: Propositional logic, Predicates and Quantifiers, Rules of Inference, Proof methods and strategies.

2. Combinatorics: Sets, Functions, Relations, Equivalence relation, Partitions, PO Set, Lattice; Infinite Sets, Basics of counting, Pigeon-hole principle, Permutation, Combination, Binomial and Multinomial Theorem, Generating permutation and combination, Inclusion-Exclusion and its application; Recurrence relation, Solving linear recurrence relation, Generating functions.

3. 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.

Classes:

Lecture 1 (Some Motivating Puzzles)
Lecture 2 (Propositional Logic, Interesting Applications)
Lecture 3 (Predicate, Quantifier, Rules of Inference)
Lecture 4 (Proof Methods and Proof Strategy, Common Mistakes in Proofs)
Lecture 5 (Sets, Relation, Equivalence Relation, POSET)
Lecture 6 (Function, Infinite Sets, Schroder-Bernstein Theorem)
Lecture 7 (Counting Rules, and their applications: Sum-Rule, Product Rule)
Lecture 8 (Counting Equivalent Problems, Principles of Inclusion-Exclusion, Pigeon-hole Principle)
Discussion on Assignment 1
Lecture 9 (Introduction to Graphs, Basic terminologies, Special types of graphs, Representation of graphs)
Lecture 10 (Connectivity – path, walk, trail, cycle, circuit, Bridge)
Lecture 11 (Euler Graph, Hamiltonian Graph, and their Properties, Knight’s tour)
Discussion on Assignment 2 and 3
Lecture 12 (Graph Isomorphism, Di-graph, Strongly and weakly connected components, De-Bruijn Graph)
Mid-Semestral Examination [Question][Solution Hint]
Lecture 13 (Tree, Characterization of Trees, Distance Metrics, Wiener Index, Spanning Tree and Enumeration, Cayley’s Formula)
Lecture 14 (Proof of Cayley’s Formula, Pruffer code, Spanning Trees in General Graphs: Contraction of edges, Kirchhoff’s Matrix-Tree Theorem)
Lecture 15 (Algorithms for finding Minimum Spanning Trees – Kruskal’s algorithm, Prim’s Algorithm)
Lecture 16 (Algorithm for finding single sourse shortest paths – Relaxing edges, Dijkstra’s Algorithm, Bellman Ford Algorithm)
Lecture 17 (Graph Traversal, DFS, BFS, Applications)
Lecture 18 (Recurrence Relations, Applications in counting problems: Tower of Hanoi, Merge Sort, Fibonacci Series)
Lecture 19 (Generating functions, Applications of Generating Functions in solving recurrences, enumeration problems, combinatorial equalities)
Lecture 20 (Catalan Number, Counting Problems on Balls & Bins – Number of ways to place M dist/indist balls in N dist/indist bins)
Lecture 21 (Planar Graph, Edge Subdivision, Minor, Kuratowski’s Theorem, Euler’s Formula, 6-Color Theorem)
Lecture 22 (5-Color Theorem, Brook’s Theorem)
Lecture 23 (Proof of Brook’s Theorem, Chromatic Number and Its Relation with Maximum Independent Set, Dual Graph, Map Coloring, Edge Coloring, Vizing’s Theorem, Konig’s Result)
Lecture 24 (The Art Gallery Problem and Its simple Variants, Proof of Kuratowski’s Theorem)
Lecture 25 (Graph Matching, Matching in Bi-Partite Graphs, Berge’s Theorem, Hall’s Theorem, Perfect Matching, Konig’s Theorem – Min-Max Result, Stable Matching, Gale-Shapley Algorithm)
Lecture 26 (Some Applications of Graphs: Instant Insanity, Oriented graphs and Tournaments, Ramsey Theory)
End-Semestral Examination [Question]

The board works are available here: [Class Notes].

Home Work / Assignments :

Model Questions for Examinations :