# 16 Aug, 2021

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

#### 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
Yes
1. 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.
The number of trees in A is more than the number of trees in B.
1. 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.
There is a component of B that contains vertices from two or more components of A.
1. 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.