0
$\begingroup$

Background and main question

I am studying algorithm analysis and design, and have been going through "Algorithm Design and Applications" by Goodrich and Tamassia.

One of the applications problems (A-11.2) poses the following:

Given a set, P, of n teams in some sport, a round-robin tournament is a collection of games in which each team plays each other team exactly once. Such round-robin tournaments are often used as the first round for establishing the order of teams (and their seedings) for later single- or double-elimination tournaments. Design an efficient algorithm for constructing a round-robin tournament for a set, P, of n teams assuming n is a power of 2.

The chapter is on the divide-and-conquer method, so I am assuming that they intend for us to use a recursive algorithm to solve the problem.


Approach

I assumed that every team would play in every round (i.e. there is no need for "bye weeks").

I tried to tackle this problem via two different approaches:

1) Place each team in a some sort of collection (or, assign each team an integer, and place those into a collection). Pop the head element from the collection, and make pairs with the elements remaining in the collection. Use these pairs to populate an n - 1 rounds * n - 2 matches grid, where n, as in the problem, is the number of teams. Repeat until one element is left in the collection.

This is not a "true" divide-and-conquer approach, and is O((n-1)!), I believe.

2) Use n - 1, n * n binary matrices to plot the matches for each round.

This approach is not divide-and-conquer at all. I know intuitively that it will work, but I'm not sure how I would implement it programmatically.


Conclusion

How can we solve this problem via the divide-and-conquer approach?

What kind of asymptotic behavior can we expect?

$\endgroup$
1
$\begingroup$

Hint. Divide the teams into two sections. Every game that needs to be played is either between two teams in the same section, or between teams in different sections. What is the set of games that must be played between teams in the same section?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.