Challenge: Smaller to Larger Random Number Generator

Let’s say you have a random number generator RNG3() that uniformly returns from and you must use it to build RNG7() that uniformly returns from . How might you do it?

Hint
It’s not a variant on , as that yields a bell curve.
Create a matrix with uniform values as follows:

```do {
RNG7 = M[RNG3()][RNG3()];
} while (RNG7 == 0);
```

Challenge: Constant-Time Min-Element Stack

Here’s another problem from the Algorithm Design Manual (Skiena), Interview Problem 4-44:

Design a stack that supports push, pop, and retrieving the minimum element in constant time. Can you do this?
Hint 1
Constant time? Well then it’s stacks all the way down.
Hint 2
Two stacks, to be exact.
Data structure contains two stacks, and . is the minimum element. After calling , push to if . Before calling , pop from if .

Challenge: Most Frequent Element

Here’s a nice problem from Notes on Streaming Algorithms:

Suppose we have sequence from a set , and that we know that one value from occurs more than times in the sequence; find the most frequent value using only two variables having total memory of only bits and in only a single sweep.

Spoiler 1
can store any value up to .
Spoiler 2
can store any value from .
```for each element