Cse2a.files.wordpress.com



Geethanjali College of Engineering and Technology

Cheeryal (V), Keesara (M), Ranga Reddy District – 501 301 (T.S)

MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

COURSE FILE

DEPARTMENT OF

COMPUTER SCIENCE & ENGINEERING

(2016-2017)

Faculty In charge

Dr. S.Nagenderkumar HOD-CSE

B.Mamatha

CH.Latha Dr. S.Nagenderkumar

Contents

|S.No |Topic |Page. No. |

|1 |Cover Page |3 |

|2 |Syllabus copy |4 |

|3 |Vision of the Department |5 |

|4 |Mission of the Department |5 |

|5 |PEOs and Pos |5 |

|6 |Course objectives and outcomes |7 |

|7 |Brief notes on the importance of the course and how it fits into the curriculum |7 |

|8 |Prerequisites if any |8 |

|9 |Instructional Learning Outcomes |8 |

|10 |Course mapping with POs |9 |

|11 |Class Time Table |10 |

|12 |Individual time Table |12 |

|13 |Lecture schedule with methodology being used/adopted |12 |

|14 |Detailed notes |17 |

|15 |Additional topics |30 |

|16 |University Question papers of previous years |30 |

|17 |Question Bank |36 |

|18 |Assignment Questions |40 |

|19 |Unit wise Quiz Questions and long answer questions |42 |

|20 |Tutorial problems |46 |

|21 |Known gaps ,if any and inclusion of the same in lecture schedule |47 |

|22 |Discussion topics , if any |47 |

|23 |References, Journals, websites and E-links if any |47 |

|24 |Quality Measurement Sheets |48 |

|A |Course End Survey | |

|B |Teaching Evaluation | |

|25 |Student List |48 |

|26 | Group-Wise students list for discussion topic |54 |

Course coordinator Program Coordinator HOD

1. COVER PAGE

|Geethanjali College of Engineering and Technology |

|DEPARTMENT OF COMPUTER SCIENCE ENGINEERING |

|(Name of the Subject/Lab Course):Mathematical Foundation of Computer Science |

|(JNTU CODE: 30504 ) Programme: UG/PG |

|Branch: CSE Version No: 3 |

|Year: II Document Number :GCET/CSE/ |

|Semester: I No. of Pages: 54 |

|Classification status (Unrestricted/Restricted ) : |

|Distribution List: |

|Prepared by : | Updated by : |

|1) Name & B.Mamatha & CH.Latha |1) Name : |

| |2) Sign : |

|2) Sign : |3) Design : |

|3) Design : Assistant Professor(B.Mamatha) |4) Date : |

|Assistant Professor( CH.Latha) | |

|4) Date : | |

|Verified by : *For Q.C only |

|1) Name : 1)Name : |

|2) Sign : 2) Sign : |

|3) Design : 3) Design : |

|4) Date : 4) Date : |

|Approved by (HOD) : |

|1) Name: |

|2) Sign : |

|3) Date : |

2. SYLLABUS

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE

UNIT-I

Mathematical Logic: Statements and notations, Connectives, Well formed formulas, Truth Tables, tautology, equivalence implication, Normal forms, Quantifiers, universal quantifiers. Predicates : Predicative logic, Free & Bound variables, Rules of inference, Consistency, proof of contradiction, Automatic Theorem Proving.

UNIT-II

Relations: Properties of Binary Relations, equivalence, transitive closure, compatibility and partial ordering relations, Lattices, Hasse diagram. Functions: Inverse Function Composition of functions, recursive Functions, Lattice and its Properties, Algebraic structures : Algebraic systems Examples and general properties, Semi groups and monads, groups sub groups’ homomorphism, Isomorphism.

UNIT-III

Elementary Combinatorics: Basis of counting, Combinations & Permutations, with repetitions, Constrained repetitions, Binomial Coefficients, Binomial Multinomial theorems, the principles of Inclusion – Exclusion. Pigeon hole principles and its application.

UNIT-IV

Recurrence Relation : Generating Functions, Function of Sequences Calculating Coefficient of generating function, Recurrence relations, Solving recurrence relation by substitution and Generating funds. Characteristics roots solution of In homogeneous Recurrence Relation.

UNIT-V

Graph Theory : Representation of Graph, DFS, BFS, Spanning Trees, planar Graphs. Graph Theory and Applications, Basic Concepts Isomorphism and Sub graphs, Multi graphs and Euler circuits, Hamiltonian graphs, Chromatic Numbers.

TEXT BOOKS :

1. Elements of DISCRETE MATHEMATICS- A computer Oriented Approach-

C L Liu, D P Mohapatra. Third Edition, Tata McGraw Hill.

2. Discrete Mathematics for Computer Scientists & Mathematicians, J.L. Mott, A. Kandel, T.P. Baker, PHI.

REFERENCE BOOKS :

1. Discrete Mathematics and its Applications, Kenneth H. Rosen, Fifth Edition.TMH.

2. Discrete Mathematical structures Theory and application-Malik & Sen, Cengage.

3. Discrete Mathematics with Applications, Thomas Koshy, Elsevier.

4. Logic and Discrete Mathematics, Grass Man & Trembley, Pearson Education.

3. VISION OF THE DEPARTMENT

To produce globally competent and socially responsible computer science engineers contributing to the advancement of engineering and technology which involves creativity and innovation by providing excellent learning environment with world class facilities.

4. MISSION OF THE DEPARTMENT

1. To be a center of excellence in instruction, innovation in research and scholarship, and service to the stake holders, the profession, and the public.

2. To prepare graduates to enter a rapidly changing field as a competent computer science engineer.

3. To prepare graduate capable in all phases of software development, possess a firm understanding of hardware technologies, have the strong mathematical background necessary for scientific computing, and be sufficiently well versed in general theory to allow growth within the discipline as it advances.

4. To prepare graduates to assume leadership roles by possessing good communication skills, the ability to work effectively as team members, and an appreciation for their social and ethical responsibility in a global setting

5. PEOS AND POS

PROGRAM EDUCATIONAL OBJECTIVES (PEOs) OF C.S.E. DEPARTMENT

PEO-I: To provide graduates with a good foundation in mathematics, sciences and engineering fundamentals required to solve engineering problems that will facilitate them to find employment in industry and / or to pursue postgraduate studies with an appreciation for lifelong learning.

PEO-II: To provide graduates with analytical and problem solving skills to design algorithms, other hardware / software systems, and inculcate professional ethics, inter-personal skills to work in a multi-cultural team.

PEO-III: To facilitate graduates get familiarized with state of the art software / hardware tools, imbibing creativity and Innovation that would enable them to develop cutting-edge technologies of multi-disciplinary nature for societal development.

PROGRAM OUTCOMES (CSE)

1. An ability to apply knowledge of mathematics, science and engineering to develop and analyze computing systems.

2. an ability to analyze a problem and identify and define the computing requirements appropriate for its solution under given constraints.

3. An ability to perform experiments to analyze and interpret data for different applications.

4. An ability to design, implement and evaluate computer-based systems, processes, components or programs to meet desired needs within realistic constraints of time and space.

5. An ability to use current techniques, skills and modern engineering tools necessary to practice as a CSE professional.

6. An ability to recognize the importance of professional, ethical, legal, security and social issues and addressing these issues as a professional.

7. An ability to analyze the local and global impact of systems /processes /applications /technologies on individuals, organizations, society and environment.

8. An ability to function in multidisciplinary teams.

9. An ability to communicate effectively with a range of audiences.

10. Demonstrate knowledge and understanding of the engineering, management and economic principles and apply them to manage projects as a member and leader in a team.

11. A recognition of the need for and an ability to engage in life-long learning and continuing professional development

12. Knowledge of contemporary issues.

13. An ability to apply design and development principles in producing software systems of varying complexity using various project management tools.

14. An ability to identify, formulate and solve innovative engineering problems.

COURSE OBJECTIVES AND OUTCOMES

Course Objectives

a) Introduce Mathematical Logic, especially First Order Logic

b) Develop an understanding of inferring a conclusion from the given premises applying rules of inference in statement calculus and predicate calculus.

c) Introduce proof techniques such as Mathematical Induction and Contradiction. These techniques will come in handy for courses such as Analysis of Algorithms and Automata Theory.

d) Develop an understanding of counting, functions and relations.

e) Be familiar with fundamental notions of statistics, such as sample space, mean and distributions.

f) Understand basic definitions and properties of graphs. To have the knowledge of applications of graphs in the field of computer science.

Course Outcomes

Upon successful completion of this course, students will be able to:

a) Distinguish between Statement Logic and Predicate Logic.

b) Check if a proposition is satisfiable.

c) Apply induction and other proof techniques towards solving recurrences and other problems in elementary algebra.

d) Illustrate by examples the basic terminology of functions, relations, and sets and demonstrate knowledge of their associated operations.

e) Demonstrate in practical applications the use of basic counting principles of permutations, combinations, inclusion/exclusion principle and the pigeonhole methodology.

f) Compute the probability of an event in a well-defined distribution.

g) Represent and Apply Graph theory in solving computer science problems.

6. BRIEF NOTES ON THE IMPORTANCE OF THE COURSE AND HOW IT FITS INTO THE CURRICULUM

Mathematical Foundations of Computer Science

The course exposes the students to fundamental knowledge in :Mathematical logic, tautology and normal forms, Predicate logic, rules of inference and validity of arguments, Elementary set theory, Venn diagrams, functions and their relations, Algebraic structure, binary operation, group theory and homomorphism, theory of permutations and combinations, binomial and multinomial theorems, Recurrence relations and methods of solving them, Graph theory, spanning tree, Eulerian and Hamiltonian circuits and isomorphism. The idea of a general purpose computer, the Turing Machine, was invented in the course of research in logic.

Logic is concerned with forms of reasoning. Since reasoning involves the student in most intellectual activities, logic is relevant to a broad range of pursuits. The study of logic is essential for students of computer science. In the process of reasoning, the student makes inferences. In an inference the student uses a collection of statements, the premises, in order to justify another statement, the conclusion.

The students can apply knowledge of mathematics, science and engineering to develop and analyze computing systems. They get an ability to identify, formulate and solve innovative engineering problems.

7. PREREQUISITES IF ANY

i) Mathematics-I studied in B.Tech I year

ii) Intermediate Mathematics

8. INSTRUCTIONAL LEARNING OUTCOMES

Upon completing this course, it is expected that a student will be able to do the following:

1. Fundamentals of Logic: Basic understanding of truth tables . Method of proving the validity of the logical formulas by using truth tables and laws of logic. Formulate and interpret statements presented in normal form and determine their validity by applying the rules and methods of propositional calculus.

2. Predicate Logic: Reformulate statements from common language to formal logic using the rules of propositional and predicate calculus, and assess the validity of arguments.

Formulate short proofs using the following methods: direct proof, indirect proof, proof by contradiction, and case analysis.

3. Functions: Apply the different properties of injections, surjections, bijections, compositions, and inverse functions, as well as the pigeon-hole principal.

4. Relations: Determine when a relation is reflexive, symmetric, antisymmetric, or transitive, apply the properties of equivalence relations and partial orderings, and explain the connection between equivalence relations and partitioning a set. Understand different methods of solving recurrence relation.

5. Algebraic Structures: understand the general properties of algebraic structures and their applications.

6. Combinatorics: Apply basic counting principles including the pigeonhole principle and rules for counting permutations and combinations.

7. Recurrence relation: Ability to write generating functions and solving using different techniques like substitution method, characteristics method. Students will be able to understand how to solve recurrence relations and their application in determining time complexities of various recursive algorithms.

8. Graph theory: Explain basic definitions and properties associated with simple planar graphs, including isomorphism, connectivity, and Euler's formula, and describe the difference between Eulerian and Hamiltonian graphs. Understand the problem of graph coloring which is applicable to various problems in real word.

9. COURSE MAPPING WITH PEOS AND POS

Mapping of Course with Programme Educational Objectives

|S.No |Course component |code |course |Semester |PEO 1 |PEO 2 |PEO 3 |

|1 |Mathematics | |MFCS |I |√ |√ | |

Mapping of Course outcomes with Programme outcomes:

*When the course outcome weightage is < 40%, it will be given as moderately correlated (1).

*When the course outcome weightage is >40%, it will be given as strongly correlated (2).

|POs |1 |2 |3 |4 |5 |

|Thursday |MFCS |EDC |DS | |CRT |

|Tuesday |BEE |B1: EE LAB/ B2: DS LAB | |DLD |FL |

|Wednesday |DLD |PS |EDC |MFCS | |

|Saturday |EDC |DLD |BEE |DS | |

| 1 | |Unit I : Mathematical Logic ; Predicates | |13-06-16 | |

| |1 |Statements and notations, Connectives, Well formed |BB |15-06-16 | |

| | |formulas | | | |

| |1 |Truth Tables, tautology |BB |17-06-16& | |

| | | | |18-06-16 | |

| |2 | Equivalence implication |BB |20-06-16& | |

| | | | |22-06-16 | |

| |2 |Normal forms. |BB |24-06-16 | |

| |1 |Quantifiers, universal quantifiers |BB |25-06-16 | |

| |1 |Tutorial Class |BB |27-06-16 | |

| |1 |Predicative logic |BB |29-06-16 | |

| |1 | Free & Bound variables |BB |01-07-16 & | |

| | | | |02-07-16 | |

| |2 | Rules of inference |BB |03-07-16 & | |

| | | | |04-07-16 | |

| |2 |Consistency, Proof of contradiction |BB |06-07-16 & | |

| | | | |08-07-16 | |

| |2 |Automatic Theorem Proving. |BB |11-07-16 | |

| |1 |Tutorial Class |BB | |17 |

|2 | |Unit II: Relations ; Algebraic structures |BB |13-07-16 & | |

| | | | |15-07-16 | |

| |2 |Properties of binary Relations, equivalence |BB |16-07-16& | |

| | | | |18-07-16 | |

| |2 |Transitive closure,Compatibility and partial ordering |BB |20-07-16 | |

| | |relations | | | |

| |1 |Lattices ,Hasse diagram |PPT |22-07-16 & | |

| | | | |23-07-16 | |

| |2 |Functions: Inverse Function Composition of functions , |BB |25-07-16 & | |

| | |recursive Functions | |27-07-16 | |

| |2 |Lattice and its Properties |PPT |01-08-16 | |

| |1 |Tutorial class |BB |03-08-16 & | |

| | | | |05-08-16 | |

| |2 |Algebraic systems Examples and general properties |BB |06-08-16 & | |

| | | | |15-08-16 | |

| |2 |Semi groups and monads |BB |17-08-16 | |

| |1 |groups sub groups |BB |19-08-16 | |

| |1 |Homomorphism |BB |19-08-16 | |

| |1 |Isomorphism, |BB |20-08-16 | |

| |1 |Tutorial class |BB | |18 |

|3 | |Unit III : Elementary Combinatorics |BB |22-08-16 | |

| |1 |Basis of counting |BB |24-08-16 & | |

| | | | |26-08-16 | |

| |2 |Combinations & Permutations with repetitions |BB |27-08-16 | |

| |1 |Constrained repetitions |BB |29-08-16 | |

| |2 |Binomial Coefficients |BB |31-08-16 | |

| |1 |Tutorial class |BB |01-09-16 & | |

| | | | |4-09-16 | |

| |2 |Binomial Multinomial theorems |BB |05-09-16 | |

| |1 |The principles of Inclusion – Exclusion |BB |07-09-16 | |

| |1 |Pigeon hole principles and its application |BB |09-09-16 | |

| |1 |Tutorial class |BB | |12 |

| | |Unit IV : Recurrence Relation |BB |11-09-16 & | |

|4 | | | |12-09-16 | |

| |2 |Generating Functions |BB |14-09-16, | |

| | | | |16-09-16 | |

| |2 |Function of Sequences Calculating Coefficient of |BB | 17-09-16, | |

| | |generating function | |19-09-16 | |

| |2 | Recurrence relations |BB |21-09-16 | |

| |1 |Tutorial class |BB |23-09-16, | |

| | | | |23-09-16, | |

| | | | |23-09-16 | |

| |3 |Solving recurrence relation by substitution and |BB |24-09-16, | |

| | |Generating funds | |24-09-16, | |

| | | | |28-09-16 | |

| |3 |Characteristics roots solution of In homogeneous |BB |28-09-16 | |

| | |Recurrence Relation. | | | |

| |1 |Tutorial class |BB | |14 |

|5 | |Unit V: Graph Theory; |BB |28-09-16 | |

| |1 |Representation of Graph |BB |29-09-16 & | |

| | | | |30-09-16 | |

| |2 |DFS, BFS, Warshalls algorithm |BB |03-10-16 | |

| |1 |Spanning Trees |BB/PPT |3-10-16 | |

| |1 |Planar Graphs |BB |3-10-16 | |

| |1 |Tutorial class |BB |3-10-16 | |

| |1 |Graph theory and Applications, Duality |BB |28-10-16 | |

| |2 |Basic Concepts Isomorphism and Sub graphs |BB |29-10-16 | |

| |1 |Multi graphs and Euler circuits |BB |31-10-16 | |

| |1 |Hamiltonian graphs, Chromatic Numbers |BB/PPT |02-11-16 | |

| |1 |Tutorial class |BB | |12 |

II CSE-B

|Unit |Total no of | Topics to be covered | Teaching aids used|Date |Remarks |

| |Periods | |LCD/OHP/BB | | |

| 1 | |Unit I : Mathematical Logic ; Predicates | | | |

| |1 |Statements and notations, Connectives, Well formed formulas |BB |13-06-16 | |

| |1 |Truth Tables, tautology |BB |15-06-16 | |

| |2 | Equivalence implication |BB |17-06-16& 18-06-16| |

| |2 |Normal forms. |BB |20-06-16& 22-06-16| |

| |1 |Quantifiers, universal quantifiers |BB |24-06-16 | |

| |1 |Tutorial Class |BB |25-06-16 | |

| |1 |Predicative logic |BB |27-06-16 | |

| |1 | Free & Bound variables |BB |29-06-16 | |

| |2 | Rules of inference |BB |01-07-16 & | |

| | | | |02-07-16 | |

| |2 |Consistency, Proof of contradiction |BB |03-07-16 & | |

| | | | |04-07-16 | |

| |2 |Automatic Theorem Proving. |BB |06-07-16 & | |

| | | | |08-07-16 | |

| |1 |Tutorial Class |BB |11-07-16 |17 |

|2 | |Unit II: Relations ; Algebraic structures |BB | | |

| |2 |Properties of binary Relations, equivalence |BB |13-07-16 & | |

| | | | |15-07-16 | |

| |2 |Transitive closure,Compatibility and partial ordering relations |BB |16-07-16& 18-07-16| |

| |1 |Lattices ,Hasse diagram |BB |20-07-16 | |

| |2 |Functions: Inverse Function Composition of functions , recursive |BB |22-07-16 & | |

| | |Functions | |23-07-16 | |

| |2 |Lattice and its Properties |PPT |25-07-16 & | |

| | | | |27-07-16 | |

| |1 |Tutorial class |BB |01-08-16 | |

| |2 |Algebraic systems Examples and general properties |BB |03-08-16 & | |

| | | | |05-08-16 | |

| |2 |Semi groups and monads |BB |06-08-16 & | |

| | | | |15-08-16 | |

| |1 |groups sub groups |BB |17-08-16 | |

| |1 |Homomorphism |BB |19-08-16 | |

| |1 |Isomorphism, |BB |19-08-16 | |

| |1 |Tutorial class |BB |20-08-16 |18 |

|3 | |Unit III : Elementary Combinatorics |BB | | |

| |1 |Basis of counting |BB |22-08-16 | |

| |2 |Combinations & Permutations with repetitions |BB |24-08-16 & | |

| | | | |26-08-16 | |

| |1 |Constrained repetitions |BB |27-08-16 | |

| |2 |Binomial Coefficients |BB |29-08-16 | |

| |1 |Tutorial class |BB |31-08-16 | |

| |2 |Binomial Multinomial theorems |BB |01-09-16 & 4-09-16| |

| |1 |The principles of Inclusion – Exclusion |BB |05-09-16 | |

| |1 |Pigeon hole principles and its application |BB |07-09-16 | |

| |1 |Tutorial class |BB |09-09-16 |12 |

| | |Unit IV : Recurrence Relation |BB | | |

|4 | | | | | |

| |2 |Generating Functions |BB |11-09-16 & | |

| | | | |12-09-16 | |

| |2 |Function of Sequences Calculating Coefficient of generating |BB |14-09-16, 16-09-16| |

| | |function | | | |

| |2 | Recurrence relations |BB | 17-09-16, | |

| | | | |19-09-16 | |

| |1 |Tutorial class |BB |21-09-16 | |

| |3 |Solving recurrence relation by substitution and Generating funds |BB |23-09-16, | |

| | | | |23-09-16, 23-09-16| |

| |3 |Characteristics roots solution of In homogeneous Recurrence |BB |24-09-16, | |

| | |Relation. | |24-09-16, 28-09-16| |

| |1 |Tutorial class |BB |28-09-16 |14 |

|5 | |Unit V: Graph Theory; |BB | | |

| |1 |Representation of Graph |BB |28-09-16 | |

| |2 |DFS, BFS, Warshalls algorithm |BB |29-09-16 & | |

| | | | |30-09-16 | |

| |1 |Spanning Trees |BB/PPT |03-10-16 | |

| |1 |Planar Graphs |BB |3-10-16 | |

| |1 |Tutorial class |BB |3-10-16 | |

| |1 |Graph theory and Applications, Duality |BB |3-10-16 | |

| |2 |Basic Concepts Isomorphism and Sub graphs |BB |28-10-16 | |

| |1 |Multi graphs and Euler circuits |BB |29-10-16 | |

| |1 |Hamiltonian graphs, Chromatic Numbers |BB/PPT |31-10-16 | |

| |1 |Tutorial class |BB |02-11-16 |12 |

II CSE-C&D

|Unit |Total no of | Topics to be covered | Teaching aids used|Date |Remarks |

| |Periods | |LCD/OHP/BB | | |

| 1 | |Unit I : Mathematical Logic ; Predicates | | | |

| |1 |Statements and notations, Connectives, Well formed formulas |BB |14-06-16 | |

| |1 |Truth Tables, tautology |BB |15-06-16 | |

| |2 | Equivalence implication |BB |16-06-16& | |

| | | | |17-06-16 | |

| |2 |Normal forms. |BB |18-06-16& | |

| | | | |21-06-16 | |

| |1 |Quantifiers, universal quantifiers |BB |22-06-16 | |

| |1 |Tutorial Class |BB |23-06-16 | |

| |1 |Predicative logic |BB |24-06-16 | |

| |1 | Free & Bound variables |BB |25-06-16 | |

| |2 | Rules of inference |BB |28-06-16 & | |

| | | | |29-06-16 | |

| |2 |Consistency, Proof of contradiction |BB |30-06-16 & | |

| | | | |01-07-16 | |

| |2 |Automatic Theorem Proving. |BB |02-07-16 & | |

| | | | |05-07-16 | |

| |1 |Tutorial Class |BB |07-07-16 |17 |

|2 | |Unit II: Relations ; Algebraic structures |BB | | |

| |2 |Properties of binary Relations, equivalence |BB |08-07-16 & | |

| | | | |12-07-16 | |

| |2 |Transitive closure,Compatibility and partial ordering relations |BB |13-07-16& | |

| | | | |14-07-16 | |

| |1 |Lattices ,Hasse diagram |BB |15-07-16 | |

| |2 |Functions: Inverse Function Composition of functions , recursive |BB |16-07-16 & | |

| | |Functions | |19-07-16 | |

| |2 |Lattice and its Properties |PPT |20-07-16 & | |

| | | | |21-07-16 | |

| |1 |Tutorial class |BB |22-07-16 | |

| |2 |Algebraic systems Examples and general properties |BB |23-07-16 & | |

| | | | |26-07-16 | |

| |2 |Semi groups and monads |BB |27-07-16 & | |

| | | | |28-07-16 | |

| |1 |groups sub groups |BB |29-07-16 | |

| |1 |Homomorphism |BB |30-07-16 | |

| |1 |Isomorphism, |BB |02-08-16 | |

| |1 |Tutorial class |BB |03-08-16 |18 |

|3 | |Unit III : Elementary Combinatorics |BB | | |

| |1 |Basis of counting |BB |04-08-16 | |

| |2 |Combinations & Permutations with repetitions |BB |05-08-16 & | |

| | | | |06-08-16 | |

| |1 |Constrained repetitions |BB |16-08-16 | |

| |2 |Binomial Coefficients |BB |17-08-16 | |

| |1 |Tutorial class |BB |18-08-16 | |

| |2 |Binomial Multinomial theorems |BB |19-08-16 & | |

| | | | |20-08-16 | |

| |1 |The principles of Inclusion – Exclusion |BB |23-08-16 | |

| |1 |Pigeon hole principles and its application |BB |24-08-16 | |

| |1 |Tutorial class |BB |26-08-16 |12 |

| | |Unit IV : Recurrence Relation |BB | | |

|4 | | | | | |

| |2 |Generating Functions |BB |27-08-16 & | |

| | | | |30-08-16 | |

| |2 |Function of Sequences Calculating Coefficient of generating function |BB |31-08-16, | |

| | | | |01-09-16 | |

| |2 | Recurrence relations |BB | 02-09-16, | |

| | | | |03-09-16 | |

| |1 |Tutorial class |BB |06-09-16 | |

| |3 |Solving recurrence relation by substitution and Generating funds |BB |07-09-16, | |

| | | | |08-09-16, | |

| | | | |09-09-16 | |

| |5 |Characteristics roots solution of In homogeneous Recurrence Relation. |BB |13-09-16, | |

| | | | |14-09-16, | |

| | | | |15-09-16 | |

| | | | |16-09-16 | |

| | | | |17-09-16 | |

| |1 |Tutorial class |BB |20-09-16 |14 |

|5 | |Unit V: Graph Theory; |BB | | |

| |2 |Representation of Graph |BB |21-09-16 | |

| | | | |22-09-16 | |

| |2 |DFS, BFS, Warshalls algorithm |BB |23-10-16 & | |

| | | | |24-10-16 | |

| |1 |Spanning Trees |BB/PPT |27-10-16 | |

| |1 |Planar Graphs |BB |28-10-16 | |

| | | | |29-10-16 | |

| |1 |Tutorial class |BB |27-10-16 | |

| |1 |Graph theory and Applications, Duality |BB |28-10-16 | |

| |2 |Basic Concepts Isomorphism and Sub graphs |BB |29-10-16 | |

| |1 |Multi graphs and Euler circuits |BB |01-11-16 | |

| |1 |Hamiltonian graphs, Chromatic Numbers |BB/PPT |02-11-16 | |

| |1 |Tutorial class |BB |03-11-16 |12 |

Total no of classes: 73

10. DETAILED NOTES

UNIT-I

1 OVERVIEW

To understand mathematics, we must understand what makes up a correct mathematical argument that is a proof. The values of logic give precise meaning to mathematical statement. These values are used to distinguish between valid and invalid mathematical arguments. The importance on understanding mathematical reasoning, logic has numerous applications on computer science. These values are used in the design of computer circuits, construction of computer programs, verification of correctness of programs and in many often ways. Recursive functions, which are functions defined in terms of themselves are used throughout computer science.

Important points and definitions:

Negation: If “P” denotes a statement, then the negation of “p” is T, then the truth value of “7p”is F. Also if the truth-value of “p” is F, then the truth-value of “7p” is T.

Conjunction: The conjunction of two statements p and q is the statement p^q which is read as “p and q”. The statement p^q has the truth value T whenever both p and q have the truth value T. otherwise it has the truth value F.

Disjunction: The disjunction of two statements p and q is the statement pvq which is read as “p or q”. The statement pvq has the truth-value F only when both P and Q have the truth value F, otherwise it is true.

Conditional: If p and q are any two statements, then the statement p→q which is read as s“if p, then q” is called a conditional statement. The statement p→q has a truth value F when q has the truth value F and p the truth-value T; otherwise it has the truth value T.

Biconditional: If p and q are any two statements, then the statement p↔q which is read as “p if and only if q” and abbreviated as “P iff q” is called a biconditional statement. The statement p↔q has the truth value T whenever both p and q have identical truth values.

Well-formed formulas: A statement formula is an expression which is a string consisting of variables, capital letters with or with out subscripts, parentheses and connective symbols.

Tautology: A statement formula, which is true regardless of the truth-values of the statements, which replace the variables in it, is called a universally valid formula or a tautology or a logical truth.

i.e if each entry in the final column of the truth table of a statement formula is T alone, then it is called as tautology.

Contradiction:

A statement formula which is false regardless of the truth values of the statements which

Replaces the variables in it is called a contradiction.

i.e if each entry in the final column of the truth table of a statement formula is F alone, then it is called as contradiction.

Equivalence of formulae:

Two formulas A and B are said to be equivalent to each other if and only if A↔B is a tautology.

Replacement Process:

Consider the formula A:P→(Q→R).The formula Q→R is a part of the formula A. if we replace Q→R by an equivalent formula 7QVR in A, we get another formula B: P→(7QVR).one can easily verify that the formulas A and B are equivalent to each other. This process of obtaining B from A is known as the replacement process.

Law of duality:

Two formulas A and A* are said to be duals of each other if either one can be obtained from the other by replacing ^ by and v and v by ^.The connectives ^ and v are also called duals of each other. If the formula A contains the special variables T or F, the A*,it’s dual is obtained by replacing T by F and F by T in addition to the above-mentioned interchanges.

Tautological implications:

A statement A is said to tautologically imply a statement B if and only if A→B is a tautology. In this case, we write A⇒ B, read as “A implies B”.

Functionally complete set of connectives:

A set of connectives is said to be functionally complete set of connectives if every formula can be expressed in terms of an equivalent formula containing the connectives only from this set.

* Functionally complete set should not contain any redundant connectives i.e., a connective which can be expressed in terms of the other connectives.

Normal forms:

A better method is to transform the statement formulas A and B to some standards forms A’ and B’ such that a simple comparison of A’ and B’ shows whether A⇔B. The standard forms are called canonical forms or normal forms.

Disjunctive Normal Forms(d.n.f):

A formula which is equivalent to a given formula and which consists of a sum of elementary products is called a disjunctive normal form of the given formula.

Conjunctive Normal forms:

A formula which is equivalent to a given formula and which consists of a product of elementary sums is called a conjunctive normal form of the given formula.

Principle Disjunctive Normal Form (p.d.n.f):

A min term consists of conjunctions in which each statement variable or it’s negation, but not both, appears only once.

An equivalent formula consisting of disjunction of min terms only is known as its principle disjunctive normal form (sum-of-products canonical form), simply p.d.n.f.

Principle Conjunctive Normal Forms (p.c.n.f):

A max term consists of disjunctions in which each variable or it’s negation, but not both, appears only once.

An equivalent formula consisting of conjunctions of max terms only is known as principle conjunctive normal form (product-of-sums canonical form), simply p.c.n.f.

Statement Calculus: Theory of Inference

The main aim of logic is to provide rules of inference to infer a conclusion from certain premises. The theory associated with rules of inference is known as inference theory.

If a conclusion is derived from a set of premises by using the accepted rules of reasoning then such a process of derivation is called a deduction or a formal proof, and the argument or conclusion is called a valid argument or valid conclusion.

Indirect method of proof:

The method of using the rule of conditional proof and the notation of an inconsistent set of premises is called the indirect method of proof or proof by contradiction.

The predicate calculus:

The logic based upon the analysis of predicates in any statement is called predicate logic.

Quantifiers:

Certain statements involve words that indicate quantity such as ‘all’,’ some’, ’none’

or ‘one’. They answer the question ‘How many?’ Since such words indicate

quantity they are called Quantifiers.

Bound and Free variables:

Generally predicate formulas contain a part of the form (∀x)p(x) or (∃x)p(x).such

a part is called x-bound part of the formula. Any variable appearing in an x

bound part of the formula is called bound variable. Otherwise it is called

free variable.

UNIT-II

1 OVERVIEW

Many important discrete structures are built using sets, which are collections of objects. Among the discrete structures, which are built from sets, are combinations, which are unordered collection of objects used extensively in counting. Relations, which are sets of ordered pairs, represent relationship between objects.

Graphs, which consists of set of vertices and edges that connect vertices.

The concept of functions is extremely important in discrete mathematics. A function assigns to each element of a set precisely one element of a set. Useful structures such as Sequences and strings are special types of functions. They are used to represent computational complexity of algorithms, to study the size of sets, to count the objects of Different kinds and in many other ways.

Important points and definitions:

Set : A set is a collection of objects , called elements which share some common property.

• Let A and B be two sets. Then A is said to be a subset of B if every element of A is an element of B;

• A is said to be a proper subset of B if A is a subset of B and there is at least one element of B which is not in A.

• Two sets A and B are equal ⇔ A⊆B and B⊆A.

• A set is called universal set if it includes every set under discussion. A universal set

Will be denoted by U.

• A set, which does not contain any element, is called an empty set or a null set, denoted by ϕ.

• For a set A, a collection or family of all subsets of A is called the power set of A, denoted by P(A).

• If A and B are sets with no elements in common i,e., no element of A is in B and no element of B is in A, then the sets are disjoint.

• The intersection of any two sets A and b, written as A∩B is the set consisting of all the elements which belong to both A and B. symbolically

A∩B={x|(x∈A)∧(x∈B)}

• Let A and B be any two sets. The relative complement of B in A(or of B w.r to A) written as A-B, is the set consisting of all elements of A which are not elements of B, that is

A-B={x|x∈A ∧ x ∉B)

• Let A and B be any two sets. Then the symmetric difference is denoted by AΔB. Then we can write AΔB = (A-B)U(B-A)

• If any set A having n elements then the power set of A contains 2n.

Basic laws of set algebra:

i) Idempotent laws : A∪A=A

A∩A=A

ii) Associative Laws: (A∪B) ∪C=A∪(B∪C)

(A∩B) ∩C=A∩ (B∩C)

iii) Commutative Laws: A∪B=B∪A

A∩B=B∩A

iv) Distributive laws: A∪(B∩C)=(A∪B)∩ (A∪C)

A∩(B∪C)=(A∩B) ∪(A∩C)

v) Absorption laws: A∪(A∩B)=A

A∩(A∪B)=A

s

vi)Demorgan’s Laws: (A∪B)’=A’∩ B’

(A∩B)’=A’∪B’

Relations

* Let R be a relation from A to B. The domain of R denoted by domR is defined:

domR={x|x∈A and (x, y) ∈R for some y∈B}

The range of R, denoted by ran R is defined

RanR={y/y ∈B and (x, y) ∈R for some x∈A}

Properties of relations:

A relation R on a set A is said to be

i) Reflexive if xRx or (x, x) ∈R ∀x∈A

ii) Irreflexive if x not relates to x or (x, x)∉R ∀x∈A

iii) Symmetric if XRY ⇒YRX,for all x,y∈A

iv) Antisymmetric if x≠y and XRY⇒y not relates to x or (y,x)∉R,for

All x, y∈A

(OR)

Whenever x R y and y R x, then x=y.

v) Transitive if x R y and y R z ⇒ xRz,for all,x,y,z ∈A

vi) Asymmetric if XRY ⇒ynot elates to x or (y, x)∉ R

Equivalence relations:

A relation R in a set X is called an equivalence relation if it is reflexive, symmetric and transitive.

• Let S be a given set and A={A1,A2…….Am} where each Ai, i=1,……m is a subset of S and UA i= S where I= 1 to m.

Then the set A is called a covering of S, and the sets A1, A2,…. Am are said to cover S.

* The transitive closure of a relation R is the smallest transitive relation containing R. We denote transitive closure of R by R+. Let X be any finite set containing n elements and R be A relation on x. The relation R+=R∪R2∪R3∪…..∪Rn in X is called the transitive closure of R in X.

• Warshall’s algorithm is an efficient method for computing the transitive closure of a relation.

• A relation R in X is said to be a compatibility relation if it is reflexive and symmetric.

• A binary relation R in a set p is called a partial order relation or a partial ordering in p ii R is reflexive, ant symmetric and transitive.

• In a poset (p, ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download