Course Title:MATHEMATICAL FOUNDATIONS of COMPUTER SCIENCE

Course Code:53022

Course Title:MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE

Semester : I

Course Time : July – Nov 2012.

TIME TABLE

Faculty Details:

Text Books & Reference Books:

1. Discrete Mathematical Structures with applications to computer science Trembly J.P. & Manohar.P, TMH
2. Discrete and Combinational Mathematics- An Applied Introduction-5th Edition – Ralph. P.Grimaldi. Pearson Education.

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

UNIT-I

MATHEMATICAL LOGIC: Statements and notations, connectives, well formed formulas. Truthtables, tautology, equivalenceimplication, Normal forms, Quantifiers, universal quantifiers.

Objective:

To discuss the concepts associated with mathematical logics, propositions well formed formulas and their applications.

Ability to learn the notations, connectives.

To understand the constructionof truth Tables.

To know the universal quantifier, existential quantifier.

Lecture Plan:

Assignment:

1.Explain with examples WFF, PCNF, PDNF, CNF, Tautology, and Contradiction.

2.Construct the truth tables for following compound prepositions

[(pᴧq) U(┐r)] ↔p

p→(q↔r)

p or[q→(rᴧp)↔(q U┐r)

3.What are laws of logic?

4.Find the duality of u=(p→q) →r

5.Find PCNF of ┐p ᴧq, (┐p→r) ᴧ (q ↔p)

UNIT-II

PREDICATES: Predicate logic, Free&Bound variables,Rules of inference,Consistency,Proof of contradiction,Automatic Theorem Proving.

Objective:

To discuss the concepts associated with predicates, Rule of inferences and their applications

To know the difference between free and bound variables

To know how to apply Antecedent rules, Consequent rules.

Lecture Plan:

Assignment:

1. Prove valid or not

If I study then I don’t fail in the exam.

If I don’t fail in the exam, my father gives me a two wheeler.

If I study then my father gives me a 2 wheeler.

2.(pᴧq) →r,r→sthen ┐ s →(┐q v ┐p)

3.p → r, ┐p → r,q → s then ┐r→ s

4.p →q,r→s,p or r then q v s

UNIT-III

RELATIONS: Properties of Binary Relations, equivalence, transitive, closure, compatibility and partial ordering relations.Lattices, Hassediagram. Functions: Inverse function Composition of functions, recursivefunctions, Lattice &its properties.

Objective:

To discuss the basic concepts associated with relations and functions, and their applications

To know about sets,relations, functions and their properties

Ability to learn lattice and its properties

To draw different diagrams like Lattice,Hasse diagrams.

Lecture Plan:

Assignment:

1.A={1,3,5} ,B={2,3} C={4,6} find A X B ,B X A ,(A U B) X C,(A X B) U(B XC).

2.Draw the Hasse diagram for R={(1,1),(1,2),(1,3)(2,3)(2,4)(3,4)}

3. Explain the properties of relations with examples.

UNIT-IV

ALGEBRAIC STRUCTURES: Algebraic systems Examples and general properties, Semi groups and monads, groups sub groups, homomorphism, Isomorphism.

Objective:

To present the concepts of groups and rings. Also, we aim to at describing the application of groups to error detection and correction.

To know the concepts of homomorphism, Isomorphism

Ability to learn basic definitions groups,monoiads,subgroups, semi groups and rings.

Lecture Plan:

Assignment:

1.Define and explain homomorphism, Isomorphism with examples.

2.Explain different categories of Groups with examples.

3.List the differences between semi group homomorphism, semi group isomorphism.

4.If N denotes the set of all natural numbers and + and * are the usual addition and multiplication

operations ,show that <N,+,*> is not a ring.

5.If<R, +, ∙> is a ring with unity 1, Prove that (-1).a=-a, for all a belongs R, and (-1) ∙ (-1) =1.

UNIT-IV

ELEMENTARY COMBINATORICS:Basics of counting,Combinations &Permutations. with repetitions,Constrained repetitions,Binomial Coefficients,Binomial Multinomial theorems,the principles of Inclusion- Exclusion.Pigeon hole principles and its application.

Objective:

To discuss the basic concepts of permutations, combinations, discrete probability and conditional probability

To understand the Permutations and Combinations Problems

To know the Pigeon hole principle and its applications.

Lecture Plan:

Assignment:

1. Find the number of nonnegative integer solutions of the inequalityx1+x2+x3+…….+x6<10
2. In how many ways can we distribute 7 apples and 6 oranges among 4 children so that each

child gets at least 1 apple?

1. Show that C(n-1 +r,r) represents the number of binary numbers that contains (n-1) 1’s and r 0’s.
2. Find the number of ways of placing 20 identical balls into 5 boxes with atleast one ball put into each box.

UNIT-IV

RECURRENCE RELATION: GeneratingFunctions, Functions of sequences Calculating Coefficient of generating function, Recurrencerelations, Solving recurrence relation by substitution and Generating functions. Characteristics roots solution of non homogeneous Recurrence Relation

Objective:

To present various types of recurrence relations and the methods to find out their solutions

How to calculate Coefficient of generating function?

To discuss the problems on characteristics roots for solving homogeneous and non homogeneous recurrence relations

Lecture Plan:

Assignment:

1. Find a recurrence relation and the initial condition for the sequence 2,10,50,250………

2. A bank pays a certain % of annual interest on deposits, compounding the interest once in 3 months. If

a deposit doubles in 6 yrs and 6 months ,what is the annual % of interest paid by the bank.

3. Find a recurrence relation for the number of binary sequences of length n>=1 that have no

Consecutive 0’s.

4. Find the general solution of the recurrence relation

an-7an-2+10an-4=0,n>=4

UNIT-VII

GRAPH THEORY: Representation of Graph,DFS,BFS,Spanning Trees,Planar graphs.

Objective:

Basic concepts of graphs, Planar graphs.

Representation of graphs, trees.

Difference between DFS, BFS

Lecture Plan:

Assignment:

1. Show that the complete bipartite graph K33 is non planar.

2. A necessary and sufficient condition for a graph G to be a planar is that G does not contain K5or K3,3 as a sub graph.

3. Prove that the Petersen graph is nonplanar.

4. Show that every graph with 4 or fewer vertices is planar.

5. Find the maximum number of edges possible in simple connected planar graph with 4 vertices.

UNIT-VIII

GRAPH THEORY AND APPLICATIONS: Basicconcepts, Isomorphism and sub graphs,Multi graphs and Euler circuits,Hamiltonian graphs,Chromatic Numbers.

Objective:

Applications of graph theory.

What are sub graphs,multigraphs and their differences?

Euler circuits, Hamiltonian graphs,Chromatic numbers.

How Chromatic numbers are useful?

Lecture Plan:

Assignment:

1. What are the applications of graph theory?

2. Explain Chromatic number and Map Coloring Problem with examples.

3. Give the difference between DFS and BFS by considering examples.

4. Prove that a connected graph G has an Euler circuit if and only if all vertices of G are of even degree.

5. Is there a graph with odd number of vertices and even number of edges that contains an Euler

circuit?