{"id":112,"date":"2015-01-10T10:20:08","date_gmt":"2015-01-10T17:20:08","guid":{"rendered":"https:\/\/blogs.ubc.ca\/cpsc320\/?p=112"},"modified":"2015-01-10T10:20:08","modified_gmt":"2015-01-10T17:20:08","slug":"tutorial-1-problems","status":"publish","type":"post","link":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/2015\/01\/10\/tutorial-1-problems\/","title":{"rendered":"Tutorial #1 Problems"},"content":{"rendered":"<h3>Problems for tutorial #1<\/h3>\n<ol>\n<li>Consider the\u00a0Coop Student\/Company Matching Problem:\u00a0<tt>n\u00a0<\/tt>students apply for jobs\u00a0at\u00a0<tt>m<\/tt> companies, where company <tt>i<\/tt> is looking for <tt>n<sub>i<\/sub><\/tt> COOP students. There are at least enough students to fill all of the positions (and there may be too many). Every student has a ranking of companies in order of preference, and each company has a ranking of students in order of preference. An assignment of students to companies is <tt>stable<\/tt> if neither\u00a0of the following situations arises:\n<ul>\n<li>There are two students <tt>s<\/tt> and <tt>s'<\/tt>\u00a0and a company <tt>c<\/tt> such that <tt>s<\/tt> is assigned to <tt>c<\/tt>, <tt>s'<\/tt> is unemployed, and <tt>c<\/tt> prefers <tt>s'<\/tt> to <tt>s<\/tt>.<\/li>\n<li>There are two students <tt>s<\/tt> and <tt>s'<\/tt>, and companies <tt>c<\/tt> and <tt>c'<\/tt>, such that <tt>s<\/tt> is assigned to <tt>c<\/tt>, <tt>s'<\/tt> is assigned to <tt>c'<\/tt>, <tt>s<\/tt> prefers <tt>c'<\/tt> to <tt>c<\/tt>, and <tt>c'<\/tt>prefers <tt>s<\/tt> to <tt>s'<\/tt> (the usual type of instability).<\/li>\n<\/ul>\n<p>Describe an efficient algorithm that will produce a stable assignment of students to companies, first using a reduction and the Gale-Shapley Algorithm, and then by modifying the G-S Algorithm so that it works directly on this problem.<\/li>\n<li>Prove or disprove each of the following two statements. That is, either prove that the statement is true, or give an example to show that it is false. Hint: exactly one of the statements is true.\n<ol class=\"level2\">\n<li>In every instance of the Stable Matching Problem, there is a stable matching containing a pair <tt>(w, m)<\/tt> such that <tt>w<\/tt> is ranked first on the preference list of <tt>m<\/tt> and <tt>m<\/tt> is ranked first on the preference list of <tt>w<\/tt>.<\/li>\n<li>Consider an instance of the Stable Matching Problem in which there exists a man <tt>m<\/tt> and a woman <tt>w<\/tt> such that <tt>m<\/tt> is ranked first on the preference list of <tt>w<\/tt> and <tt>w<\/tt> is ranked first on the preference list of <tt>m<\/tt>. Then in every stable matching <tt>S<\/tt> for this instance, the pair <tt>(w, m)\u00a0<\/tt>belongs to <tt>S<\/tt>.<\/li>\n<\/ol>\n<\/li>\n<li>(Induction review) Suppose you begin with a pile of <tt>n<\/tt> stones, and split this pile into <tt>n<\/tt> piles of one stone each by successively splitting a pile of stones into two smaller piles. Each time you split a pile you multiply the number of stones in each of the two smaller piles you form, so that if these piles have <tt>r<\/tt> and <tt>s<\/tt> stones in them, respectively, you compute <tt>rs<\/tt>. Show that no matter how you split the pile, the sum of the products computed at each step equals <tt>n(n-1)\/2<\/tt>. Here is an example that shows how the computation proceeds:<br \/>\n<blockquote><p><img decoding=\"async\" src=\"http:\/\/www.ugrad.cs.ubc.ca\/~cs320\/2014W1\/tutorials\/tree.jpg\" alt=\"\" \/><\/p><\/blockquote>\n<p>The sum is 21+2+12+1+3+2+2+1+1 = 45, which is indeed 10 * 9 \/ 2.<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"<p>Problems for tutorial #1 Consider the\u00a0Coop Student\/Company Matching Problem:\u00a0n\u00a0students apply for jobs\u00a0at\u00a0m companies, where company i is looking for ni COOP students. There are at least enough students to fill all of the positions (and there may be too many). Every student has a ranking of companies in order of preference, and each company has [&hellip;]<\/p>\n","protected":false},"author":7560,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3426],"tags":[],"class_list":["post-112","post","type-post","status-publish","format-standard","hentry","category-tutorials"],"_links":{"self":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/posts\/112","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/users\/7560"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/comments?post=112"}],"version-history":[{"count":0,"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/posts\/112\/revisions"}],"wp:attachment":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/media?parent=112"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/categories?post=112"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/tags?post=112"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}