Algorithms in a Nutshell

Size of a Problem Instance | 13

AlgorithmsThe Math of

Selecting the representation of a problem instance depends on the type and variety

of operations that need to be performed. Designing efficient algorithms often

starts by selecting the proper data structures in which to represent the problem to

be solved, as shown in Figure 2-1.

Instances Are Encoded

Suppose you are given a large numberxand want to compute the parity of the

number of 1s in its binary representation (that is, whether there is an even or odd

number of 1s). For example, ifx=15,137,300,128, its base 2 representation is:

x 2 =1110000110010000001101111010100000

and its parity is even. We consider two possible encoding strategies:

Encoding 1 ofx: 1110000110010000001101111010100000

Here, the 34-bit representation ofxin base 2 is the representation of the

problem and so the size of the input isn=34. Note thatlog 2 (x)isy≅33.82, so

this encoding is optimal. However, to compute the parity of the number of 1s,

every bit must be probed. The optimal time to compute the parity grows linearly

withn (logarithmically withx).

xcan also be encoded as ann-bit number plus an extra checksum bit that shows

the parity of the number of 1s in the encoding ofx.

Encoding 2 ofx: 1110000110010000001101111010100000[0]

The last bit ofxin Encoding 2 is a 0 reflecting the fact thatxhas an even

number of 1s (even parity=0). For this representation,n=35. In either case, the

size of the encoded instance,n, grows logarithmically withx. However, the time

for an optimal algorithm to compute the parity ofxwith Encoding 1 grows loga-

rithmically with the size of the encoding ofx, and with Encoding 2 the time for an

optimal algorithm is constant and doesn’t depend on the size of the encoding ofx.

Figure 2-1. More complex encodings of a problem instance

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use

Licensed by

Ming Yi