Find the lexicographic ordering of the bit strings given below based on the…
2020
Find the lexicographic ordering of the bit strings given below based on the ordering 0<1.
(A) 001
(B) 010
(C) 011
(D) 0001
(E) 0101
Choose the correct answer from the options given below:
- A. 001 < 010 < 011 < 0001 < 0101
- B. 0001 < 001 < 010 < 0101 < 011
- C. 0001 < 0101 < 001 < 010 < 011
- D. 001 < 010 < 0001 < 0101 < 011
Attempted by 350 students.
Show answer & explanation
Correct answer: B
Answer: 0001 < 001 < 010 < 0101 < 011
Reasoning (lexicographic order with 0 < 1):
Compare 0001 and 001: positions 1 and 2 are both 0, but at position 3, 0001 has 0 while 001 has 1, so 0001 < 001.
Compare 001 and 010: at position 2, 001 has 0 and 010 has 1, so 001 < 010.
Compare 010 and 0101: 010 is a prefix of 0101, and in lexicographic order the shorter prefix comes first, so 010 < 0101.
Compare 0101 and 011: positions 1 and 2 are equal (0 and 1), at position 3 0101 has 0 while 011 has 1, so 0101 < 011.
Combining these pairwise results yields the final ordering: 0001 < 001 < 010 < 0101 < 011.
A video solution is available for this question — log in and enroll to watch it.