Scribd Logo
Upload

Welcome to Scribd!

  • 161 views

    DSA - IT PYQ - 2024 MAY TO 2019 DEC - Aeraxia - in

    Uploaded by

    milindnagare13
    Dsa it pyq may to 2019 dec aeraxia.in

    Copyright:

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

    DSA - IT PYQ - 2024 MAY TO 2019 DEC - Aeraxia - in

    Uploaded by

    milindnagare13
    161 views10 pages
    Dsa it pyq may to 2019 dec aeraxia.in

    Original Title

    DSA - IT PYQ - 2024 MAY TO 2019 DEC - Aeraxia.in

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Dsa it pyq may to 2019 dec aeraxia.in

    Copyright:

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

    DSA - IT PYQ - 2024 MAY TO 2019 DEC - Aeraxia - in

    Uploaded by

    milindnagare13
    Dsa it pyq may to 2019 dec aeraxia.in

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 10

    Paper / Subject Code: 50922 / Discrete Structures & Graph Theory

    Duration: 3 Hours Total Marks: 80


    N.B. : 1) Question Number 1 is compulsory
    2) Solve any three questions from the remaining questions
    3) Make suitable assumptions if needed
    4) Assume appropriate data whenever required. State all assumptions
    clearly.

    Q.1 Solve any four of the following questions.


    a. What is a tautology? Check whether the following logical expression is 5
    tautology?
    [(p→r) ^ (~q→p) ^ ~r ] → q
    b. State the Pigeonhole principle and show that if any five numbers form 1 to 5
    8 are chosen, then two of them will add to 9.

    c. Convert the following into CNF form. 5


    (A→B) → ((B→C) →(A→C))
    d Given S = {1, 2, ..., 10} and a relation R on S, where R = {(x, y)| x + y = 10}. 5
    Is it reflexive, symmetric, transitive, antisymmetric?
    e Define the following terms 5
    1. Planer graph 2. Cut Vertex 3.Chain 4. Monoid 5.Group
    Q.2 a Let A= {p,q,r,s} and let R={(p,p),(p,q),(p,r),(q,p),(q,q),(r,p),(q,r),(r,q),(r,r),(s,s) 8
    }. Show that R is an equivalence relation . Determine the equivalence classes
    and find the rank of R.
    b. Show that A={0,3,6,9,12} is a ring w.r.t. the operation of addition & 8
    multiplication modulo 15.
    c Explain two different types of Quantifiers with example? 4
    Represent the following sentences using First Order logic
    i) Some students took GenAI.
    ii)Every student who takes GenAI passes it.
    Q.3 a What is an Abelian Group? Let G = { 1,2,3,4,5,6,7} 8
    i) Prepare the composition table w.r.t the operation of multiplication modulo
    8.
    ii) Check whether it is an Abelian group? Justify your answer.
    b Define minimum hamming distance. Find the code words generated by the 8
    parity check matrix H given below.
    101
    H= 011
    110
    100
    010
    00 1

    56489 Page 1 of 3

    X237Y21B858X237Y21B858X237Y21B858X237Y21B858
    Paper / Subject Code: 50922 / Discrete Structures & Graph Theory

    c 4
    Determine whether the following graph is Eulerian or Hamiltonian or both.
    Justify your answer.

    Q.4 a Define function. What are three different types of functions.. Consider the 8
    function f and g from N x N to N given by f(x,y) = 2x+y and g(x,y)= xy
    ,identify its type.
    b Let A= {a,b,c,d,e} and let R be a relation on A. 8
    Let R={(a,a),(a,c),(b,b),(c,d),(c,e),(d,a),(e,b),(e,e)
    Compute transitive closure using Warshall’s algorithm
    c Prove using Mathematical Induction that sum of cubes of three consecutive 4
    integers is divisible by 9.

    Q.5 a Let X={1,2,3,4,6,24,36,72} and R ={(x,y) ∈ R | x divides y} 8


    i) Write the pairs in a relation set R.
    ii) Construct Hasse diagram.
    iii) Mention Chains and Anti Chains from above set.
    iv) Is it a lattice?

    b Find the number of integers between 1 to 500 that are not divisible by 5,6, or 8? 8

    c Check whether the following graphs are Isomorphic or not? Justify 4

    56489 Page 2 of 3

    X237Y21B858X237Y21B858X237Y21B858X237Y21B858
    Paper / Subject Code: 50922 / Discrete Structures & Graph Theory

    Q.6. a Draw the Hasse Diagram of D72 8


    i)Find the complement of each element
    ii) Check whether it is a Distributive Lattice
    b Let f(x) = x + 3, g(x) = x − 3 and h(x) = 3x for x ∈ R, where R is the set of real 8
    numbers.
    Find i)g ◦ h ii) f ◦ g. i)g ◦ h ◦ f ii) f ◦ h ◦ g
    c Find the generating functions for the following sequences: 4
    a. 0, 0, 0, 1, 2, 3, 4, 5, 6, 7,…………………………
    b. 6, -6, 6, -6, 6, -6,…………………………………….

    ____________________

    56489 Page 3 of 3

    X237Y21B858X237Y21B858X237Y21B858X237Y21B858

    You might also like