Kathford
International College of Engineering and Management
Pre Board
Examination
Discrete Structure
B. Sc. CSIT 2nd
Semester
2012
Set A
Full marks: 80
Pass marks: 32 Time: 3 hrs.
Attempt all questions:
Group A (10×2
= 20)
- ”Good students never lies” and “liars are
not a good student”. Are these two statements same?
- Define universal quantification with
suitable examples.
- State which rule of inference is basis of the
following argument: “It is below freezing and raining now, therefore, it
is below freezing now”.
- What
are the contrapositive, the converse, and the inverse of the conditional
statement “If it is raining, then the home team wins”.
- Distinguish between deterministic and
nondeterministic finite state automaton.
- What
do you mean by fallacies?
- Define the complete graph Kn
and determine its chromatic number.
- Show
that
(p
q) and p 
q are logically equivalent. - How many edges are there in a graph with ten
vertices each of degree six?
- What do you mean by proposition, Give example to
justify your answer?
Group
B (5×4
= 20)
11. Prove that “A simple graph is connected if and
only if it has a spanning tree”.
12. For
the set of premises “If I play hockey, then I am sore the next day.” “I use the
whirlpool if I am sore.” “I did not use the whirlpool”. What relevant
conclusion can be drawn? Explain the rules of inference used to draw the
conclusion.
13. Define finite-state with output with suitable examples.
14. Use mathematical induction to prove that the
sum of the first n odd positive integers is n2
15. Prove that a tree with n-vertices has n-1 edges.
Group C (5×8
= 40)
16. Define Euler and Hamiltonian circuits and
paths with examples illustrating the existence and nonexistence of them.
17. Suppose that a person deposits Rs. 10,000/- in a fixed
account at a bank yielding 11% per year with interest compounded annually. How
much will be in the account after 10 years? Solve the problem with modeling it
into recursion relations.
18. Prove
that if n is an integer, then n2 ≥ n , by the help of proofs by
Cases method.
19. Show that the premises “A student in this
class has not read the book”, and “Everyone in this class passed the first
exam” imply the conclusion “Someone who passed the first exam has not read the
book”.
20. Find a maximum flow for the network in the
figure below
Kathford
International College of Engineering and Management
Pre Board
Examination
Discrete Structure
B. Sc. CSIT 2nd
Semester
2012
Set B
Full marks: 80
Pass marks: 32 Time: 3 hrs.
Attempt all questions:
Group A (10×2
= 20)
1. Given propositions p and q, define conjunction and
disjunction of them.
- How do you define logically equivalent propositions?
3. State the Pigeonhole principle
4. Define linear homogeneous recurrence relation.
5. Let
Q(x) be the statement “x<2.” What is the truth value of the quantification 
xQ(x), where the domain consists of all real numbers?
xQ(x), where the domain consists of all real numbers?
6. Define the complete graph Kn on n vertices and the
complete bipartite graph Km,n with suitable examples.
- Draw the binary search tree for the following words: mathematics,
physics, geography, zoology, meteorology, geology, psychology and
chemistry
- Let G be the grammar with vocabulary V ={S,A,a,b},t ={a,b},
starting symbol S and productions P={S→a.A, S→b, A→aa}. What is L(G), the
language of this grammar?
9. Differentate between existential and universal
quantifiers with suitable examples.
10. How do you define logically equivalent propositions?
Group
B (5×4
= 20)
11. Show
that t is a valid conclusion from the premises p→ q, q→ r, r → s, 
s and p
q.
s and p q.
12. Explain the 4 rules of inference for quantified
statements.
13. Prove that an undirected graph is a tree if and only if
there is a unique simple path between any two of its vertices.
14. Solve the recurrence relation
an = 2an-1 + an-2 - 2an-3 for n ³ 3, a0 = 3, a1 = 6
and a2 = 9
15. How many permutations of the letters ABCDEFGH contain the string ABC?
Group C (5×8
= 40)
16. Explain Tautology, contradictions and
contingencies with suitable examples.
17. Discuss the Algorithm of Dijkstra for finding the
shortest path in a weighted graph between two vertices with suitable example.
18. Use
a direct proof method to show that the sum of two odd integers is even.
19. “Everyone
in this discrete mathematics class has taken a course in computer science” and
“Marla is a student in this class”. Convert these English sentences into the
quantified statement.
20. Find a maximum flow for the network in the
figure below.
No comments:
Post a Comment