2. Recall the n-cube graph On, as defined in lecture and in the reading. A verte

Question

2. Recall the n-cube graph On, as defined in lecture and in the reading. A vertez listing of a graph G(V, E) is an ordering of the vertices such that consecutive vertices in the ordering are adjacent in the graph. Let's consider a Qn Vertex Listing: this is a vertex listing of the vertices of Qn starting from the vertex labeled with all 0 bits such that no vertex is repeated and all vertices are included in the listing exactly once. For example, the Qi vertex listing is 0, 1. A Qa vertex listing is 00, 01, 11,10. A Qs vertex listing is 000, 001,011,010, 110, 111, 101,100. (a) (5 points) Provide an iterative algorithm to produce a Q. Vertex Listing. (b) (5 points) Prove the correctness of your iterative Q, Vertex Listing Algorithm. (c) (5 points) Provide a recursive algorithm to produce a Qn Vertex Listing. (It is fine if some iteration is used as well, but there must be at least one recursive call for any case that is not a base case.) (d) (5 points) Prove the correctness of your recursive algorithm Qn Vertex Listing

Explanation / Answer

Ans)a

Now let us write the algorithm, it will take integer n as input and return list:

QnVertexListing(int n):

if n=1

List=[0 1]

return List

else

List = [ ];

Plist = QnVertexListing(n-1);

for each element E in Plist

append 0 before E

add it to List

end

Reverse PList

for each element E in Plist

append 1 before E

add it to List

end

return List

end

Ans)Take a Look at the sequence:

for v=1 : 0 1

for v=2 : 00 01 11 10

for v=3 : 000 001 011 010 110 111 101 100

Observe first half of the vertex listing of any vertex after 1st vertex , it is nothing but 0 appended before the vertex listing of previous vertex.

Now observe the second half of the vertex listing of any vertex after 1st vertex, It is nothing but 1 appended before the vertex listing of previous vertex taken in opposite order.

For example

vertex listing of v=2 is 00 01 11 10

first half : 00 01, vertex listing of previous vertex: 0 1

We can observe the 00 01 is obtained by appending 0 before 0 1.

Now look at second half: 11 10, vertex listing of previous vertex : 0 1, reverse : 1 0

We can see that 11 10 is obtained by appending 1 before 1 0.

Ans)d

In order to prove this algorithm is correct,

Vertex listing of any vertex follows the following rule:

In the vertex listing of any vertex, consecutive elements in the list differ by a single bit

(you can verify it in the list above, it is actually how the vertex listing is created.)

We can prove the correctness of our algorithm by induction:

step 1:

For v=1: vertex listing 0 1

every element differ only by single bit, correct for v=1

Step 2:

Assume that our algorithm gives correct answer for v=k

So, list returned for k vertex is correct i.e every element of this list differs only by a single bit.

Step 3:

Now we have to prove that our algorithm gives correct list for v=k+1 also.

To calculate the vertex listing for v=k+1, first half of list we are creating by appending 0 before the vertex listing of v=k, Since elements of vertex listing of v=k differ only by 1 bit and we are appending same bit before every element, resulting list will also differ by only 1 bit. hence first half of the list is correct.

Now for second half, we are reversing the list. When reversing the list, elements will still differ by 1 bit. and appending same bit before every element will give us a list that will differ by 1 bit.

Now we ave to check wether last element of first half and first element of second follow this rule.

Last element of first half is created by appending 0 before last element of vertex listing v=k and fisrt element of second half is created by appending 1 before the same element. Appendin 0 and 1 before last element of list of v=k give s us element that will differ by only 1 bit.

Hence, vertex listing returned by our algorithm for v=k+1 is correct.

Hence by principle of mathematical induction, our algorithm is correct.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.