Name of the Institute : Babu Banarasi Das National Institute of Technology & Management
Degree : BCA
Department : Computer Applications
Subject Code/Name : (BCA-305) Discrete Mathematics
Year : 2nd
Semester : 3rd
Document Type : Question Bank
Website : bbdnitm.ac.in
Download Model/Sample Question Paper :https://www.pdfquestion.in/uploads/bbdnitm.ac.in/3169-BCA-C-305DM-QBANk.pdf
BBDNITM Discrete Mathematics Question Bank
BCA-305 – Discrete Mathematics Question Bank
Related / Similar Question Paper : BBDNITM BCA Database Management System Question Bank
Unit-1
1) Explain the principle of inclusion and exclusion with an appropriate example.
2) In a survey of 300 Students, 64 had taken a mathematics course, 94 had taken an English course, 58 had taken a computer course, 28 had taken both mathematics and computer course, 26 had taken both an English and mathematics course, 22 had taken both English and a computer course, 14 had taken all three courses.
(i) How many students were surveyed who has taken none of the three courses?
(ii) How many had taken exactly one of the 3 subjects?
3) Among the first 1000 positive integers :
(i) Determine the integers divisible by 5, nor by 7, nor by 9.
(ii) Determine the integers divisible by 5, but not by 7, not by 9.
5) Define the Recurrence Relations. Explain linear Recurrence Relations with constant coefficients with appropriate examples.
6) Sole the difference equation (Recurrence Relations) 2ar-5ar-1+2ar-2 = 0 and find particular solutions, such that a0 = 0 and a1 = 1.
7) State and prove pigeonhole principle.
8) What is inclusion – exclusion principle? How many bit strings of length eight start with one bit or end with the two bits 00?
9) What is the solution of Recurrence Relations :
an = an-1 + 2 an-2
With a0 = 2 and a1 = 7?
10) Define generating function. What is generating function of sequence { ak }, k = 0,1,2 …….. ?
12) (i) Find the Recurrence Relations of the sequences.
(a) S = {5, 8, 11, 14, 17} (b) S = {1, 1, 2, 3, 5, 8, 13}
(ii) Find first four terms of each of the following Recurrence Relations.
(a) ak = 2 ak-1 + k , for all integers k = 2 , a0 = 1 .
(b) ak = ak-1 + 3ak-2 , for all integers k = 2, a0 = 1, a1 = 2.
13) Solve an+2 – 5 an+1 + 6an = 2 with initial condition a0 = 1 and a1 = -1.
14) (i) Find the generating function for the sequence 1, a, a2, a3 ….where a is fixed constant.
(ii) Find the closed form for the generating function for each of the following sequence.
(a) 1 – z + z2 – z3 + z4 – z5 +…
(b) 1 + 2z + 4z2 + 8z3 + 16z4 + 32z5 +…
(c) z + z2 + z3 + z4 + z5 + …
(d) 3 – 4z + 4z2 – 4z3 + 4z4 – 4z5 +…
(e) 1 – z2 + z4 – z6 + z8 – z10 +……
(iii) Obtain partial fraction decomposition and identify the sequence having the expression as a generating function.
(a) 1/ 5 – 6 z + z2
(b) 3 – 5z/ 1 – 2z – 3z2
15) Write short notes on the following.
(i) Generating function
(ii) Recurrence Relation
(iii) Closed form
(iv) Polynomials
Unit-2
1) Consider the following—
P : Anil is rich
Q : Kanchan is poor
Write each of the following statement in the symbolic forms
(i) Anil and Kanchan are both rich.
(ii) Anil is poor and Kanchan is rich.
(iii) Neither Anil nor Kanchan is poor.
(iv) It is not true that Anil and Kanchan are both rich.
(v) Eithrt Anil or Kanchan is poor
2) State the Converse , Inverse and Contra positive of the following—
(i) If today is Easter, Then tomorrow is Monday.
(ii) If P is square, then P is rectangle.
(iii) If n is prime, Then n is odd or n is 2.
3) What is predicate calculus? Write the predicate variable and propositional function also?
Unit-3
1) Write short notes on the following—
(i) Disjunctive normal form (ii) conjunctive normal form (iii) Principal disjunctive normal form (iv) Principle conjunctive normal form (v) Maxterms (vi) Minterms.
2) Represent the argument
If I study hard, then I get A’s
I study hard
—————————————- I get A’s
Symbolically and determine whether the argument is valid or not.
3) Represent the given argument is valid or not
If it rains today, then we will not have a party today
If we do not have party today, then we will have a party tomorrow
———————————————————————————
Therefore, if it rains today, then we will have a party tomorrow
4) Show that t is a valid conclusion from the premises
p => q , q => r , r => s ,-s .
5) Prove the validity of the following argument ?If I get the job and work hard, then I will get promoted. If I get promoted. Then I will be happy. I will not be happy. Therefore, either I will not get the job or I will not work hard.?
6) What are quantifiers? Explain the Existential and Universal quantifiers?
7) Write the different phrases where the Existential and Universal quantifier used?
8) Using rule of inferences, determine whether the following inference pattern are valid or not.
9) Rewrite the following argument using quantifiers, variable and predicate symbols.Prove the validity of the argument.
All healthy people eat an apple a day.
Ram does not eat an apple a day.
Therefore, Ram is not a healthy person.
Unit-4
1) (i) Write the definition of simple graph, multi graph and pseudo graph with example?
(ii) How many vertices and how many edges do the following graphs have?
a) Kn (b) Cn (c) Wn (d) Km,n (e) Qn
2) Draw a graph having the properties or explain why no such graph exists.
(i) Graph with four vertices of degree 1, 1, 2 and 3.
(ii) Graph with four vertices of degree sequence 1, 1, 3, and 3.
(iii) Graph with four vertices of degree sequence 3, 3,3,3,2.
(iv) Graph with four vertices of degree sequence 0, 1,2,2,3.
3) If a graph has exactly two vertices of odd degree, then they must be connected by a path.
4) Write definitions of the following with an example.
(i) Diagraph or directed graph
(ii) Complete graph
(iii) Bipartite graph
(iv) Sub graphs
(v) Induced sub graphs
(vi) Planner graph
(vii) Cut edge
(viii) Walk
(ix) Sub graph
(x) Multigraph
5) Consider the ahead graph. Determine the following.
(i) Pendent vertex
(ii) Odd vertices
(iii) Even vertices
(iv) Incident vertices
(v) Adjacent edges
(vi) In degree and Out degree
6) A simple graph with n vertices and k components cannot have more than (n-k) (n-k+1) edges.
Unit -5
1) Define the following with a example :
(i) Euler line
(ii) Decomposition
(iii) Components
(iv) Ring sum of two graphs
(v) Planner graph
(vi) Hamiltonian path and circuit
(vii) Eulerian path and circuit
(viii) Binary tree
(ix) Height of tree
2) (i) Prove that a tree with n vertices has n-1 edges.
(ii)Prove that respect to any of its spanning trees, a connected graph of n vertices and e edges has n-1 tree branches and e-n+1 chords.
3) (i) Draw a connected graph that becomes disconnected when any edged remove from it.
(ii) Simple graph and multi graph with two, three, and four vertices.
4) (i) A graph with n vertices and with no loops or parallel edges which has at least ½ (n-1) (n-2) +2 edges is Hamiltonian.
(ii) Give an example of a graph which is Hamiltonian but not Eulerian and Vice-versa.
5) (i) If a connected Planner graph G has n vertices, e edges, and r regions then n – e + r = 2.
(ii) If g is connected simple Planner graph with n (= 3) and e edges then e = 3n -6.
6) Define a spanning tree. Give an example. Find the spanning tree for the graph given below.