210241: DISCRETE STRUCTURES

Teaching SchemeExamination Scheme Lectures: 4 Hrs./week Theory: 100 Marks

Prerequisite: Knowledge of Elementary Mathematics

Learning Objectives:

1.

To learn formal logic, proofs, sets, relations and functions

2.

To use formal logic proofs and logical reasoning to solve problems

3.

To relate the ideas of mathematical induction to recursion and recursively defined structures

4.

To learn graphs, trees and related algorithms

5.

To apply these concepts to various areas of computer science

Unit I

Logic and Proofs

Propositions, Conditional Propositions, Logical Connectivity, Prepositional calculus, Universal and Existential Quantifiers, Proofs, Proof Techniques, Mathematical Induction

Set Theory - Set, Combination of sets, Finite and Infinite sets, Un-countably infinite sets, Principle of inclusion and exclusion (8)

# Unit II

Combinatorics and Discrete Probability

Permutations and Combinations: rule of sum and product, Permutations, Combinations, Algorithms for generation of Permutations and Combinations.

Discrete Probability, Conditional Probability, Information and Mutual Information, Binomial Coefficients and Combinatorial Identities. (8)

## Unit III

Relations

Definitions, Properties of Binary Relations, Equivalence Relations and partitions, Partial ordering relations and lattices, Chains and Anti chains.

## Functions

Definitions, domain, Range, One-to-One and OnTo, Inverse and Composition, Pigeonhole Principle, Discrete Numeric functions and Generating functions, Job scheduling Problem.

Recurrence Relations

Recurrence Relation, Linear Recurrence Relations With constant Coefficients, Homogeneous Solutions, Total solutions, solutions by the method of generating functions (10)

### Unit IV

## Graphs

Basic terminology, multi graphs and weighted graphs, paths and circuits, shortest path in weighted graph, Hamiltonian and Eulerian paths and circuits, factors of a graph, planer graph and Traveling salesman problem. (8)

### Unit V

Trees

Trees, rooted trees, path length in rooted trees, prefix codes, binary search trees, spanning trees and cut set, minimal spanning trees, Kruskal’s and prime’s