This is a Question of the Design and Analysis of Algorithms class, please help Q

Question

This is a Question of the Design and Analysis of Algorithms class, please help

Question 1 (15 marks) You are organizing a soccer match with your friends. Since you have played together many times before, each of you knows how well they play on the same team with everybody else. As a result, each of you may express one of the following two preferences for any other member y of your group: I would rather not play on the same team with y. I really want to play on the same team with y. Note that you may not care whether you play on the same team with y; in that case, you don?t express any preference concerning y. Your goal is to figure out whether there is a way to form two teams so that 1. all preferences of every member of your group are satisfied and 2. there are at least 11 players on each team. Develop an algorithm that answers this question. Your algorithm should run in O(n + m) time, where n is the number of people in your group and m is the number of preferences that were expressed. Argue that the algorithm is correct and that its running time is indeed O(n + m). You may assume that n > or = to 22 because otherwise it is obviously impossible to have at least li players on each team.

Explanation / Answer

Answer:

1: Start

2: Initialize m:=11,n:=22

3: Repeat steps 4 to 6 For player:=1 to n step 1

4: Repeat steps 5,6 For preference:=1 to player step 1

5: IF player plays preference THEN

6: Set count:=count+1

[End If]

[End For 4]

[End For 3]

7: Print count

8: Stop

Explanation:

- Player loop is repeated >=22 times, and each player has his preference of playing. Preference is repeated player no.of times.

- So that time complexity is O(n+m)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.