{"id":2344,"date":"2018-01-22T22:12:50","date_gmt":"2018-01-23T06:12:50","guid":{"rendered":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/?page_id=2344"},"modified":"2018-01-22T22:12:50","modified_gmt":"2018-01-23T06:12:50","slug":"tutorial-3-solutions","status":"publish","type":"page","link":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/tutorial-3-solutions\/","title":{"rendered":"Tutorial #3 solutions"},"content":{"rendered":"
    \n
  1. We can rewrite xy<\/i> as ((x + y)2<\/sup> – x2<\/sup> – y2<\/sup>)\/2<\/i>, and hence compute xy<\/i> using three calls to our square function, and 4 other operations.<\/li>\n
  2. We construct a new graph G’ = (V, E’) where E’ contains every pair {x, y} of vertices of G that is NOT an edge of G (that is, every {x, y} such that {x, y} \u2209 E), and find the largest clique in G’. Because every subset W of V that is a clique in G’ is an independent set in G, and every subset W of V that is an independent set in G is a clique in G’, the largest clique in G’ is<\/b> the largest independent set in G.<\/li>\n
  3. Given G, we contruct a graph G’ by adding one vertex ve<\/sub> for each edge e \u2208 E, and connecting this vertex to the endpoints of e. That is, if e = {x, y} then we add the edges {ve<\/sub>, x} and {ve<\/sub>, y}. This construction is illustrated below: the graph on top is G, and the bottom graph is G’.
    \n<\/p>\n

    Suppose that G has a vertex cover W with K vertices. The same K vertices will be a dominating set in G’: a vertex of G’ that is not in W is either (1) a vertex from G that’s the endpoint of an edge of G, whose other endpoint must be in W, or (2) one of the new vertices ve<\/sub>, which is connected to both endpoints of the edge e of G, and hence to a member of W.<\/p>\n

    Finally suppose that G’ has a dominating set W’ with K vertices. We construct a vertex cover W of G by choosing<\/p>\n