Practice Big Hammers In Algorithms (11.1.2) - Reductions - Design & Analysis of Algorithms - Vol 3

Practice: Big Hammers in Algorithms

Lesson 11.1.2Reductions

Practise this section

9 questions

Flashcard drill
4 cards from this section. Quick, good the night before a test.
Exercise
6 questions · about 4 min · pass mark 70%. Hints available.
Sign up to start the exercise
Quiz
3 questions · about 2 min · pass mark 70%. Hints available.
Sign up to start the quiz

6 sample questions

Question 1.
What is a bipartite graph?
Show hintHide hint
Think about how teachers and courses can connect.
Question 2.
What does the term 'matching' refer to in the context of bipartite graphs?
Show hintHide hint
Consider the connection between teachers and subjects.
3Question 3.
What is bipartite matching?
- A matching that includes any network structure.
- A special allocation where connections only exist between two distinct sets.
- A random assignment of courses to any teacher.
Show hintHide hint
Consider how teachers and courses are organized.
4Question 4.
True or False: In a bipartite matching, a teacher can teach multiple courses.
- True
- False
Show hintHide hint
Think about the constraints of the matching problem.
Question 5.
Given a set of 5 teachers and only 4 courses, devise a method to allocate courses while ensuring no teacher teaches more than one course and explain your reasoning.
Show hintHide hint
Use the concept of capacities to frame your solution.
Question 6.
If a specific teacher wishes to teach two courses and refuses to pick, how would this affect your bipartite graph and flow algorithm?
Show hintHide hint
Consider how stubborn choices can limit overall network flow.

5 more questions in this section. Enroll free to practise them all.