Discrete Structures 2078

Group A

Long answer questions:

Attempt any Two questions:

1. Prove that for all integers x and y, if x²+y² is even then x+y is even. Using induction prove that 1³+2³+..........+n³ = n²(n+1)²/4.    [5+5]

2. State division and remainder algorithm. Suppose that the domain of the propositional function P(x) consists of the integers 0, 1, 2, 3 and 4. Write out each of following propositions using disjunctions, conjunctions and negations.        [4+6]

    a. ∃x P(x)

    b. ∀x P(x)

    c. ∃x ¬P(x)

    d. ∀x ¬P(x)

    e. ¬∃x P(x)

    f. ¬∀x P(x)

3. List the necessary conditions for the graphs to be isomorphic with an example. Find the maximal flow from the node SOURCE to SINL in the following network flow.        [5+5]

Group B

Short answer questions:

Attempt any Eight questions:

4. What is the coefficient of x⁷ in (1+x)¹¹? Describe how relation can be represented using matrix.    [2+3]

5. Solve the recurrence relation a_n = 5n_n-1 - 6n_n-2 with initial conditions a₀ =1, a₁ = 4.                [5]

6. Prove that if n is positive integer, then n is odd if and only if 5n+6 is odd.            [5]

7. Define proposition. Consider the argument "John, a student in this class knows how to write program in C. Everyone who knows how to write program in C can get a high paying job. Therefore, someone in this class can get high paying job." Now, explain which rules of inferences are used for each step.        [1+4]

8. Show that if there are 30 students in a class, then at least two have same names that begin with the same letter. Explain the Pascal's triangle.        [2.5+2.5]

9. Illustrate the Dijkstra's Algorithm to find the shortest path from source node to destination node with an example.        [5]

10. What are the significances of Minimal Spanning Tree? Describe how Kruskal's algorithm can be used to find the MST.        [2+3]

11. Define zero-one matrix. Explain the types of function.        [1+4]

12.  Represent any three set operations using Venn diagram. Give a recursive defined function to find the factorial of any given positive integer.        [3+2]