Course Code: CS-204
Credit Hours: 3 (3+0)
Prerequisites: None
Course Learning Outcomes (CLOs)
By the end of the course, students will be able to:
| CLO | Domain | BT Level |
|---|---|---|
| Understand the fundamental concepts of discrete mathematics, including logic, sets, and functions. | C | 2 |
| Apply combinatorial techniques and discrete probability in problem-solving. | C | 3 |
| Analyze graphs, trees, and their applications in computer science. | C | 4 |
| Develop proofs using direct, indirect, and mathematical induction methods. | C | 3 |
(BT = Bloom’s Taxonomy; C = Cognitive Domain)
Course Contents
Week 1: Introduction to Discrete Structures
- Importance of discrete structures in computer science
- Applications in algorithms, databases, and networking
- Class Activity: Discuss real-world applications of discrete mathematics
Week 2: Logic and Propositional Calculus
- Propositions, logical operators, and truth tables
- Logical equivalence, implications, and predicates
- Assignment: Create truth tables for given logical expressions
Week 3: Methods of Proof
- Direct proof, indirect proof, and proof by contradiction
- Mathematical induction and strong induction
- Task: Prove basic theorems using different proof methods
Week 4: Sets and Set Operations
- Definitions and representations of sets
- Venn diagrams, Cartesian products, and power sets
- Operations: Union, intersection, difference, and complement
- Reading Material: Chapter 2 from “Discrete Mathematics and Its Applications” by Kenneth H. Rosen
- Assignment: Solve problems on set theory and Venn diagrams
Week 5: Relations and Their Properties
- Definition and types of relations: Reflexive, symmetric, transitive, and equivalence relations
- Representing relations using matrices and digraphs
- Class Activity: Identify relation types from examples
Week 6: Functions and Their Types
- Definitions and types: Injective, surjective, bijective functions
- Composition of functions and inverse functions
- Assignment: Solve problems involving types of functions
Week 7: Combinatorics – Basics
- Basic counting principles: Addition and multiplication rules
- Permutations and combinations
- Task: Solve combinatorial problems
Week 8: Combinatorial Analysis
- Pigeonhole principle and inclusion-exclusion principle
- Advanced counting techniques
- Reading Material: Chapter 6 from the textbook
- Assignment: Apply combinatorial principles to solve problems
Week 9: Midterm Exam
- Coverage: Weeks 1–8
- Format: Short answer questions and problem-solving
Week 10: Discrete Probability
- Basic concepts of probability theory
- Conditional probability and independence
- Bayes’ theorem and its applications
- Assignment: Solve probability problems based on real-world scenarios
Week 11: Graph Theory – Fundamentals
- Graphs: Definitions, types, and representations (adjacency matrix and list)
- Graph terminology: Paths, cycles, and connectivity
- Task: Draw and analyze graphs for practical scenarios
Week 12: Advanced Graph Theory
- Trees, spanning trees, and minimum spanning trees
- Graph traversal techniques: BFS and DFS
- Assignment: Implement BFS and DFS in Python
Week 13: Boolean Algebra and Logic Gates
- Boolean functions and expressions
- Simplification using Boolean identities and Karnaugh maps
- Applications in digital circuits
- Task: Simplify Boolean expressions and design simple circuits
Week 14: Recurrence Relations and Generating Functions
- Solving linear recurrence relations
- Homogeneous and non-homogeneous recurrence relations
- Reading Material: Chapter 8 from the textbook
- Assignment: Solve recurrence relation problems
Week 15: Algebraic Structures
- Groups, rings, and fields: Definitions and examples
- Applications of algebraic structures in cryptography
- Task: Solve problems involving groups and rings
Week 16: Course Revision and Final Exam Preparation
- Review key concepts and practice problems
- Mock test and Q&A session
Teaching Methodology
- Lectures and interactive discussions
- Problem-solving sessions and tutorials
- Written assignments and quizzes
- Peer review and feedback
Assessment Criteria
| Component | Weightage (%) |
|---|---|
| Assignments | 20% |
| Midterm Exam | 20% |
| Quizzes | 10% |
| Final Exam | 30% |
| Class Participation | 10% |
| Project/Case Study | 10% |
Textbook
- “Discrete Mathematics and Its Applications” by Kenneth H. Rosen, 7th Edition
Reference Materials
- “Discrete Mathematical Structures” by Kolman, Busby, and Ross
- “Concrete Mathematics” by Ronald Graham, Donald Knuth, and Oren Patashnik