Download DU (University of Delhi) B-Tech 3rd Semester 1568 Discrete Structures Question Paper

FirstRanker.com

This question paper contains 4+1 printed pages

Roll No.

--- Content provided by FirstRanker.com ---

S. No. of Question Paper : 1568

Unique Paper Code : 2341303

Name of the Paper : Discrete Structures

Name of the Course : B.Tech. in Computer Science

Semester : III

--- Content provided by FirstRanker.com ---

Duration : 3 Hours Maximum Marks : 75

(Write your Roll No. on the top immediately on receipt of this question paper.)

Section A is compulsory.

Do any four questions from Section B.

Section A

--- Content provided by FirstRanker.com ---

1. (a) A collection of 10 electric bulbs contains 3 defective ones :
   1. In how many ways can a sample of four bulbs be selected ?
   2. In how many ways can a sample of four bulbs be selected which contains two good bulbs and 2 defective ones ? 1+2
2. (b) Suppose f1(x) is O(g1(x)) and f2(x) is O(g2(x)) then show that (f1(x) + f2(x) is O(max(g1(x), g2(x))). 3
3. (c) Evaluate the sum : S 3

   ∑ 2^k

   --- Content provided by FirstRanker.com ---

   k=1

4. (d) Show that : p→(q→r) and (p∨r) are logically equivalent. 2
5. (e) Determine the discrete numeric function of the generating function : A(Z) = Z²/(4 - 4Z + Z²). 4
6. (f) Prove that every bipartite graph is 2-colorable. 2

--- Content provided by FirstRanker.com ---

7. (g) Using master theorem, find the solution to the recurrence : T(n) = 4T(n/2) + n². 3
8. (h) Consider a set A = {2, 7, 14, 28, 56, 84} and the relation a ≤ b if and only if a divides b. Give the Hasse diagram for the Partial order-set (A, ≤). 3
9. (i) How many edges are there in an undirected graph with two vertices of degree 4, four vertices of degree 5, and four vertices of degree 6 ? 2
10. (j) Show that a full m-ary balanced tree of height 4 has more than m³ leaves. 3
11. (k) Let |A| = n and |B| = m where m > n. Give the number of one-to-one functions, f:A→B that can be defined? 2

--- Content provided by FirstRanker.com ---

12. (l) Show that for a graph to be planar it should at least one vertex of degree 5 or less. 3
13. (m) Write the contrapositive and inverse of the following statements : 2

    If you try hard, then you will win.

Section B

2. (a) Find the number of integers between 1 and 250 that are divisible by any of the integers 2, 3, 5 and 7. 4

--- Content provided by FirstRanker.com ---

3. (b) Let X = {1, 2, 3, 4, 5, 6}, and define a relation R on X as R = {(1, 2), (2, 1), (2, 3), (3, 4), (4, 5), (5, 6)}. Find the reflexive and transitive closure of R. 3
4. (c) Prove that n³ — n is divisible by 3 for any integer n > 0. 3

3. (a) Let ‘@’ be a numeric function such that :
   1. V a_n = a_n-1 + a_n-2
   2. Determine a_n

--- Content provided by FirstRanker.com ---

4. (b) Find the total solution of the recurrence relation : a_n + 4a_n-1 = 7, where a₀ = 3. 3
5. (c) How many students must be in a class to guarantee that at least two students receive the same score on the final exam, if the exam is graded on a scale from 0 to 100 points ? 2

4. (a) Draw the graph K₅ and answer the following questions : 4
   1. What is the degree of each vertex ?
   2. Is K₅ planar ?

--- Content provided by FirstRanker.com ---

5. (b) A connected planar graph G has 10 vertices each of degree 3. Into how many regions does a representation of this planar graph split the plane ? 4
6. (c) How many leaves does a regular (full) 3-ary tree with 100 vertices have ? 2

5. (a) Draw graphs each having six vertices such that :
   1. Graph is Hamiltonian but not Eulerian
   2. Graph is Eulerian but not Hamiltonian.

--- Content provided by FirstRanker.com ---

6. (b) Show that the sum of degree of all vertices in G is twice the number of edges in G. 3
7. (c) What is the condition for K_n to have an Euler path or circuit ? Justify your answer. 3

6. (a) Use the insertion sort algorithm to sort the list 2, 14, 9, 18, 12. 4
7. (b) Determine whether each of the functions 2ⁿ and n² is O(n!). 4
8. (c) Using substitution method, prove that T(n) is O (n lg n) given that : T(n) = 2T(n/2) + n. 3

--- Content provided by FirstRanker.com ---

7. (a) Show that (p → q) ∧ (r → q) ≡ (p ∨ r) → q are logically equivalent using the laws of logical equivalences. 4
8. (b) Show that : (p∧q)→(p∨q) is a tautology with the help of truth table. 2
9. (c) Show that the premises “It is not sunny this afternoon and it is colder than yesterday;” “We will go swimming only if it sunny;” “If we do not go swimming, then we will take a canoe trip”; and “If we take a canoe trip, then we will be home by sunset” lead to the conclusion—*“We will be home by sunset”. 4

FirstRanker.com

--- Content provided by FirstRanker.com ---