X hits on this document

114 views

0 shares

0 downloads

0 comments

1 / 32

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

Document info
Document views114
Page views119
Page last viewedFri Dec 09 01:06:38 UTC 2016
Pages32
Paragraphs1002
Words9463

Comments