# DISCRETE STRUCTURES

 Course Code : PCS3I001 Author : uLektz University : Biju Patnaik University of Technology (BPUT) Regulation : 2016 Categories : Computer Science Format : ePUB3 (DRM Protected) Type : eBook

FREE

Description :DISCRETE STRUCTURES of PCS3I001 covers the latest syllabus prescribed by Biju Patnaik University of Technology (BPUT) for regulation 2016. Author: uLektz, Published by uLektz Learning Solutions Private Limited.

Note : No printed book. Only ebook. Access eBook using uLektz apps for Android, iOS and Windows Desktop PC.

##### Topics
###### UNIT - I SETS AND PROPOSITIONS, RELATIONS AND FUNCTIONS

1.1 Sets and Propositions: Principle of Inclusion and Exclusion, Mathematical induction, oppositions

1.2 Logical Connectives, Conditionals and Biconditionals, Logical Equivalences, Predicate Calculus, Quantifiers, Theory of inference, Methods of proof

1.3 Relations and Functions: properties of binary relations, Closure of relations

1.4 Warshall’s algorithm, Equivalence relations, Partial ordering relations and lattices, Chains and antichains, Functions

1.5 Composition of Functions, Invertible Functions, Recursive Functions, Pigeonhole principle

###### UNIT - II NUMERIC FUNCTIONS AND GENERATING FUNCTIONS, RECURRENCE RELATIONS AND RECURSIVE ALGORITHMS

2.1 Numeric Functions and Generating Functions: Discrete Numeric functions, Generating Functions

2.2 Recurrence Relations and Recursive Algorithms: Recurrence relations, Linear recurrence relations with constant coefficients, Solution of recurrence relations by the method of generating functions

2.3 Divide and conquer algorithms

###### UNIT - III GROUPS AND RINGS, BOOLEAN ALGEBRAS

3.1 Groups and Rings: Groups and subgroups, Cosets and Lagrange’s theorem

3.2 Codes and Group codes, Error detection and correction using Group codes

3.3 Isomorphism, Homomorphism and normal subgroups, Rings, Integral domains and Fields

3.4 Boolean Algebras: Lattices and algebraic systems, Principle of duality, Distributive and complemented lattices

3.5 Boolean functions: Boolean expressions, Simplification of logic expressions using Karnaugh Map, Design and Implementation of Digital Networks, Switching Circuits

###### UNIT - IV GRAPHS AND TREES

4.1 Graphs and Trees: Basic terminology, Digraphs and relations, representation of Graphs, operations on graphs

4.2 Paths and circuits, graph traversals, shortest path in weighted graphs, Eulerian paths and circuits

4.3 Hamiltonian paths and circuits, Traveling sales person’s problem

4.4 Planar graphs, Graph Coloring

4.5 Trees, Rooted trees, Binary search trees, Spanning trees, Minimum spanning trees, Kruskal’s Algorithm, Prim’s Algorithm