Discrete Structures

Course Title: Discrete Structures

Course No: CSIT.212

Nature of the Course: Theory + Lab

Semester: 3

Full Marks: 60 + 20 + 20

Pass Marks: 24 + 10 + 10

Credit Hours: 3

Course Description

After completing this course, the target student will gain knowledge in discrete mathematics. It helps the target student in gaining fundamental and conceptual clarity in the area of set theory, logic, reasoning, counting, probability, and graph theory.

Course Objectives

Describe basic discrete structures such as sets, functions and relations. Express and proof verbal arguments using propositional and predicate logic. Select the best proof strategy for the given problem. Demonstrate counting principles and apply them to solve problems. Model problems using graph theory and identify their solutions.

Course Contents

1. Functions Sets and Relations

4 hrs

1.1. Sets

Venn Diagrams

Complements

Cartesian Products

Power Sets

Cardinality and Countability

Computer Representation of Sets

1.2. Functions

Surjections

Injections

Bijections

Inverses

Composition

Growth of Functions

1.3. Relations

Reflexivity

Symmetry

Transitivity

Asymmetry

Equivalence Relations

Representing Relations using Matrices and Diagraphs

Equivalence Classes

Partitions

Partial and Total Ordering

2. Basics of Logic

10 hrs

2.1. Propositional logic, Logical connectives, Truth tables, Normal forms (conjunctive and disjunctive), Validity

2.2. Conditional statements, inverse, converse, and contrapositive, Translating English sentences, logical equivalences, inference rules, proof of equivalence

2.3. Predicate logic, Universal and existential quantification, Nested quantifiers, Logical equivalences, Translating english sentences, proof of logical equivalences, Limitations of predicate logic

3. Proof Techniques

6 hrs

3.1. Proof Strategies

Direct Proofs

Proof By Counterexample

Proof By Contradiction

3.2. Mathematical Induction, Strong Induction And Well Ordering

3.3. Recursive Mathematical Definitions, Structural Induction, Recursive Algorithms

3.4. Program Correctness

4. Basics Of Counting

8 hrs

4.1. Sum And Product Rule, Inclusion-Exclusion Principle, Pigeon-hole Principle, and Applications of Pigeon-hole Principle.

4.2. Permutations and Combinations, Binomial Coefficients, Pascal's Identity and Triangle, Generalized Permutation and Combinations, Generating Permutation and Combinations.

4.3. Recurrence Relations, Modeling with Recurrence Relations, Solving Linear Recurrence Relations (Proof of theorems is not Required)

5. Discrete Probability

6 hrs

5.1. Finite probability space, probability measure, events, overview of non-discrete probability theory

5.2. Conditional probability, independence, Bayes' theorem, Applications of Bays Theorem

5.3. Integer random variables, expectation, variance, and Chebyshev bounds, Law of large numbers

6. Graphs and Trees

6 hrs

6.1. Types of Graphs, Basic Terminologies, Special Types of Graphs and their Applications, Graph Representation, Graph Isomorphism.

6.2. Connectivity, Paths, Connectedness, Euler and Hamiltonian Paths and circuits, Travelling Salesman Problem, Planner Graphs, Shortest path problems, Graph Coloring and Applications

6.3. Trees, Properties and Applications of Trees, Decision Trees, infix/prefix/postfix Notations, Tree Traversal, Spanning Trees, Minimum Spanning Trees.

7. Network Flows

5 hrs

7.1. Concept of network flows, proof of Maxflow and Mincut theorem, verification of the algorithms by examples.

Laboratory Works

After completing the end semester theoretical examination, viva examination will be held. External examiner will evaluate report/presentation & take viva exam. Students should make a small report by relating any of the studied topics in the subject to some application areas/examples.

1.Report and Presentation

Text Books

1.Kenneth H. Rosen, Discrete Mathematics & it's Applications to Computer Science, WCB/McGraw Hill.
2.Joe L. Mott, Abrahan Kandel and Theodore P. Baker, Discrete Mathematics for Computer Scientists and Mathematicians, Prentice-Hall of India.

Reference Books

1.G. Chartand, B.R. Oller Mann, Applied and Algorithmic Graph Theory, McGraw Hill.
2.G. Birkhoff, T.C. Bartee, Modern Applied Algebra, CBS Publishers.

Notes:

This syllabus follows the official CSIT curriculum of Far Western University. In case of any doubt or revision, the university's published syllabus shall be considered authoritative. https://cdc.fwu.edu.np/faculties.html

Discrete Structure

Discrete Structure

Select University

Select Program

TabFlux . Discrete Structures . FWU . BSc. CSIT