SKE Algo II (Winter 2019)/Homework 1/Solution

Problem 2

Consider the Gale-Shapley's algorithm mentioned in the classroom.

We define non-stable pairs \((b_i, g_j)\) such that there exists \(g_i\) preceeding \(g_j\) in \(b_j\)'s preference list, and there also exists \(b_j\) preceeding \(b_i\) in \(g_j\)'s preference list.

Proof that the Gale-Shapley's algorithm would not create any non-stable pairs.

Solution

From the definition of non-stable pair, it could be shown that \(g_i\) precedes \(g_j\) in \(b_i\)'s preference list, and that \(b_j\) precedes \(b_i\) in \(g_j\)'s preference list.

For \(i < j\), the Gale-Shapley algorithm would not cause the break-up between the pair \((b_i, g_i)\), as the break-up will occur only when \(g_j\) precedes \(g_i\) in \(b_i\)'s preference order.

For \(i > j\), the Gale-Shapley algorithm would cause the break-up between the pair \(b_i, g_j\) since the preference of \(g_j\) on \(b_j\) is higher than on \(b_i\).

Problem 3

Consider the stable marriage problem mentioned in the classroom.

Given that \(b_i\)'s first preferred match is \(g_i\), and \(g_j\)'s first preferred match is \(b_j\), proof that the there exists \((b_i, g_j)\) pair in any stable matchings.

Note: Do not proof with Gale-Shapley's algorithm. Use stable matching definition.

Solution

We need to proof that if \(M\) is stable then there exists \((b_i, g_j)\) pair.

We'll consider the proof by contradiction. Suppose our stable pairs \(M\) contains the matching between \((b_i, g_x)\) and \((b_x, g_j\)). As \(b_i\) prefers \(g_j\) more than \(g_x\) and \(g_j\) prefers \(b_j\) more than \(g_x\), we could show that \((b_i, g_j)\) is a rouge pair in \(M\), therefore \(M\) is not stable.

As our conclusion does not agree with our hypothesis, thus we proof by contradiction that if \(M\) is stable, then there exists \((b_i, g_j)\) pair.

Problem 4A

Given this weighted scheduling algorithm, give an counterexample on why it fails:

Given the schedule (which is the list of events to attend), greedily attend the event that begins first.

Example: If there are four event at (1) 9:00 - 10:00, (2) 10:00 - 12:00, (3) 11:00 - 12:00, and (4) 13:00 - 14:00, this algorithm will attend event number 1, 2, and 4.

Solution

Let there be three event at (a) 8:00 - 16:00, (b) 9:00 - 10:00, and (c) 11:00 - 12:00, this algorithm will fail since it will attend only event (a).

Problem 4B

Given this weighted scheduling algorithm, give an counterexample on why it fails:

Given the schedule (which is the list of events to attend), greedily attend the event that is the shortest in time.

Example: If there are four event at (1) 9:00 - 10:00, (2) 10:00 - 12:00, (3) 11:00 - 12:00, and (4) 13:00 - 14:00, this algorithm will attend event number 1, 3, and 4.

Solution

Let there be three event at (a) 8:00 - 10:00, (b) 9:00 - 10:00, and (c) 10:00 - 12:00, this algorithm will fail since it will attend only event (b).

Problem 5

Given this weighted scheduling algorithm, give an counterexample on why it fails:

Given the schedule (which is the list of events to attend), greedily attend the event that is least overlapped.

Example: Given the list of events A to F as follows:

<img src="https://edufarm.ku.ac.th/draftfile.php/52661/user/draft/512860086/algoii-hw1-failedschedule-c.png" alt="" role="presentation" class="img-responsive atto_image_button_text-bottom" width="1920" height="502">

The algorithm will choose event A and C first as each of them has only 1 overlapping event, then it will choose event D and E as each of them has 2 overlaping events. No more events can be chosen, so the algorithm returns [A, C, D, E] as the scheduling problem's solution.

Solution

<img src="https://edufarm.ku.ac.th/draftfile.php/52661/user/draft/43300127/algoii-hw1-failedschedule-c-soln.png" alt="" role="presentation" class="img-responsive atto_image_button_text-bottom" width="1920" height="518">