SKE Algo II (Winter 2019)/Homework 1/Solution - Revision history

Srakrn: /* Problem 5 */

2020-03-05T08:56:02Z

Problem 5

Srakrn at 08:54, 5 March 2020

2020-03-05T08:54:38Z

Srakrn: Created page with "= 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\) i..."

2020-03-05T08:53:27Z

Created page with "= 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\) i..."

New page

= 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">

@@ Line 55: / Line 55: @@
 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">
+[[File:Algoii-hw1-failedschedule-c.png|thumb|center]]
 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.
@@ Line 61: / Line 61: @@
 == 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">
+This is one of the failing case:

@@ Line 3: / Line 3: @@
 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.
+We define non-stable pairs <math>(b_i, g_j)</math> such that there exists <math>g_i</math> preceeding <math>g_j</math> in <math>b_j</math>'s preference list, and there also exists <math>b_j</math> preceeding <math>b_i</math> in <math>g_j</math>'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.
+From the definition of non-stable pair, it could be shown that <math>g_i</math> precedes <math>g_j</math> in <math>b_i</math>'s preference list, and that <math>b_j</math> precedes <math>b_i</math> in <math>g_j</math>'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 <math>i < j</math>, the Gale-Shapley algorithm would not cause the break-up between the pair <math>(b_i, g_i)</math>, as the break-up will occur only when <math>g_j</math> precedes <math>g_i</math> in <math>b_i</math>'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\).
+For <math>i > j</math>, the Gale-Shapley algorithm would cause the break-up between the pair <math>b_i, g_j</math> since the preference of <math>g_j</math> on <math>b_j</math> is higher than on <math>b_i</math>.
 = 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.
+Given that <math>b_i</math>'s first preferred match is <math>g_i</math>, and <math>g_j</math>'s first preferred match is <math>b_j</math>, proof that the there exists <math>(b_i, g_j)</math> 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 need to proof that if <math>M</math> is stable then there exists <math>(b_i, g_j)</math> 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.
+We'll consider the proof by contradiction. Suppose our stable pairs <math>M</math> contains the matching between <math>(b_i, g_x)</math> and <math>(b_x, g_j</math>). As <math>b_i</math> prefers <math>g_j</math> more than <math>g_x</math> and <math>g_j</math> prefers <math>b_j</math> more than <math>g_x</math>, we could show that <math>(b_i, g_j)</math> is a rouge pair in <math>M</math>, therefore <math>M</math> 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.
+As our conclusion does not agree with our hypothesis, thus we proof by contradiction that if <math>M</math> is stable, then there exists <math>(b_i, g_j)</math> pair.
 = Problem 4A =