Discrete Mathematics for Computer Science

Chapter Review 473

available storage locations, but these may be scattered across the disk in pieces too small

to use. This sort of problem is called fragmentation.

Suppose a hard disk can store a total of 230 bytes of data and you need to store a file

that is 212 bytes long. Suppose each file currently on the disk is 210 bytes long. What is

the minimum number of files that could be on the disk so that there is no room to add

the new file (in 212 consecutive bytes).

3. Suppose that in a computer program we want an easy way to list-and to access-all

the edges of the complete graph Kn, with each edge listed only once and no unused

space. We can use a part of the adjacency matrix:

n-lI n

n-2 n-I n

3 4 5 6 7... n

2 3 4 5 6 7 ... n

1 2 345 6 7 ... n

where after vertex i, we list only the edges going to higher-numbered vertices. Now, we

could list all the edges in a single array:

{n-l,n} {n-2, n-1} {n-2, n} {n-3, n-2} ... {1,n-l} {1,n}

Use combinations to express the position of edge (i, j) in the array above.

4. One method of checking for errors in data is to add "parity bits." If a number n has the
   form X1X2 ... Xn where xi is either 0 or 1 is to be transmitted, an additional bit Xn+l is
   added at the end of the original n bits. The added bit is 1 if n has an odd number of 1
   bits and 0 if n has an even number of 1 bits. When the number is received, the receiving
   computer can check the number and see whether the parity bit is correct. This way, the
   receiving computer can recognize any 1-bit error in transmitting the number.

(a) A string of 0's and l's is to be processed, from left to right, and converted to an

even-parity string by adding a parity bit to the end of the string. The parity bit is

initially 0. When a 0 character is processed, the parity bit remains unchanged. When

a 1 character is processed, the parity bit is switched from 0 to 1 or from I to 0. Prove

that the number of 1's in the final string-that is, including the parity bit-is always

even.) (Hint: Consider cases).

(b) A string consisting of 0's and 1's has even parity if 1 occurs an even number of

times; otherwise, the string has odd parity. How many strings of length n have even

parity? How many strings of length n have odd parity?

5. Six distinct symbols are transmitted through a communication channel. A total of 12
   blanks are to be inserted between the symbols, with at least two blanks between every
   pair of symbols. How many ways can the symbols and blanks be arranged? How many
   ways can the symbols and blanks be arranged if there are 25 blanks?


6. A boolean function of n boolean variables is defined by the assignment of a value of
   either 0 or 1 to each of the 2n ordered n-tuples of 0 - 1 values for the variables. Recall
   the usual convention that 0 represents FALSE and 1 represents TRUE.
   (a) How many different boolean functions of n variables are there?
   (b) Approximate, in ordinary decimal notation, the number of boolean variables in
   eight variables: How many decimal digits in length is that number?