Discrete Structure 2068

Attempt all questions:

Group A (10x2=20)

1. Define disjunction and conjunction with suitable examples.

2. Is the following argument valid?

Smoking is healthy.

If smoking is healthy, then cigarettes are prescribed by physicians.

∴Cigarettes are prescribed by physicians

3. State the rules for the strong form of mathematical induction with propositions.

4. State and prove “the extended pigeonhole principle”.

5. Define the terms a language over a vocabulary and the phrase – structure grammar.

6. Distinguish between binary tree and spanning tree with suitable examples.

7. Consider K_n, the complete graph on n vertices. What is the degree of each vertex?

8. Explain the static transition function of the finite state machine with a suitable table.

9. Define regular expression over a non-empty set A.

10. What is the chromatic number of the complete bipartite graph, where m and n are positive integers?

Group B (5x4=20)

11. Explain the rules of inference for quantified statements.

12. Let A = {p, q, r}. Give the regular set corresponding to the regular expression given:

a) (p v q ) ┌  q*    b) p( q q )* r.

13. Find an explicit formula for the Fibonacci sequence defined by

f_n = f_n−1 + f_n−2 ,  f₁ = f₂ = 1

14. Define finite – state machines with output.

15. Show that the maximum number of vertices in a binary tree of height n is 2ⁿ⁺¹ − 1.

OR

Draw all possible unordered trees on the set {a, b, c}.

Group C (5x8=40)

16. Construct the transition table of the finite – state machine whose diagraph is shown?

17.  Let G = ( V, S, v₀, |→), where V = { v₀, x, y, z}, S = {x, y, z } and

|→ : v₀ |→ xv₀

v₀ |→ yv₀

v₀ |→ z

What is L(G), the language of this grammar?

18. Find a maximum flow in the network shown in figure

19. Prove that a symmetric connected relation has a undirected spanning tree.

OR

Give a simple condition on the weights of a graph that will guarantee that there is a unique maximal spanning tree for the graph.

20. Use Fleury’s algorithm to construct an Euler circuit for the following graph.

OR

Explain the concept of network flows and max-flow min- cut with suitable examples.