Discrete Structure

Course Title: Discrete Structure

Course No: IT 235

Nature of the Course: Theory + Lab

Semester: 2

Full Marks: 60 + 40

Pass Marks: 30 + 20

Credit Hours: 3

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 Objectives

The main objective of this course is to provide students both theoretical and practical knowledge of different concepts of discrete structures.

Course Contents

1. Logic and Proofs

8 hrs

1.1. Propositional Logic and Applications

1.2. Propositional Equivalences

1.3. Predicates and Quantifiers

1.4. Nested Quantifiers

1.5. Rules of Inference for Propositional Logic and Quantified Statements

1.6. Proof Methods and Strategies

1.7. Mistakes in Proofs

2. Number Theory

7 hrs

2.1. Divisibility and Modular Arithmetic

2.2. Integer Representations and Algorithms

2.3. Primes

2.4. Greatest Common Divisors

2.5. Least Common Multiplier

2.6. Euclidian and Extended Euclidian Algorithm

2.7. Solving Congruences

2.8. Chinese Remainder Theorem

2.9. Computer Arithmetic with Lage Integers

2.10. Pseudorandom Numbers

3. Induction and Recursion

5 hrs

3.1. Mathematical Induction and Examples

3.2. Strong Induction and Well Ordering

3.3. Recursive Definitions and Structural Induction

3.4. Recursively Defined Functions and Sets

3.5. Recursive Algorithms

3.6. Program Correctness

3.7. Recursion and Iteration

4. Counting and Advanced Counting

12 hrs

4.1. Basics of Counting

Sum Rule

Product Rule

Subtraction Rule

Division Rule

4.2. Pigeonhole Principle

4.3. Generalized Pigeonhole Principle

4.4. Permutations and Combinations

4.5. Binomial Theorem

4.6. Pascal's Identity and Triangle

4.7. Permutations and Combinations with Repetition

4.8. Generating Permutations and Combinations

4.9. Recurrence Relations and Applications

4.10. Solving Linear Recurrence Relations

Homogenous

Non-homogenous

Theorems without Proof

4.11. Principle of Inclusion-Exclusion

5. Graphs

10 hrs

5.1. Graph and Graph Models

5.2. Graph Terminology and Special Types of Graphs

5.3. Representing Graphs and Graph Isomorphism

5.4. Connectivity

Paths and Circuits

Connectedness in Undirected and Directed Graphs

5.5. Euler and Hamilton Paths and Circuits

5.6. Shortest-Path Problem

Dijkstra's Algorithm

Travelling Salesman Problem

5.7. Planar Graphs and Applications

5.8. Graph Coloring and Applications

6. Trees

6 hrs

6.1. Trees

Introduction

Rooted Trees

Trees as Models

Properties of Trees

6.2. Applications of Trees

Binary Search Trees

Decision Trees

Prefix Codes

Game Trees

6.3. Tree Traversals

Introduction

Traversal Algorithms

6.4. Depth-First and Breadth-First Search

6.5. Spanning Trees

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

1.Implementation of course concepts and algorithms

Text Books

1.Discrete Mathematics and Its Applications, Eighth Edition, Kenneth H. Rosen, McGraw-Hill Education, 2019

Reference Books

1.Discrete Mathematical Structures, Sixth Edition, Bernard Kolman, Robert Busby and Sharon C. Ross, Pearson Publications, 2015.
2.Discrete Mathematics for Computer Scientists and Mathematicians, Second Edition, Joe L Mott, Abraham Kandel and Theodore P Baker, Printice Hall of India, 2008.
3.Discrete Mathematics for Computer Scientists, First Edition, Ken Bogart, Scot Drysdale, and Cliff Stein, Addison-Wesley, 2010

Notes:

This syllabus follows the official BIM curriculum of Tribhuvan University. In case of any doubt or revision, the university’s published syllabus shall be considered authoritative.https://www.fomecd.edu.np/syllabuses

Discrete Structure

Discrete Structure

Select University

Select Program

TabFlux . Discrete Structure . TU . BIM