Recall the n-cube graph Qn, as defined in lecture and in the reading. A vertex l
ID: 3729507 • Letter: R
Question
Recall the n-cube graph Qn, as defined in lecture and in the reading. A vertex 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 Q1 vertex listing is 0, 1. A Q2 vertex listing is 00, 01, 11, 10. A Q3 vertex listing is 000, 001, 011, 010, 110, 111, 101, 100.
(a) Provide an iterative algorithm to produce a Qn Vertex Listing.
(b) Prove the correctness of your iterative Qn Vertex Listing Algorithm.
(c) 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) Prove the correctness of your recursive algorithm Qn Vertex Listing.
NOTE: This is the same as another question, but no one seems to be able to answer it. (See https://www.chegg.com/homework-help/questions-and-answers/2-recall-n-cube-graph-qn-defined-lecture-reading-verter-listing-graplh-g-v-e-ordering-vert-q27306209).
Explanation / Answer
SOLUTION:
Answer for C)
The below formaqt describes the subsequent vertex listing
for v=1 : 0 1
for v=2 : 00 01 11 10
for v=3 : 000 001 011 010 110 111 101 100
->then 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.
->Here 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
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
answer for D)
here we have to prove the correctness of the algorithm.
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
We can prove the correctness of our algorithm by induction:
1st step:
For v=1: vertex listing 0 1
every element differ only by single bit, correct for v=1
2nd Step:
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.
Final step/Induction step:
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.
->here 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 have to check wether last element of first half and first element of second follow this rule.
->thus the 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
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.