Discrete Mathematics

UNIT 1: Propositional Logic & Proof Strategies (15 Hrs)

• Propositional Logic
  • Applications of Propositional Logic
  • Propositional Equivalences
  • Predicates and Quantifiers
  • Nested Quantifiers
  • Rules of Inference
• Proof Strategies
  • Introduction to Proofs
  • Proof Methods and Strategy

UNIT 2: Number Theory & Boolean Functions (15 Hrs)

• Number Theory Basics
  • Divisibility and Modular Arithmetic
  • Primes and Greatest Common Divisor (GCD)
  • Least Common Multiple (LCM)
• Boolean Functions
  • Representing Boolean Functions
  • Logic Gates
  • Minimization of Circuits

UNIT 3: Graph Theory Fundamentals (15 Hrs)

• Graphs and Graph Models
• Terminology & Special Types of Graphs
• Representation of Graphs
• Graph Isomorphism
• Connectivity
• Euler and Hamiltonian Paths

UNIT 4: Trees & Advanced Graph Concepts (15 Hrs)

• Introduction to Trees
• Tree Traversal
• Spanning Trees
• Minimum Spanning Trees
• Planar Graphs
• Graph Colouring

Practical/Lab Work (2 Credits, 60 Hours)

Logic and Proofs

1. Truth Table Generator: Implement a program to generate truth tables for given propositional formulas
2. Propositional Logic Solver: Implement a SAT solver for propositional logic formulas

Number Theory

3. Prime Number Checker: Write a program to determine if a given number is prime using different algorithms (e.g., brute force, sieve of Eratosthenes)
4. GCD and LCM Calculator: Implement functions to calculate the greatest common divisor (GCD) and least common multiple (LCM) of two numbers
5. Modular Arithmetic Calculator: Create a program to perform arithmetic operations in modular arithmetic
6. Number Theory Problems: Solve various number theory problems, such as finding prime factorization, modular exponentiation, and solving linear congruences

Boolean Functions

7. Boolean Function Evaluator: Develop a program to evaluate Boolean functions given input values
8. Logic Gate Simulator: Build a simulator for basic logic gates (AND, OR, NOT, XOR)
9. Circuit Minimizer: Implement a simple circuit minimization algorithm (e.g., Karnaugh maps)
10. Boolean Algebra Simplification: Implement algebraic simplification techniques for Boolean expressions

Graph Theory

11. Graph Representation: Implement both adjacency matrix and adjacency list representations of graphs
12. Find the degree of a vertex in a graph
13. Find a path between two vertices in a graph
14. Graph Traversal: Implement depth-first search (DFS) and breadth-first search (BFS) algorithms
15. Connectivity Checker: Determine if a graph is connected or disconnected
16. Shortest Path Finder: Implement Dijkstra’s algorithm to find the shortest path between two nodes
17. Eulerian and Hamiltonian Path Finder: Check if a given graph has an Eulerian or Hamiltonian path
18. Graph Isomorphism Checker: Develop a program to check if two graphs are isomorphic

Trees

19. Tree Traversal: Implement pre-order, in-order, and post-order traversals for binary trees
20. Traverse a binary tree using pre-order, in-order, or post-order traversal
21. Minimum Spanning Tree: Implement Kruskal’s or Prim’s algorithm to find a minimum spanning tree

Advanced Graph Concepts

22. Planarity Checker: Determine if a given graph is planar
23. Graph Coloring: Implement a greedy algorithm for graph coloring

RECOMMENDED TEXTBOOKS

1. Rosen, K. H. (2023). Discrete mathematics and its applications (9th ed., ISBN: 978-1260424718). New York, NY: McGraw-Hill.
2. Data Structures in C, Yashwant Kanetkar