Computer programming - Lab 6

1. 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, ...

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. Write a function that takes two m × n matrices and transforms the first to the second according to the rules in Conway's Game of Life: matrix elements represent dear or live cells with (at most) eight neighbours, and the transformation rules are:

Use the function to simulate a number of rounds of the game.
Marius Minea
Last modified: Wed Oct 30 7:30:00 EEST 2013