DISCRETE MATH - COMBINTORICS What is the minimum number of bits required to stor
ID: 3141454 • Letter: D
Question
DISCRETE MATH - COMBINTORICS
What is the minimum number of bits required to store each binary string of length 50? What is the minimum number of bits required to store each number with 9 base ten digits? What is the minimum number of bits required to store each length 10 fixed-density binary string with 4 ones? In terms of n, what is the minimum number of bits required to store each subset of a set with n elements? What is the minimum number of bits required to store each rearrangement of the numbers 1 through 8? What is the minimum number of bits required to store each three-letter string? (26 alphabetical letters, not case-sensitive)Explanation / Answer
(According to Chegg policy, only four subquestions will be answered. Please post the remaining in another question)
(a) Each bit can have two choices i.e 0 or 1.
Therefore total number of 50 bit binary strings = 250.
Each string takes 50 bits.
Therefore 250 strings take 50*250 bits.
(b) Each digit in base 10 can have 10 options i.e 0,1,2.....9.
So there are 109 numbers with 9 base ten digits.
Each number takes 9 digits.
Therefore 109 numbers take 9*109 digits.
Each decimal digit can be represented using a minimum of four bits (9 = 1001).
Therefore a minimum of 36*109 bits is required.
(c) The 4 ones can occupy 10 digits in 10C4 ways.
The remaining 6 are automatically 0s.
Each string has length 10.
Therefore 10C4 strings take 10*10C4 bits = 2100 bits.
(d) Since there are n elements, the various elements need [log2 n] bits where [x] is the least integer greater than or equal to x also known as the ceiling function.
There are nC1 one element subsets and each subset needs [logn 1] bits.
There are nC2 two element subsets and each subset needs [logn 2] bits.
There are nC3 three element subsets and each subset needs [logn 3] bits.
.....
There are nCn n element subsets and each subset needs [logn n] bits.
=> Minimum number of bits needed to store all subsets
= nC1 * [logn 1] + nC2 * [logn 2] + nC3 * [logn 3] + ......... nCn * [logn n]
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.