Powered by ZigaForm version 3.7.8

Enter your keyword

Mathematical Foundations of Computer Science(18D08101)

COURSE: M.TECH                                                    BRANCH:  CSE        

YEAR & SEM:   I-I                                                     REGULATION: R18

UNIT-I

1. Expailn in detail about logical connectives with examples

2. a) Defined well formed formula .Explain about tautology and contraduction with examples.

b) Determind whether the conclusion “C” follows logically from the premises H1^H2.

H1:7p,H2:p↔Q,C:7(p^Q).

3.(a) show that ((PvQ)^7(7P^(7Qv7R)))v(7P^7Q)v(7P^7R) is a tautology.

(b)Write the P.D.N.F and P.C.N.F for using following formulas without using truth table Pv(QR).

4.Using inference theory for statement calculus ,show the following implications.

      (a).(PvQ) and (PR) and (QS)SvR

       (b). show that R →S can be derived from P→(Q→S),(7RvP) and Q.

5. show that SvR is a tautologically implied by ((PvQ)^(P→R)^(Q→S)).

6. show that from (a) (x)(F(x)^S(x)→(y)(M(y)→W(y)).

            (b)(y)(M(y)^7W(y)) then conclusion (x)(F(x)→7S(x)) follows .

7.Show That (x) (P(x)vQ(x))(x)P(x)v(x)Q(x).

8. show that R^(PvQ) is a valid conclusion form the premises PvQ,Q→R,PM and

UNIIT-II

  1. Define the following with examples .Set,proper subset ,empty set,power set, compliment.

  2. a)Show that for any two sets A and B if. A-(A.

             b)Show that AB =(A (B).

  1. Find how many integers b/w 1 and 60 that are not divisible by ‘2’ nor by ‘3’ nor by ‘5’. Also determine the no.of integers divisible ‘5’ not by ‘2’ not by ‘3’.

  2. Define a Equivalence Relation . If R be a relation in the set of integers ‘Z’ defind by

        R={(x,y)/x ,y ,(x-y) is divisibie by 6}.Then provr that ‘R’ is an Equivalence Relation .

5.a) Define group ,semi group, sub group and abelian group.

     b) Define group and an abelian group.Prove that the set Z of all integers with the binary operation ∗,Define as a∗b=a+b+1 a,bZ Is an abelian group.

6.a) The necessary and sufficient condition for a non empty subset H of a group (G,∗) to be a subgroup Is a a∗b-1H.

   b).Prove that A non empty subset H of a group G is a subgroup of G Iff

          I) aH,bH a∗bH 2)aHa-IH, where a-I is the inverse of a in G.

7. a)Let (L,≤) be a lattice in which ∗ and denote the meet and join respectively for any a,bL.Prove That a≤b =a ab=b.

  b) Define Boolean algebra.In any Boolean algebra prove that a=b iff abl alb =0.

8. a)Prove that every chain is a distributive lattice .

   b)Show that in a complemented distributive lattice if a≤b a∗bl alb=1 bl≤ al.

UNIT-III

1.How many ways can the digits 0,1,2,3,4,5,6,7,8,9 be arranged so that

                   a) 0&1 adjacent and in the order of 01 b) 0&1 adjacent c) 0&1 are not adjacent.

2.Suppose there are 5 boys and 3 girls

                a) In howmany ways can they sit in a row.

                b) How many sitting arrangements are there with no two girls sitting together.

                c) How many arrangements when all the girls never together.

                d) How many ways all the girls sit together and all the boys sit together.

               e) In how many than can they sit in a row if the boys are to sit together and the girls do not sit together.

3.A man has 7 relatives ,4 of them are ladies and 3 gentlemen,has wife has 7 relatives and 3 of them are ladies and 4 gentlemen . In howmany ways can they invite a dinner party of 3 ladies and 3 gentlemen so that there are 3 of wife relatives?

4. state and prove Binomial theorem and Multionmial theorem

5.Find the coefficient of a) x2 y4 in (x+y)6 b) x3y2z2 in (x+y+z)9

6.Explain Principle of inclusion & Exclusion give an example ?

7. Compute a) 20 b) Find n if (n+1)12x(n-1) c)Convent the product 6.7.8.9.10 into factorial.

8. a) Compute the no.of the committees of three members each that can be formed from the committee of 25 members.

    b)In how many was a committee of 5 members can be selected from 6 men and 5 women consisting of 3 men and 2 women ?

9.Find the no.of unordered samples of size five (repitation allowed) from the set .

                  a)No further restrictions b) ‘a’ occur atleast twice. C) ‘a’ occur exactly twice.

10. Find the no.of arrangement of the letters in the word a)”ACCOUNTANT “ b) “COMMERCE “

                     c) “PROGRAMMING” d) “MATHEMATICS”

UNIT-IV

1. Find a closed form for the generating function for each of the following sequence a)0,0,1,1,1…….

           b) 1,1,0,1,1,1,1,1,…. C) 1,0,-1,0,1,0,-1,0,1,…. D) 3,-3,3,-3,3,-3,…..

2. A person invest Rs 10,000/- @12% intrest compound annually. how much will be there of the end of 15years

3.Solve the recurrence relation of the Fibonacci sequence of number fn=fn-1+fn-2 n with the initial condition f0=0,f1=1

4.Solve fn=fn-1+fn-2,n2 with initial condition f0=f1=1 using fibonaci sequence

5. Solve the following RR by using iteration method

             1). an =an-1+f(n),n1 2). an=an-1+3n if n1 at a0=1

6Solve an+3-5an+1+6an=2 with initial condition a0=1 and a1=-1

7.Solve the followingyn+2-yn+1-2yn=n2

8.Solve by using generating function an-9an-1+20an-2=0 with initial condition a0=-3,a1=-10

9. By using generating function an+2-2an+1+an=2n with initial condition a0=2,a1=1

10.Suppose there are n guests of a dinner Party.each person shakes hands with everybody else exactly once,deduce the recurrence relation for the number of handshakes that occurs and solve the by iterative method.

UNIT-V

1.a) 1.What is a graph? Explain in detail.

             b).Define the following with an example . a) Sub graph b) Spaning subgraph c) Null graph.

2.a)Let G be undirected graph with E|=e edges and |v|=n vertices then show that Vi)=2|E|.

               b)Show that the sum of in degree of all nodes of a simple diagraph is equal to the sum of out degrees of all its nodes and that this sum is equal to the number of edges.

3 .a)In any graph G prove that the total number of vertices of odd degree is even.

        b)Define isomorphism of two graphs. Give an example.

4.a) Define the following a)Walk b)Closed walk c) Open walk

    b)Prove that the maximum no. Of edges in a simple graph with small n nodes in nc2 (or) (or) .

5.a) What are Eulerian graph and Hamiltonian graph ?Explain briefly with an example

        b) explain with Fleury’s Algorithm with any suitable example .

6. Explain about the Chinese postman problem ?

7.Explain about the Traveling sales man problem.

8.What do you mean by graph traversal ?Explain the different graph traversal with an Example .

1). an =an-1+f(n),n1 2). an=an-1+3n if n1 at a0=1

6Solve an+3-5an+1+6an=2 with initial condition a0=1 and a1=-1

7.Solve the followingyn+2-yn+1-2yn=n2

8.Solve by using generating function an-9an-1+20an-2=0 with initial condition a0=-3,a1=-10

9. By using generating function an+2-2an+1+an=2n with initial condition a0=2,a1=1

10.Suppose there are n guests of a dinner Party.each person shakes hands with everybody else exactly once,deduce the recurrence relation for the num

6. Explain about the Chinese postman problem ?

7.Explain about the Traveling sales man problem.

8.What do you mean by graph traversal ?Explain the different graph traversal with an Example .