2. Write a function that reads a text from input and encodes it into a byte (unsigned char) array given as parameter, using 5 bits for each character. Use the (5-bit) value 0 to denote the end of text, and define encodings for letters (case-insensitive), space, and period. Any other character should be mapped to '?'. Write another function that takes a byte array containing a 5-bit-encoded text and prints the text.
Combinatorics
3. Write a function that produces all n-choose-k sets of k
numbers from 1 to n and prints them in increasing order
(both the numbers in each set, and the sets).
Hint: keep an array with the numbers chosen and how many there are
still to choose. For each number, you may or may not choose it, unless
you must choose all remaining numbers to fill up the set.
4. Write all permutations of numbers 1 to n in lexicographic ordering.
Hint: from the current permutation, search backwards and find the first
number smaller than the one after it. Then, replace it with the next-largest
number in the tail of the array, and add all remaining ones in increasing order.
Miscellaneous
5. The Collatz
conjecture says that for any positive n, the following
sequence of operations will eventually reach 1: if n is even, divide it
by 2; else, if n is odd, compute n = 3n + 1.
a) Tabulate for n = 1 to 1 million the number of steps it takes to reach 1
(the "stopping time") starting from n. Avoid repeating computations.
b) Compute and print from the tabulated values the sequence of numbers
whose stopping time is larger than that of any smaller number, i.e.:
1, 2, 3, 6, 7, 9, ...
6. Implement multiplication of arbitrarily large natural numbers, stored as arrays of digits. Write a function that takes as parameters two such numbers, computes and prints their product.
7. Given two natural numbers m < n, compute and print the digits
in the binary representation of fraction m / n . If the fraction
is periodic, determine its period and print it out between parantheses,
e.g. 1/10 = 0.0(0011) .
Hint: use an array to track remainders you have already seen, as shown in the course slides for base 10.
Extra credit: if n ≤ 64, use bit operations on a uint64_t both
for tracking remainders and constructing the result.
Strings
8. Write a function to determine whether a string is an anagram of another string (can be obtained by rearranging its letters). Hint: use a histogram of letters.
9. Write a function that takes as parameter a string and changes it, collapsing any sequence of whitespace (as reported by isspace) to a single space character.
10. Write a function that takes as parameter a string, and prints out the string with all words in reverse order. A word is a sequence of non-whitespace characters. Do not change the spacing between words.