16 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 went over the generic matroid optimization algorithm (sort the elements of universe in non-increasing order of weight, and keep picking all elements in the solution skipping over those whose inclusion violates independence) and argued why it is correct. We also learned why the graphic matroid for a graph , where the universe is and the family consists of all acyclic subsets of edges.

  1. Let be an undirected and connected graph. Let be the ground set. A subset is independent if the subgraph induced by is acyclic. Does the set of highlighted (i.e, solid) edges in the graph below (c.f. Figure 1) form an independent set?
    1. Yes
    2. No
    3. Figure 1.
      Figure 1.
      Reveal answer
      βœ…

      Yes

  2. If A and B are subsets of E(G) that both induce forests on V(G), and |B| > |A|, then which of the following is true?
    1. The number of trees in A is more than the number of trees in B.
    2. The number of trees in B is more than the number of trees in A.
    3. Neither of these statements may be consistently true.
    4. Reveal answer
      βœ…

      The number of trees in A is more than the number of trees in B.

  3. If A and B are subsets of E(G) that both induce forests on V(G), and |B| > |A|, then which of the following is true? Recall that we already know from the previous question that the number of trees in A is more than the number of trees in B. (Hint: Apply the pigeon-hole principle.)
    1. There is a component of A that contains vertices from two or more components of B.
    2. There is a component of B that contains vertices from two or more components of A.
    3. Neither of these statements may be consistently true.
    4. Reveal answer
      βœ…

      There is a component of B that contains vertices from two or more components of A.

  4. If A and B are subsets of E(G) that both induce forests on V(G), and |B| > |A|, then which of the following is true?
    1. There is an edge in A\B that can be safely added to B without forming a cycle in the forest B.
    2. There is an edge in B\A that can be safely added to A without forming a cycle in the forest A.
    3. Neither of these statements may be consistently true.
    4. Reveal answer
      βœ…

      There is an edge in B\A that can be safely added to A without forming a cycle in the forest A.

  5. Let G = (V, E) be an arbitrary undirected graph. Let E be the ground set, and let F be the family of all subsets of E that form a forest (i.e, induce an acyclic subgraph). Does this family form a matroid?
    1. Yes
    2. No, it violates the first axiom (empty set membership)
    3. No, it violates the second axiom (heredity)
    4. No, it violates the third axiom (exchange axiom)
    5. Reveal answer
      βœ…

      Yes