<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>Lab1/notes.md - +/EE360C @ master</title>
<meta name="description" content="Lab1/notes.md in +/EE360C at master.">
<meta property="og:title" content="Lab1/notes.md - +/EE360C @ master">
<meta property="og:description" content="Lab1/notes.md in +/EE360C at master.">
<meta property="og:type" content="website">
<meta property="og:site_name" content="git.julia.blue">
<link rel="stylesheet" href="/css/style.css?v=62">
<script type="module" src="/js/main.js?v=62"></script>
</head>
<body>
<main data-ref="master" data-tip="01622e7c18c228502223417191c50745856674c3">
<noscript>
  <div class="callout">
    <p>
      hey! this is a static git repo viewer. commit diffs, file history,
      older commits and other revisions won't load without javascript.
    </p>
    <p>
      you are still able to view source files on branch/tag tips,
      but the experience is degraded.
    </p>
  </div>
</noscript>
<header class="repo"><div>
<h1>+/EE360C</h1>
<p class="desc">algorithms</p>
</div>
<pre class="clone">git clone https://git.julia.blue/+/EE360C</pre>
</header>
<p class="snapshot-commit"><span class="commit-author">Joseph Ryan</span><span class="commit-message" data-commit="15a372710460d935e5e016792926138d674e8140">Add labs 1 and 2</span><span class="snapshot-sha sha" data-commit="15a372710460d935e5e016792926138d674e8140">15a3727</span><time datetime="2019-11-05T10:13:59-06:00" title="2019-11-05 10:13:59 -0600">2019-11-05</time></p>
<header class="topbar"><details class="switcher"><summary>master</summary><div class="menu"><strong>branches</strong><a class="current" href="/%2B/EE360C/ref/master/">master</a><a class="all" href="/%2B/EE360C/refs">all refs →</a></div></details><nav class="crumbs"><a href="/%2B/EE360C/">EE360C</a> / <a href="/%2B/EE360C/ref/master/tree/Lab1/">Lab1</a> / <span class="cur">notes.md</span></nav>
<span class="view-stats"><span>1.7 KiB</span><span>25 lines</span></span><span class="actions"><a class="raw" href="/%2B/EE360C/raw/ce5402b8cd54c573c1172692273f376ddfcc6fa5/Lab1/notes.md">raw</a></span></header>
<div class="markdown-view"><input type="radio" name="markdown-view" id="markdown-rendered" checked><label for="markdown-rendered">rendered</label><input type="radio" name="markdown-view" id="markdown-code"><label for="markdown-code">code</label><section class="readme rendered"><h2>Part 1</h2>
<h3>A</h3>
<pre>initialize all s ∈ S to free
while ∃ a free student s who hasn't interviewed with all c ∈ C:
    c = first company on s's list to whom s has not yet interviewed with
    if c has open slots:
        (s, c) engage in salary negotiations
    else some pair (s', c) already exists where s' is the
    companies least favorite candidate that it's considering:
        if c prefers s to s':
            s' gets the rejection email
            (s, c) begin negotiations
        else:
            (s', c) remain in negotiations

</pre>
<p>The notable modification to the Gale-Shapley algorithm is that we add a clause to account for the fact that companies have multiple slots for internships. Namely, we always consider the pair <code>(s', c)</code> where <code>s'</code> is the <em>least</em> favorite candidate of company c.</p>
<h3>B</h3>
<p>This algorithm is O(n^2 * m) (n is students and m is internships). The first n term is because we always have to consider every student, the m term is because the number of companies dictates the maximal number of times that a student could have to re-try their matching. The reason there's an extra n term compared to GS is that the act of finding <code>s'</code> every time we try to switch 2 students is another linear scan of the students. If we modified the datastructure used to store the students and companies such that each company maintained a sorted list of the students it had in it's slots, then it would be possible to reduce the complexity to O(m * nlogn) because we could binary search for the students instead of doing linear scans and inserting new students. On the other hand that would increase the space complexity of the algorithm, so I chose to use the O(m * n^2) version.</p>
</section><div class="code-panel"><pre class="code src language-markdown"><span class="code-line"><a class="ln" id="L1" href="#L1">1</a><span class="code-text"><a-p>##</a-p> <a-tt>Part 1</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L2" href="#L2">2</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L3" href="#L3">3</a><span class="code-text"><a-p>###</a-p> <a-tt>A</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L4" href="#L4">4</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L5" href="#L5">5</a><span class="code-text"><a-p>```</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L6" href="#L6">6</a><span class="code-text"><a-p>initialize all s ∈ S to free</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L7" href="#L7">7</a><span class="code-text"><a-p>while ∃ a free student s who hasn&#39;t interviewed with all c ∈ C:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L8" href="#L8">8</a><span class="code-text"><a-p>    c = first company on s&#39;s list to whom s has not yet interviewed with</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L9" href="#L9">9</a><span class="code-text"><a-p>    if c has open slots:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L10" href="#L10">10</a><span class="code-text"><a-p>        (s, c) engage in salary negotiations</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L11" href="#L11">11</a><span class="code-text"><a-p>    else some pair (s&#39;, c) already exists where s&#39; is the</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L12" href="#L12">12</a><span class="code-text"><a-p>    companies least favorite candidate that it&#39;s considering:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L13" href="#L13">13</a><span class="code-text"><a-p>        if c prefers s to s&#39;:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L14" href="#L14">14</a><span class="code-text"><a-p>            s&#39; gets the rejection email</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L15" href="#L15">15</a><span class="code-text"><a-p>            (s, c) begin negotiations</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L16" href="#L16">16</a><span class="code-text"><a-p>        else:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L17" href="#L17">17</a><span class="code-text"><a-p>            (s&#39;, c) remain in negotiations</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L18" href="#L18">18</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L19" href="#L19">19</a><span class="code-text"><a-p>```</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L20" href="#L20">20</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L21" href="#L21">21</a><span class="code-text"><a-p>The notable modification to the Gale-Shapley algorithm is that we add a clause to account for the fact that companies have multiple slots for internships. Namely, we always consider the pair `(s&#39;, c)` where `s&#39;` is the _least_ favorite candidate of company c.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L22" href="#L22">22</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L23" href="#L23">23</a><span class="code-text"><a-p>### </a-p><a-tt>B</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L24" href="#L24">24</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L25" href="#L25">25</a><span class="code-text">This algorithm is O(n^2 * m) (n is students and m is internships). The first n term is because we always have to consider every student, the m term is because the number of companies dictates the maximal number of times that a student could have to re-try their matching. The reason there&#39;s an extra n term compared to GS is that the act of finding `s&#39;` every time we try to switch 2 students is another linear scan of the students. If we modified the datastructure used to store the students and companies such that each company maintained a sorted list of the students it had in it&#39;s slots, then it would be possible to reduce the complexity to O(m * nlogn) because we could binary search for the students instead of doing linear scans and inserting new students. On the other hand that would increase the space complexity of the algorithm, so I chose to use the O(m * n^2) version.</span></span></pre></div></div>
</main>
</body>
</html>
