Question 1 This question is about greedy approaches to problems. One of your fri

Question

Question 1 This question is about greedy approaches to problems. One of your friends, Kishan, is looking to choose some units for their next semester that will let them attend all of their classes. This means they wish to choose units which do not have clashes (where two units have classes with the same start and end time or overlap for some amount of time). Fortunately, each unit's timetable is listed in advance to help students choose their units (see Figure 1) Kishan has asked for your help in choosing units for him to sign up for so that they can choose the most units that result in zero clashes. Note: You may ignore any prerequisites or other restrictions in choosing units for this Problem Note2: You may assume each unit only has a single time for each type of class (eg. One tutorial time rather than the choice of three) MONTUES WED THUR UNIT 9:00 10:00 UNIT 4 4 UNIT UNLE 10:00 - 11:00 UNIT 2 3 11:00 12:00 12:00 13:00Nr G UNITS I 1 UNIT 3 1 1 UNITS 13:00 14:00 Figure 1: example timetable

Explanation / Answer

Part (a)

The principal of greedy can be applied to this by using any one of below algorithms:

Job sequence

Prim's algorithm

Kruskal's algorithm

Because it greedy method he want to cover all the subjects with in 9:00 to 14:00

This is same as knapsak problem as one want to gain more profit in the given space

Solution to problem:

Mon 9:00 to 10:00 unit1

Mon 10:00 to 11:00 unit2

Wed 12:00 to 13:00 unit3

Tues 9:00 to 11:00 unit4

Mon 11:00 to 14:00 unit6

Thus 11:00 to 14:00 unit5

(B).

Brute force is an algorithm which is used to check all possible solutions in problem which is countable steps.

For the above problem we can apply brute force by checking each and e every module step by step an pick the optimum one

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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