CPSC 320 2020W1: Assignment 2
This assignment is due Sunday, October 9, 2020 at 22:00 Pacic Time. Assignments submitted within 24 hours after the deadline will be accepted, but a penalty of 15% will be applied. Please follow these guidelines:
Prepare your solution using LATEX, and submit a pdf le. Easiest will be to use the .tex le provided. For questions where you need to select a circle, you can simply change \fillinMCmath to \fillinMCmathsoln .
Enclose each paragraph of your solution with \begin{soln}Your solution here…\end{soln}. Your solution will then appear in dark blue, making it a lot easier for TAs to nd what you wrote.
Start each problem on a new page, using the same numbering and ordering as this assignment handout.
Submit the assignment via GradeScope at https://gradescope.ca. Your group must make a single submission via one group member’s account, marking all other group members in that submission using GradeScope’s interface.
After uploading to Gradescope, link each question with the page of your pdf containing your solution. There are instructions for doing this on the CPSC 121 website, see https://www.students.cs.ubc.ca/ ~cs-121/2020W1/index.php?page=assignments&menu=1&submenu=3. Ignore the statement about group size that is on that page.
Before we begin, a few notes on pseudocode throughout CPSC 320: Your pseudocode should commu- nicate your algorithm clearly, concisely, correctly, and without irrelevant detail. Reasonable use of plain English is ne in such pseudocode. You should envision your audience as a capable CPSC 320 student unfamiliar with the problem you are solving. If you choose to use actual code, note that you may neither include what we consider to be irrelevant detail nor assume that we understand the particular language you chose. (So, for example, do not write #include
Remember also to justify/explain your answers. We understand that gauging how much justi- cation to provide can be tricky. Inevitably, judgment is applied by both student and grader as to how much is enough, or too much, and it’s frustrating for all concerned when judgments don’t align. Justica- tions/explanations need not be long or formal, but should be clear and specic (referring back to lines of pseudocode, for example). Proofs should be a bit more formal.
On the plus side, if you choose an incorrect answer when selecting an option but your reasoning shows partial understanding, you might get more marks than if no justication is provided. And the eort you expend in writing down the justication will hopefully help you gain deeper understanding and may well help you converge to the right selection :).
Ok, time to get started…
1
1 Statement on Collaboration and Use of Resources
To develop good practices in doing homeworks, citing resources and acknowledging input from others, please complete the following. This question is worth 2 marks.
1. All group members have read and followed the guidelines for groupwork on assignments in CPSC 320 (see https://www.students.cs.ubc.ca/~cs-320/2020W1/index.php?page=assignments&menu=1&submenu=3).
Yes No
2. We used the following resources (list books, online sources, etc. that you consulted):
3. One or more of us consulted with course sta during oce hours. Yes No
4. One or more of us collaborated with other CPSC 320 students; none of us took written notes during our consultations and we took at least a half-hour break afterwards.
Yes No
If yes, please list their name(s) here:
5. One or more of us collaborated with or consulted others outside of CPSC 320; none of us took written notes during our consultations and we took at least a half-hour break afterwards.
Yes No
If yes, please list their name(s) here:
2
2 Reductions and Quantum Computing
Quantum computing is an exciting and promising future technology for computing (and cynics will point out it has been for quite some time and might continue to be exciting and promising but useless for a long time to come…), and it’s cool to note that the world’s leading quantum computing company is a UBC spin-o based in Burnaby, D-Wave Systems. They are the rst company to have sold commercial quantum computers, and they have a several-year headstart on big companies like IBM and Google.
D-Wave’s approach to quantum computing is controversial, however, because rather than trying to build quantum versions of standard logic gates, D-Wave builds computers that solve a very specic optimization problem. Getting a D-Wave quantum computer to solve a dierent problem, therefore, involves creating a reduction from the problem you want to solve to the problem the computer solves. This makes it great practice for you to learn about reductions!
The fundamental problem solved by D-Wave’s quantum computers is the Ising Spin Glass Minimization problem (which we’ll abbreviate as ISGM):
Given an undirected graph G = (V,E) with vertices V and edges E, an integer (positive, zero, or negative) weight hv for each v ∈ V , and an integer (positive, zero, or negative) weight Ju,v for each edge {u, v} ∈ E, nd an assignment of +1 or −1 to the variables xv for each v ∈ V that minimizes the objective function:
hvxv + Ju,vxuxv v∈V (u,v)∈E
(In real life, the D-Wave computer works on a specic, nite-sized graph, but we can ignore that, because it’s possible to embed other graphs into D-Wave’s graph. Also, the weights in real life have limits on their magnitude and precision, but we’ll ignore that, too.)
For example, consider this graph:
h2 = −7
h1 = 5
h3 = 6
The problem is to assign a +1 or −1 to each vertex to try to minimize the objective function. If you assign all xi = +1, then the objective function is (5)(+1)+(−7)(+1)+(6)(+1)+(10)(+1)(+1)+(−40)(+1)(+1)+ (30)(+1)(+1) = 4. Here’s a table of all the values the objective function could take:
x1 -1 -1 -1 -1
+1 +1 +1 +1
x2 x3 Value -1 -1 -4 -1 +1 28
+1 -1 -98 +1 +1 54 -1 -1 66 -1 +1 -62 +1 -1 12 +1 +1 4
3
J1,3 = −40
J1,2 = 10
J2,3 = 30
So for this instance, the minimum value is −98, which happens if we assign x1 = −1 (the vertex at the top), and x2 = +1 (the vertex on the left), and x3 = −1 (the vertex on the right).
In this problem, we’ll explore a real-life, non-trivial, practical reduction. This will require quite a bit of reading, but it’s good to see how a real reduction works. In particular, we’ll consider solving this problem, which we’ll abbreviate as ATPG (for Automatic Test Pattern Generation, because this problem arises when developing tests for integrated circuits):
Given a combinational circuit, with ni inputs, na 2-input AND gates, no 2-input OR gates, nn NOT gates, and a single output, nd a truth assignment to the inputs that makes the output TRUE, or determine that no such truth assignment exists. (In case you forgot from CPSC 121, a combinational circuit is the usual Boolean logic circuit, with no latches, no feedback cycles, and every wire (except the primary inputs) driven by exactly one gate.)
For example, consider the following two circuits:
in1 in2
out in1
out
For the circuit on the left, a solution is in1=TRUE and in2=FALSE. For the circuit on the right, the solution is that no input assignment makes the output TRUE.
For the remainder of this problem, we will explain a reduction that takes an instance of ATPG and converts it into an instance of ISGM. Your job will be to come up with the other part of the reduction, that takes the solution to the ISGM instance and converts it back into a solution to the original ATPG instance.
OK, let’s do the reduction! An instance of ATPG is a circuit, as specied above. We’ll use this circuit to construct a graph, which we’ll feed to the ISGM solver. In particular, the graph we construct will closely follow the structure of the circuit, where we replace the gates in the circuit with special little sub-graphs (and also add a few extra vertices and edges to the graph). And we’ll use −1 and +1 in our ISGM instance to denote FALSE and TRUE (respectively) in the logic circuit instance.
The rst step of this construction is that since the ATPG instance has ni inputs, we will create ni vertices in the graph we are building, and we will set the h weight for each of these vertices to be 0. This means that whether the ISGM solution assigns +1 or −1 to these vertices, they won’t change the value of the objective function. (However, any edges connecting these vertices to other vertices might contribute to the value of the objective function. More on those edges later, when we talk about what to do about wires in the circuit.)
Next, for every NOT gate in the ATPG instance, we introduce two vertices and an edge connecting them, shaped like this:
h2 = 0
h1 = 0
with x1 being the input to the NOT gate and x2 being the output. Since h1 = h2 = 0 and J12 = 1, we get
the following contributions to the objective function, depending on the assignments to x1 and x2:
4
J1,2 = 1
x1 x2 Value -1 -1 1 -1+1 -1
+1 -1 -1 +1+1 1
In other words, if the ISGM solution assigns values to the NOT gate input and output that correspond to the NOT gate correctly inverting its input to its output, then this sub-graph contributes −1 to the total objective function; if the ISGM solution doesn’t assign correct values for the NOT gate, then it contributes a larger number (in this case, 1). Therefore, since there are nn NOT gates in the circuit, then all these NOT-gate subgraphs combined will contribute −nn to the objective function if the ISGM solution assigns values such that every NOT gate’s output is the NOT of its input; or they’ll contribute a larger number if any NOT gate isn’t behaving properly.
How about AND gates? For each AND gate in the circuit, our reduction creates a 3-vertex sub-graph like this:
h1 = 2
h2 = −1
where you can think of the output of the AND gate as x1 at the top, and the 2 inputs are x2 and x3 on
the left and right. This table shows the contribution of this subgraph to the overall objective function:
x2 x3 x1 Value -1 -1 -1 -3 -1-1+1 9 -1+1-1 -3 -1 +1 +1 1
+1 -1 -1 -3 +1-1+1 1 +1+1-1 1 +1 +1 +1 -3
As you can see, whenever an ISGM solution assigns values to the vertices that correspond to the AND gate being a proper AND gate, the contribution is −3. In all other assignments, the contribution is a larger number. Since there are na AND gates in the circuit, then if the ISGM assigns all AND gates correctly, the sub-graphs will contribution −3na to the value of the objective function; if any AND gate is assigned incorrectly, the contribution will be larger.
OR gates are handled similarly. For each OR gate, we’ll create a sub-graph like this:
h3 = −1
J2,3 = 1
5
J1,3 = −2
J1,2 = −2
h1 = −2
h2 = 1
J2,3 = 1
x2 x3 x1 -1 -1 -1 -1-1+1 -1+1-1 -1 +1 +1
+1 -1 -1 +1-1+1 +1+1-1 +1 +1 +1
h3 = 1
Value -3 1 1 -3 1 -3 9 -3
As above, whenever an ISGM solution assigns values to
a proper OR gate, the contribution is −3. In all other
Since there are no OR gates in the circuit, then if the ISGM assigns all OR gates correctly, the sub-graphs will contribution −3no to the value of the objective function; if any OR gate is assigned incorrectly, the contribution will be larger.
For the single output of the ATPG instance circuit, we’ll create a single vertex vout and set hvout = −1. This means that if the output is set to +1 in the ISGM solution (corresponding to TRUE in the ATPG instance), then this vertex contributes −1 to the objective function; otherwise, it contributes a larger number (in this case 1).
Finally, we’re going to add a bunch of edges to the graph for our ISGM instance, to model all the connections in the circuit. In particular, for every connection from a gate output (or from one of the ni primary circuit inputs) to a gate input (or to the single primary circuit output), create an edge in the graph between the corresponding vertices. Set the J weight of all these edges to be −1. This means that if both ends of a connecting wire get assigned the same ±1 value (which corresponds to both ends of a wire in the circuit having the same logic value, i.e., correct circuit operation), this edge contributes −1 to the ISGM objective function; if the two ends are assigned dierent values, then the contribution is larger (in this case, 1). Let nc be the number of these connection edges, and then the total contribution to the objective function is −nc if the ISGM solution assigns values so that these edges behave correctly, or a larger number if not.
For example, if we return to the ATPG circuit example we saw earlier, and applied the reduction above to the circuit on the left, we’d end up with the following graph, with the h and J weights labeled on the graph. (We’ve turned the subgraphs for the gates sideways to make it easier to draw.)
the vertices that correspond to the OR gate being assignments, the contribution is a larger number.
0 -1 -1
0 0 0 -1 -1 1 -1
2 -1 -1
Whew! That’s it! We’re given an instance of ATPG (a combinational circuit with ni primary inputs, na AND gates, no OR gates, nn NOT gates, and 1 primary output), and we apply these rules to derive an
6
J1,2 = −2
J1,3 = −2
-2
1
-2
instance of ISGM (a graph with ni +3na +3no +2nn +1 vertices and 3na +3no +2nn +nc edges, and weights on the vertices and edges). We can hand this ISGM instance to the D-Wave computer, and it will return an ISGM solution: an assignment of ±1 to every vertex in the graph that minimizes the objective function. Your job now is to explain how to interpret that ISGM solution back into a solution to the ATPG instance:
1.
[5 marks] Based on the ISGM solution, how/when can you conclude that there is no truth assignment that makes the circuit output TRUE in the ATPG instance? Briey justify your answer. (Note that even though this problem is LONG, the answers are very short!)
Solution: We’ll write these solutions out a bit longer and more formally than we’d expect from you, just so you have lots more detail.
Let m = 0ni − 1nn − 3na − 3no − 1nc − 1. (The m stands for minimum.) This value is a lower-bound on the value of the objective function of the ISGM instance that we generate, because the objective function is just the sum of the contributions of the various parts, and m is the sum of the minimum possible value of each part.
If the minimum solution value returned by ISGM is > m, we conclude that the ATPG instance has no solution; if the minimum solution value returned by ISGM = m, then there is a solution to the ATPG instance.
To justify this, note that an ISGM solution will attain the value of m i the solution assigns the x values such that each component of the graph attains its minimum possible value. That means that the output node must be assigned +1, that both ends of each edge in the ISGM instance corresponding to a connecting wire in the ATPG instance must be assigned the same value, and that vertices in the ISGM instance must be assigned values that correspond with each gate behaving as it must in the ATPG instance. The only freedom the ISGM instance might have would be in the assignments to the vertices corresponding to the input nodes. Therefore, an ISGM solution with value m corresponds to an input assignment in the ATPG instance that produces correct circut operation and makes the output node TRUE. If the ISGM solution is greater than m, then no such input assignment is possible.
As an editorial note, it’s an important when writing up a solution like this to keep clear the distinction between the two problems and their respective instances, solutions, terminology, etc.
[5 marks] If the ISGM solution does indicate that there is an input TRUTH assignment that makes the circuit output TRUE, explain how to extract that ATPG solution (an input truth assignment for the circuit) from the ISGM solution. Briey justify your answer, specically why the truth assignment you extract will make the circuit output TRUE. (Again, this isn’t a long answer.)
Solution: This part builds on the solution in the rst part, and we’re OK if you reference the argument you made already.
To get the input assignment for the ATPG instance, you simply look at what the ISGM solution assigns to the vertices corresponding to the inputs of the ATPG instance: +1 in the ISGM instance means TRUE in the ATPG instance for the corresponding input; −1, means FALSE.
The justication is basically the same as in the preceding part. Because we know the ISGM solution has value m, we know that each component in the ISGM solution is modeling correct operation of the corresponding gate/wire/input/output of the ATPG instance. Since the ISGM output node gets assigned +1 in this solution, we know the corresponding ATPG instance outputs TRUE.
Reductions and Quantum Computing 2
2.
3
OK, now it’s your turn to create your own reduction for the D-Wave computer! (This problem is a continuation from Problem 2.)
7
Fortunately, the reduction we’re asking you to do is a lot easier than the one in the preceding problem. However, this time, you get to create and justify the entire reduction.
For this problem, we consider how to determine whether a graph is bipartite. As you may recall from the textbook (Section 1.2, pp. 1415), a graph is bipartite if it’s possible to partition the set of vertices V into two disjoint subsets V = X ∪Y with X ∩Y = ∅, such that every edge goes between X and Y. Specically, the problem instance will consist of a graph, and your answer should be Yes if the graph is bipartite, or No if it’s not.
You must solve this problem by giving a reduction to the ISGM problem from Problem 2. (In real life, there are much easier ways to check whether a graph is bipartite, but the goal here is for you to learn how to do an entire reduction. To prevent silly solutions, your reduction must create a non-trivial ISGM instance that reects the structure of the bipartiteness instance. For example, we will not give any credit for a solution of the form, Run a standard algorithm that checks for bipartiteness, and if the answer is yes, then create one ISGM instance, and if the answer is no, then create some other ISGM instance.)
1. [5 marks] First, describe precisely how you reduce an arbitrary instance of the bipartiteness checking problem into an instance of ISGM.
Solution: These two parts need to be marked together. (Apologies to the TAs who have to mark this, if students write up really complex and confusing reductions!) The justication for this part will be in the next part of the solutions.
Let Gb = (V, E) be the graph instance for the bipartiteness checking problem. We will create the graph Gi for the ISGM problem as the same graph, i.e., let Gi = Gb. The rest of the reduction just requires that we specify weights for each vertex and edge. We’ll assign weight hv = 0 for each vertex v ∈ V . And we’ll assign weight Je = 1 for each edge e ∈ E.
2. [5 marks] Next, describe how you extract the solution to the bipartiteness instance, based on the solution to the ISGM instance. Justify your answer. (I.e., how do you know for sure that your answer is correct?)
Solution: Formally, we can extract the solution to the bipartiteness check (which is a yes/no answer) from the ISGM instance by just checking whether the minimum value of the ISGM objective function (i.e., the value of the solution that the ISGM solvers gives you) is equal to −|E|. If it is, the graph is bipartite; if it isn’t, the graph isn’t bipartite.
It’s probably a bit more helpful to explain that if the ISGM instance achieves the objective value −|E|, then we can witness the bipartiteness of the graph by grouping all vertices assigned +1 in the ISGM instance into the subset X, and all vertices assigned −1 in the ISGM instance into the subset Y . Obviously (by construction), X and Y are disjoint, and V = X ∪ Y . How do we show that every edge goes between X and Y ? Similarly to in Problem 2, we note that the value of the ISGM objective function is just the sum of the contributions from each part of the graph. In particular, the smallest value each edge can contribute is −1, so the smallest possible value of the objective function is −|E| and that occurs i each edge has its endpoints assigned dierent values in the ISGM instance, which corresponds to the two endpoints of every edge being in the dierent sets X and Y .
Formally, the way we phrased the above paragraph, we have only proved one direction: that if the ISGM instance has value −|E|, then the graph is bipartite. It’s good training when doing reductions to make sure we prove both directions, i.e., that if the ISGM instance doesn’t achieve the value −|E| the graph is NOT bipartite. (Or equivalently, using the contrapositive, that if the graph is bipartite, the ISGM instance has value −|E|.)
Since we’re writing up this solution to help you learn, let’s write up BOTH of those proofs of the second direction. Logically, these are equivalent, so you only need one (of these two proof of this direction you of course also need the proof of the rst direction, which we did in the 2nd paragraph above).
8
4
Proof 1 of (ISGM ̸= −|E| implies not bipartite):
As noted earlier −|E| is clearly a lower bound on the value of the objective function. Therefore, if ISGM could not reach −|E|, that means that for ALL possible assignments to the x values of the vertices, the objective function was > −|E|. This means that every possible way of splitting the vertices into two sets (into X and Y as described above) will always have at least one edge entirely contained in X or entirely contained in Y (as that’s what makes the objective function > −|E|). Since every possible partition of the vertices has at least one edge that is entirely contained in one set, the graph isn’t bipartite.
Proof 2 of the same property, but doing the contrapositive (bipartite implies ISGM instance has value −|E |):
This is easier to write. Since the graph is bipartite, there exists a partition of the vertices into disjoint sets X and Y such that V = X ∪ Y and every edge goes between X and Y . So, therefore, if we assign xv =+1forallv∈X,andxv =−1forallv∈Y,theneveryedgewillcontribute(1)(1)(−1)=−1tothe objective function. Therefore, the ISGM instance will evaluate to −|E| for this particular assignment. But since that’s the minimum possible value of the ISGM instance, then we know that that is the value of the ISGM solution.
Editorial Note: We’re writing a lot more here than we expect of you, but it’s important to note that at the top level, we need to prove that our reduction gives the correct answer both when the input instance is bipartite and when the input instance is not bipartite. Sometimes you can explain both of these parts at the same time, but generally, when justifying a reduction, you’ll want to have both parts. (Now in what might be confusing, but was meant to be helpful, we’ve further split up the second part of the proof, by giving you two dierent but equivalent ways to do it.)
Distances in Graphs
In class, we discussed an algorithm to nd the diameter of a graph: the pair of vertices whose distance (the number of edges on the shortest path between them) is maximum. The problems in this section all related to distances in graphs. In all cases, we consider a graph G = (V, E), with n = |V | and m = |E|.
1. [5 marks] Suppose that an undirected graph contains two nodes u and v whose distance is strictly greater than n/2. Prove that there is a vertex w distinct from u and v, and whose removal disconnects G and leaves u and v in dierent connected components.
Hint: suppose the shortest path P from u to v consists of the vertices u0 = u, u1, u2, . . . , uk−1, uk = v where k > n/2. Assume that none of u1, … uk−1 can be removed to disconnect G and leave u and v in dierent connected components. Start by looking at the path from u0 to uk that leaves P before u1, and rejoins P as late as possible after u1. Count the number of vertices of this path that don’t belong to P, and proceed inductively.
Solution: Consider the tree obtained by doing a breadth-rst search starting from u. Because the shortest path from u to v contains k + 1 vertices, this tree has at least k + 1 levels. If every level except levels 0 and k contains at least 2 vertices, then the tree contains at least 2(k − 1) + 2 = 2k vertices. This is however a contradiction because 2k > n, and the tree can not contain more vertices than the graph G. So at least one level i of the tree (1 ≤ i ≤ k − 1) contains a single node w. Removing that node will disconnect the graph, since every path from u to v needs to go through w (the only node on its level on the tree).
2. [5 marks] Describe an O(n + m) time algorithm to nd such a vertex w. Hint: a depth-rst search from u might be helpful.
Solution: We use a breadth-rst search starting at u, and keep track of the distance of each node from u, and of the number of nodes at each distance. Once we have found a distance with a single node, this node is the node whose removal disconnects G as required.
9
3. [5 marks] Given two vertices u and v of G, we can nd the smallest subset of edges of G that connects them (the shortest path between them) in O(n + m) time using breadth-rst search. Suppose now that we are given three vertices u, v and w, and that we want to nd the smallest subset of edges of G that connects them (a bit like a minimum spanning tree, except that we only want to connect these three vertices instead of every vertex of the graph).
It is tempting to believe that the edges we are looking for include the shortest path between two of the three vertices, plus some additional edges to connect the third vertex to the rst two. Give an example (a graph G and three specic vertices) that shows this conjecture is false. Hint: our solution is a 3-fold symmetric graph with 22 vertices and 24 edges.
Solution: Consider the following graph:
The shortest path from any one of the vertices a, b and c to another one of these vertices ows along the edges of the gure. Adding a connection to the third vertex gives us a subgraph with 11 vertices and 10 edges. We can however connect a, b and c using the edges in the middle of the gure, using only 10 vertices and 9 edges.
10