11.1.4. Reduction Process

Try these first

1. 1.

   Define what a reduction is in algorithm design.

   Hint

   Consider how one problem's solution could assist another.

2. 2.

   What is a bipartite graph?

   Hint

   Think about the structure and where edges connect.

3. 3.

   What is a bipartite graph?

   • A graph with one set of vertices
   • A graph with two disjoint sets of vertices
   • A graph with cycles

   Hint

   Focus on how vertices are organized.

4. 4.

   True or False: A perfect matching means one vertex can be matched to multiple vertices.

   • True
   • False

   Hint

   Think about the definition of matching.

5. 5.

   Given a scenario with 6 teachers and 4 courses, how would you approach solving for an allocation using network flows? Describe your steps.

   Hint

   Visualize the connections and think about how the flow behaves in your network.

6. 6.

   Discuss how a mismatch in the number of teachers and courses affects the matching process. What strategies could work around this?

   Hint

   Consider the implications of surplus vs shortage in an allocation context.