Discrete Structure 2066

Attempt all questions:

Group A (10x2=20)

1. Define proposition and its negation with an example.

2. Show that  and  are logically equivalent.

3. State which rule of inference is the basis of the following argument; “It is below freezing now. Therefore, it is either below freezing or raining now.”

4. State the Pigeonhole principle. How many students must be in class to guarantee that at least two students receive the same score on the final exam is graded on a scale from 0 to 100?

5. Let {an} be a sequence that satisfies the recursion relation a_n = a_n-1 - a_n-2 for n≥2 and suppose that a₀ = 3 and a₁=5. Find the values a₂ and a₃.

6. Let G be the grammar with vocabulary V = {S, A, a, b}, t = {a, b}, starting symbol S and production P = {S→ aA, S→ b, A→ aa}. What is L(G), the language of this grammar ?

7. Determine the kleen closures of the sets A = {0}, B = {0, 1}, C = {11}.

8. How many edges are there in graph with 10 vertices each of degree six?

9. Which of the undirected graphs in the following have an Euler path?

10. Determine the chromatic number K_n.

Group B (5x4=20)

11. Differentiate between existential and universal quantifiers with suitable examples.

12. Find the solution of the recursion relation a_n = a_n-1 + 2_an-2 with a₀ = 2 and a₁=7?

OR

Find an explicit formula for the Fibonacci numbers.

13. Define deterministic finite state automata. Construct a DFA whose language is the set of strings that ends with 111 and contains odd number of 1’s.

14. Prove that an undirected graph is a tree if and only if there is a unique simple path between any two of its vertices.

15. Find a spanning tree of the simple graph in the following graph, if it exists.

Can there be more possibilities?

Group C (5x8=40)

16. Discuss the techniques of proofs by contradiction and by cases with suitable examples.

17. Describe linear homogeneous and linear non-homogeneous recurrence relations with suitable examples.

18. Explain non-homogeneous finite automata and language of NFA with suitable example.

19. State and prove the Max-flow and Min-cut theorem.

OR

Find a maximum flow for the network in the figure below.

20. Define Hamiltonian paths and circuits with suitable examples for the existence and nonexistence. Show that has a Hamilton circuit whenever .

OR

Write the shortest path algorithm of Dijkstra for finding the shortest path between two vertices. What is the length of shortest path between a and z in the weighted graph in the following figure?

Apply the stated algorithm for finding the solution.