Tribhuvan University
Faculty of Management
Office of the Dean
Bachelor of Information Management (BIM)
Course Description
:This course covers different concepts of discrete structures including logic and proofs, number theory, induction and recursion, counting and advanced counting techniques, graphs, and trees.
Course Objective
:The main objective of this course is to provide students both theoretical and practical knowledge of different concepts of discrete structures.
Course Contents:
Lecture hours show the approximate classroom time allocated to each unit.
Unit 1.Logic and Proofs
8 hours
- Propositional Logic and Applications
- Propositional Equivalences
- Predicates and Quantifiers
- Nested Quantifiers
- Rules of Inference for Propositional Logic and Quantified Statements
- Proof Methods and Strategies
- Mistakes in Proofs
Unit 2.Number Theory
7 hours
- Divisibility and Modular Arithmetic
- Integer Representations and Algorithms
- Primes
- Greatest Common Divisors
- Least Common Multiplier
- Euclidian and Extended Euclidian Algorithm
- Solving Congruences
- Chinese Remainder Theorem
- Computer Arithmetic with Lage Integers
- Pseudorandom Numbers
Unit 3.Induction and Recursion
5 hours
- Mathematical Induction and Examples
- Strong Induction and Well Ordering
- Recursive Definitions and Structural Induction
- Recursively Defined Functions and Sets
- Recursive Algorithms
- Program Correctness
- Recursion and Iteration
Unit 4.Counting and Advanced Counting
12 hours
- Basics of Counting (Sum Rule, Product Rule, Subtraction Rule , Division Rule )
- Pigeonhole Principle
- Generalized Pigeonhole Principle
- Permutations and Combinations
- Binomial Theorem
- Pascal’s Identity and Triangle
- Permutations and Combinations with Repetition
- Generating Permutations and Combinations
- Recurrence Relations and Applications
- Solving Linear Recurrence Relations (Homogenous and Non -homogenous
- Theorems without Proof)
- Principle of Inclusion-Exclusion
Unit 5.Graphs
10 hours
- Graph and Graph Models
- Graph Terminology and Special Types of Graphs
- Representing Graphs and Graph Isomorphism
- Connectivity (Paths and Circuits, Connectedness in Undirected and Directed Graphs)
- Euler and Hamilton Paths and Circuits
- Shortest-Path Problem (Dijkstra’s Algorithm, Travelling Salesman Problem)
- Planar Graphs and Applications
- Graph Coloring and Applications
Unit 6.Trees
6 hours
- Trees (Introduction, Rooted Trees, Trees as Models, Properties of Trees)
- Applications of Trees (Binary Search Trees, Decision Trees, Prefix Codes, Game Trees)
- Tree Traversals (Introduction and Traversal Algorithms)
- Depth-First and Breadth -First Search
- Spanning Trees
- Minimum Spanning Trees (Introduction, Prim’s Algorithm, Kruskal’s Algorithm) Laboratory Works: Students should implement all the concepts and algorithms studied in each unit of the course using any suitable programming language.
Textbooks:
- Discrete Mathematics and Its Applications, Eighth Edition, Kenneth H. Rosen, McGraw- Hill Education, 2019 Reference Books:
- Discrete Mathematical Structures, Sixth Edition, Bernard Kolman, Robert Busby and Sharon C. Ross, Pearson Publications, 2015.
- Discrete Mathematics for Computer Scientists and Mathematicians, Second Edition, Joe L Mott, Abraham Kandel and Theodore P Baker, Printice Hall of India, 2008.
- Discrete Mathematics for Computer Scientists, First Edition, Ken Bogart, Scot Drysdale, and Cliff Stein, Addison-Wesley, 2010