Discrete Structure TU Board 2078 question paper

Prove that for all integers x and y, if x^2 + y^2 is even then x + y is even. Using induction prove that 1^3 + 2^3 + 3^3 + ………………. + n^3 = n^2(n + 1)^2 / 4

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

1. ∃x P(x)
2. ∀x P(x)
3. ∃x ¬P(x)
4. ∀x ¬P(x)
5. ¬∃x P(x)
6. ¬∀x P(x)

List all the necessary conditions for the graph to be isomorphic with an example. Find the maximal flow from the node SOURCE to SINK in the following network flow.

[figure in the original paper]

What is the coefficient of x^2 in (1 + x)^11? Describe how relation can be represented using matrix.

Solve the recurrence relation a_n = 5a_n-1 – 6a_n-2 with initial conditions a_0 = 1, a_1 = 4.

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

Define preposition. 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 sed for each step.

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.

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

What are the significance of Minimum Spanning Tree? Describe how Kruskal's algorithm can be used to find the MST.

Define zero-one matrix. Explain the types of function.

Represent any three set operations using Venn-diagram. Give a recursive defined function to find the factorial of any given positive integer.