Scribd Logo
Upload

Welcome to Scribd!

  • 31 views

    Assignment 1 DS

    Uploaded by

    Usman Asif
    This document provides the details of Assignment 1 for the Discrete Structures course due on March 20, 2020. It includes 10 problems covering the topics of counting, sets, and graphs. The counting problems involve finding the number of combinations in various scenarios. The set problems involve listing subsets, finding unions and intersections, and proving set identities using Venn diagrams. The graph problems involve representing friendship relations and chemical/maze connections using arrays and graphs.

    Copyright:

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

    Assignment 1 DS

    Uploaded by

    Usman Asif
    31 views2 pages
    This document provides the details of Assignment 1 for the Discrete Structures course due on March 20, 2020. It includes 10 problems covering the topics of counting, sets, and graphs. The counting problems involve finding the number of combinations in various scenarios. The set problems involve listing subsets, finding unions and intersections, and proving set identities using Venn diagrams. The graph problems involve representing friendship relations and chemical/maze connections using arrays and graphs.

    Original Description:

    DS Assignment 03

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document provides the details of Assignment 1 for the Discrete Structures course due on March 20, 2020. It includes 10 problems covering the topics of counting, sets, and graphs. The counting problems involve finding the number of combinations in various scenarios. The set problems involve listing subsets, finding unions and intersections, and proving set identities using Venn diagrams. The graph problems involve representing friendship relations and chemical/maze connections using arrays and graphs.

    Copyright:

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

    Assignment 1 DS

    Uploaded by

    Usman Asif
    This document provides the details of Assignment 1 for the Discrete Structures course due on March 20, 2020. It includes 10 problems covering the topics of counting, sets, and graphs. The counting problems involve finding the number of combinations in various scenarios. The set problems involve listing subsets, finding unions and intersections, and proving set identities using Venn diagrams. The graph problems involve representing friendship relations and chemical/maze connections using arrays and graphs.

    Copyright:

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

    Discrete Structures – Spring-2020 Assignment-01 Due Date: 20 March 2020

    Counting
    Problem 1
    From section 1.1 of the given reading, what is the number of pairings (in all the various senses as discussed) in a
    party of 10?
    a. Handshakes b. Seating arrangements c. Playing chess (with 5 chess-boards)
    Problem 2
    (a) How many words of 10 letters can you form, using the English alphabet? (there are 26 different letters, of which
    5 are vowels).
    (b) How many words of length 10 can you form, where no letter is repeated?
    (c) How many words of length 8 can you form, where the first letter is the same as the last letter?
    (d) How many words of length 8 can you form, which contain exactly one vowel?
    Problem 3
    In how many ways can a photographer at a wedding arrange six people in a row, including the bride and groom, if
    a) the bride must be next to the groom?
    b) the bride is not next to the groom?
    c) the bride is positioned somewhere to the left of the groom?

    Sets
    Problem 4
    a. List all subsets of {0, 1, 3}. How many do you get?
    b. List all subsets of {𝑎, 𝑏, 𝑐, 𝑑, 𝑒}, containing 𝑎 but not containing 𝑏.
    c. Define a set of which both {1, 3, 4} and {0, 3, 5} are subsets. Find such a set with the smallest possible number
    of elements.
    d. What is the number of subsets of a set with n elements?
    e. What is the number of subsets of a set with n elements, containing a given element (when element becomes
    fixed, part of every subset)?
    Problem 5
    a. We form the union of a set with 5 elements and a set with 9 elements. Which of the following numbers can
    we get as the cardinality of the union: 4, 6, 9, 10, 14, 20?
    b. We form the union of two sets. We know that one of them has n elements and the other has m elements. What
    can we infer about the cardinality of their union?
    c. What is the intersection of
    i) the sets {0, 1, 3} and {1, 2, 3};
    ii) the set of girls in this class and the set of boys in this class;
    iii) the set of prime numbers and the set of even numbers?
    d. We form the intersection of two sets. We know that one of them has n elements and the other has m elements.
    What can we infer about the cardinality of their intersection?
    Problem 6
    Use Venn-diagram to prove following:
    a. Prove equations (1.2), (1.3), and (1.4) given in the reading pages.
    b. Prove that |𝐴 ∪ 𝐵| + |𝐴 ∩ 𝐵| = |𝐴| + |𝐵|.
    Problem 7
    a. What is the symmetric difference of the set ℤ+ of nonnegative integers and the set 𝔼 of even integers (𝔼 =
    {. . . , −4, −2, 0, 2, 4, . . . } contains both negative and positive even integers).
    b. Let 𝐶 be the symmetric difference of 𝐴 and 𝐵 ( that is 𝐴Δ𝐵 = 𝐶). Now, form the symmetric difference of A
    and C. What did you get? Give a proof of the answer using Venn diagram.

    Graphs
    Problem 8
    A friendship graph is given below.
    a. Make a 5 × 5 array to show who is friend of whom.
    (All rows are labelled A, B, C, D, E, and all columns are labelled A, B, C, D, E. Mark the corresponding
    entry if they are friends, and cross if they are not).
    b. Represent the friendship relation as sets (e.g. 𝐴 = {𝐸, 𝐵, 𝐶, 𝐷}, all friends of A. Similarly do for others).
    Discrete Structures – Spring-2020 Assignment-01 Due Date: 20 March 2020

    Problem 9
    a. Draw graph of the following chemical bonds:

    b. Draw graph of the following maze. You make an edge whenever one labelled corridor is connected to another
    one.

    Problem 10

    You might also like