### Exam Year

Tribhuvan University

Institute of Science and Technology

2078

Bachelor Level / second-semester / Science

Computer Science and Information Technology( CSC160 )

Discrete Structure

Full Marks: 60 + 20 + 20

Pass Marks: 24 + 8 + 8

Time: 3 Hours

Candidates are required to give their answers in their own words as far as practicable.

The figures in the margin indicate full marks.

Group A

Attempts 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 + 33 + ………………. + n3 = n2(n + 1)2 / 4

2

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)
3

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. Group B

Attempts any EIGHT questions

4

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

5

Solve the recurrence relation an = 5an-1 – 6an-2 with initial conditions a0 = 1, a1 = 4.

6

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

7

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.

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.

9

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

10

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

11

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

12

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