Discrete Structures 2078
Group A
Long answer questions:
Attempt any Two questions:
1. Prove that for all integers x and y, if x2+y2 is even then x+y is even. Using induction prove that 13+23+..........+n3 = n2(n+1)2/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 x7 in (1+x)11? Describe how relation can be represented using matrix. [2+3]
5. Solve the recurrence relation an = 5nn-1 - 6nn-2 with initial conditions a0 =1, a1 = 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]