Difference between revisions of "SKE Algo II (Winter 2019)/Homework 1/Solution"
(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...") |
|||
| Line 3: | Line 3: | ||
Consider the Gale-Shapley's algorithm mentioned in the classroom. | Consider the Gale-Shapley's algorithm mentioned in the classroom. | ||
| − | We define non-stable pairs | + | 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. | Proof that the Gale-Shapley's algorithm would not create any non-stable pairs. | ||
== Solution == | == Solution == | ||
| − | From the definition of non-stable pair, it could be shown that | + | 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 | + | 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 | + | 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 = | = Problem 3 = | ||
Consider the stable marriage problem mentioned in the classroom. | Consider the stable marriage problem mentioned in the classroom. | ||
| − | Given that | + | 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. | Note: Do not proof with Gale-Shapley's algorithm. Use stable matching definition. | ||
==Solution== | ==Solution== | ||
| − | We need to proof that if | + | 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 | + | 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 | + | 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 = | = Problem 4A = | ||
Revision as of 15:54, 5 March 2020
Contents
Problem 2
Consider the Gale-Shapley's algorithm mentioned in the classroom.
We define non-stable pairs Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (b_i, g_j)} such that there exists Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_i} preceeding Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_j} in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_j} 's preference list, and there also exists Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_j} preceeding Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_i} in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_i} precedes Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_j} in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_i} 's preference list, and that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_j} precedes Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_i} in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_j} 's preference list.
For Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i < j} , the Gale-Shapley algorithm would not cause the break-up between the pair Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (b_i, g_i)} , as the break-up will occur only when Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_j} precedes Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_i} in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_i} 's preference order.
For Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i > j} , the Gale-Shapley algorithm would cause the break-up between the pair Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_i, g_j} since the preference of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_j} on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_j} is higher than on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_i} .
Problem 3
Consider the stable marriage problem mentioned in the classroom.
Given that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_i} 's first preferred match is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_i} , and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_j} 's first preferred match is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_j} , proof that the there exists Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} is stable then there exists Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (b_i, g_j)} pair.
We'll consider the proof by contradiction. Suppose our stable pairs Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} contains the matching between Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (b_i, g_x)} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (b_x, g_j} ). As Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_i} prefers Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_j} more than Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_x} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_j} prefers Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_j} more than Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_x} , we could show that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (b_i, g_j)} is a rouge pair in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} , therefore Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} is not stable.
As our conclusion does not agree with our hypothesis, thus we proof by contradiction that if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} is stable, then there exists Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (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">
