Scribd Logo
Upload

Welcome to Scribd!

  • 7 views

    Discrete Mathematics-3-12-18

    Uploaded by

    Deepali Rajguru

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Discrete Mathematics-3-12-18

    Uploaded by

    Deepali Rajguru
    7 views2 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    7 views2 pages

    Discrete Mathematics-3-12-18

    Uploaded by

    Deepali Rajguru

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 2

    DR.

    BABASAHEB AMBEDKAR TECHNOLOGICAL UNIVERSITY,


    LONERE
    End Semester Examination - Winter 201g
    Course: B. Tech in Computer Science and Engg
    Sem: III
    Subject Name: Discrete Mathematics
    Subject Code: BTCOC3O2
    Date:0311212018 Max Marks: 60 Duration: 3 Hrs.
    fnstructions to the Students:
    1. Solve ANY FIW questions out of thefollowing.
    2. Use of non-programmable scientific calculatori is allowed.
    3. Assume suitable data wherever

    Marks
    Q. I Solve Any Three of the following.

    A) Let p and q be the propositions "swimming at the New Jersey shore is allowed,,
    and 4M
    "sharks have been spotted near the shore,,respectively. Express each ofthese
    compound propositions as an English sentence.
    a) -q b)p*-q c)p*-q d) -pvq
    B) Explain with example, notations used and mathematical expression to describe
    following terms.
    the 4M
    i) Membership ii) Subset iii) Equality of two sets iv) Union
    c) Use mathematical induction to show that l+5+9+...+(4n-3): n(2n-l), vn > l,neZ 4M
    D) Explain Universal quantifiers and Existential quantifiers with example. what
    is De 4M
    Morgan's law for quantifiers?

    Q.2 Solve the following.


    A) Check whether the relation R defined in the set
    {1,2,3,4, 5, 6} is 6M
    : :
    R { (a, b) : b a+1 } is reflexive, symmetric or transitive. Justify your answer.
    Find
    the relation Matrix.
    B) Explain surjective, injective, bijective and inverse function each with example.
    6M

    Q. 3 Solve Any three of the following.

    A) Explain the pigeonhole principle with example.


    4NI
    B) Find how many symbol codes can be formed if the first two symbols are letters and the
    4M
    next three are digits but no symbol is repeated?
    C) What is the expansion of (3x + y) n?
    4M
    D) Determine the sequence { a"} where an = 3n for every non-negative integer, n is a
    4M
    solution of the recurrence relation an=2a nj- d n_2for n = 2,3,4, ...
    Q.4 Solve the following.

    A) Define Euler graph and Hamiltonian Graph.


    6M
    i)For a given graph G :
    (a) Find a Hamiltonian path that begins ar A and ends at E.
    (b) Find a Hamiltonian circuit that starts at A and ends with the pair of vertices E,
    A.
    (c) Find a Hamiltonian path that begins at F and ends at G.
    ii) For a given graph I find Eulerian path and Eulerian cycle.

    44527 06 Ar 5C42C8064E A682DAF03 B I 9F


    Graph: H Graph: I

    B) Find the shortest path in the given graph using Dijkstra shortest path algorithm. 6M

    (f,
    Slt '--
    {''
    ,5

    .r'"
    L-
    l
    1:\
    ; .
    r,1u
    (.1)- .

    Q.5 Solve Any three of the following.

    A) Show that a tree with n vertices has n-l edges. 4M


    B) Find minimum spanning tree for the given graph using prim,s algorithm? 4NT

    C) Define the following terms with reference to tree with example. 4M


    i)Level and Height of a tree ii)M-ary Tree iii) Eccentricity of a vertex
    D) Construct the rninimum spanning tree (MST) for the given graph using Kruskal,s 4M
    Algorithm.

    6
    Q. Solve the following.
    A) Define the following terms. 6M
    i)Algebraic Structures ii) Semi Groups iii) Monoids iv) Ring
    v) Field vi) Group
    B) For each of the following, determine whether the binary operation * is commutative or 6M
    associative?

    i) Nisthesetof naturalnumbersanda* b=a*b+2 fora, b GN


    ii) On N where a * b: min(4 b+2)
    iii) OnRwherea*b:ab
    :k*,k *:k:k
    End

    44s27 06 At 5C42C8064E A,682DAF03B I 9F

    You might also like