1. This C program uses the Standard Library qsort to sort a file of integers.
int intcomp(int *x, int *y) { return *x - *y; } int a[1000000]; int main(void) { int i, n=0; while (scanf("%d", &a[n]) != EOF) n++; qsort(a, n, sizeof(int), intcomp); for (i = 0; i < n; i++) printf("%d\n", a[i]); return 0; }
int main(void) { setS; int i; set ::iterator j; while (cin >> i) S.insert(i); for (j = S.begin(); j != S.end(); ++j) cout << *j << "\n"; return 0; }
2. These functions use the constants to set, clear and test the value of a bit:
#define BITSPERWORD 32 #define SHIFT 5 #define MASK 0x1F #define N 10000000 int a[1 + N/BITSPERWORD]; void set(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); } void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); } int test(int i){ return a[i>>SHIFT] & (1<<(i & MASK)); }
3. This C code implements the sorting algorithm, using the functions defined in Solution 2.
int main(void) { int i; for (i = 0; i < N; i++) clr(i); while (scanf("%d", &i) != EOF) set(i); for (i = 0; i < N; i++) if (test(i)) printf("%d\n", i); return 0; }
System Sort | C++/STL | C/qsort | C/bitmaps | |
---|---|---|---|---|
Total Secs | 89 | 38 | 12.6 | 10.7 |
Compute Secs | 79 | 28 | 2.4 | .5 |
Megabytes | .8 | 70 | 4 | 1.25 |
4. See Column 12, especially Problem 12.8. This code assumes that randint(l, u) returns a random integer in l..u.
for i = [0, n) x[i] = i for i = [0, k) swap(i, randint(i, n-1)) print x[i]
5. Representing all ten million numbers with a bitmap requires that many bits, or 1.25 million bytes. Employing the fact that no phone numbers begin with the digits zero or one reduces the memory to exactly one million bytes. Alternatively, a two-pass algorithm first sorts the integers 0 through 4,999,999 using 5,000,000/8 = 625,000 words of storage, then sorts 5,000,000 through 9,999,999 in a second pass. A k-pass algorithm sorts at most n nonrepeated positive integers less than n in time kn and space n/k.
6. If each integer appears at most ten times, then we can count its occurrences in a four-bit half-byte (or nybble). Using the solution to Problem 5, we can sort the complete file in a single pass with 10,000,000/2 bytes, or in k passes with 10,000,000/2k bytes.
9.
The effect of initializing the vector data[0..n-1]
can be accomplished with a signature contained
in two additional n-element vectors,
from and to, and an integer top.
If the element data[i] has been initialized,
then from[i] < top
and to[from[i]]=i.
Thus from is a simple signature,
and to and top together make sure that from
is not accidentally signed by the random contents of memory.
Blank entries of data are
uninitialized in this picture:
The variable top is initially zero;
the array element i is first accessed by the code
from[i] = top to[top] = i data[i] = 0 top++
10. The store placed the paper order forms in a 10x10 array of bins, using the last two digits of the customer's phone number as the hash index. When the customer telephoned an order, it was placed in the proper bin. When the customer arrived to retrieve the merchandise, the salesperson sequentially searched through the orders in the appropriate bin -- this is classical ``open hashing with collision resolution by sequential search''. The last two digits of the phone number are quite close to random and therefore an excellent hash function, while the first two digits would be a horrible hash function -- why? Some municipalities use a similar scheme to record deeds in sets of record books.
11. The computers at the two facilities were linked by microwave, but printing the drawings at the test base would have required a printer that was very expensive at the time. The team therefore drew the pictures at the main plant, photographed them, and sent 35mm film to the test station by carrier pigeon, where it was enlarged and printed photographically. The pigeon's 45-minute flight took half the time of the car, and cost only a few dollars per day. During the 16 months of the project the pigeons transmitted several hundred rolls of film, and only two were lost (hawks inhabit the area; no classified data was carried). Because of the low price of modern printers, a current solution to the problem would probably use the microwave link.
12. According to the urban legend, the Soviets solved their problem with a pencil, of course. For background on the true story, learn about the Fisher Space Pen company. The company was founded in 1948, and its writing instruments have been used by the Russian Space Agency, underwater explorers, and Himalayan climbing expeditions.
Copyright © 1999 Lucent Technologies. All rights reserved. Thu 23 Sep 1999