Course Structure
- The course title is Discrete Mathematics, with a total of 100 marks.
- Assessment includes two minor tests (20 marks each) and one major test (60 marks).
- Each minor test lasts 1.5 hours, while the major test lasts 3 hours.
- The course is scheduled for examinations in December 2025, 2026, and 2027.
Course Objectives & Learning Outcomes
- Understand key concepts of discrete mathematics, including counting, relations, graphs, and logic.
- Develop problem-solving skills through various mathematical theories.
- Apply discrete mathematics in computer science contexts, such as algorithms and data structures.
- Analyze and construct logical expressions and mathematical models relevant to computer science.
Unit I: Overview of Counting
- Covers basic counting principles, pigeon-hole principle, and generating functions.
- Discusses recurrence relations, including linear and homogenous types.
- Explores applications like Fibonacci and Tower of Hanoi problems.
- Total duration: 10 hours.
Unit II: Relations and Functions
- Examines domains, ranges, and types of relations and functions.
- Discusses closure of relations and their applications in computer science.
- Introduces functions like floor, ceil, and hash functions.
- Total duration: 10 hours.
Unit III: Theory of Graphs
- Defines graphs, multigraphs, directed and weighted graphs.
- Discusses graph operations, spanning trees, and traversal algorithms (BFS, DFS).
- Covers shortest paths in weighted graphs and planarity detection.
- Total duration: 10 hours.
Unit IV: Trees and Graph Coloring
- Explores properties of trees, including traversals and minimal spanning trees.
- Discusses graph coloring, chromatic numbers, and coloring algorithms.
- Total duration: 10 hours.
Unit V: Mathematical Logic
- Introduces propositions, connectives, and well-formed formulas.
- Covers inference theory for propositional and predicate calculus.
- Discusses algebraic structures, particularly groups.
- Total duration: 10 hours.
Suggested Readings/References:
1. Elements of Discrete Mathematics C. L. Liu McGraw-Hill Education
2. Discrete Mathematics and Its Applications K. H. Rosen McGraw-Hill Education
3. Concrete Mathematics R. L. Graham, D. E. Knuth, O. Patashnik Addison Wesley
4. Discrete Mathematical Structures with Applications to Computer Science J. P. Tremblay, R. P.
Manohar McGraw-Hill
5. Graph Theory with Applications to Engineering and Computer Science N. Deo Prentice-Hall Inc.
6. Applied Discrete Structures of Computer Science A. Doerr, K. Levasseur Galgotia Publications Pvt.
Ltd.
- Course creator: Amit Sharma