11 Aug, 2021

Courses βΈ± Algorithms

You can also access the quiz on Itempool here if you want to practice, or see the notes below for more context.

Lecture Recording

In-class Quiz Questions

πŸ“

We defined a matroid as a family over a fixed finite universe with the following properties:

  1. (Empty set axiom.) .
  2. (Hereditary property.) If and then .
  3. (Exchange axiom.) If and , then there exists an element such that also belongs to .

  1. Let be an arbitrary undirected graph. Let E be the ground set. A subset is independent if the subgraph of is connected. Does this collection of independent sets form a matroid?
    1. Yes, it is a matroid
    2. No, it violates the first axiom (empty set membership)
    3. No, it violates the second axiom (heriditary)
    4. No, it violates the third axiom (exchange property)
    5. Reveal answer
      βœ…

      Violates the second and third axioms.

      For a violation of (c) consider a star. For a violation of (d) consider a graph that has a small star (say five leaves) and a large star (say ten leaves) whose centers are connected by an edge, and let and be the set of edges on the small and large star, respectively.

  2. Consider a ground set that consists of colored elements. Each element has exactly one color. Let a set of elements be independent if no pair of included elements share a color. Is this collection of independent sets a matroid?
    1. Yes, it is a matroid
    2. No, it violates the first axiom (empty set membership)
    3. No, it violates the second axiom (heriditary)
    4. No, it violates the third axiom (exchange property)
    5. Reveal answer
      βœ…

      Yes

      Straightforward to verify the first two axioms. Use the pigeon-hole principle to show the exchange axiom.