Brain Benders
Quick Estimation of π
Problem:
Come up with an algorithm that uses a random number generator to estimate the value of π.
Solutions:
Find the Largest Sub-Array Sum
Problem:
Come up with an algorithm that finds the largest sub-array of any size from a large array of positive and negative integers (but disclude zeros for simplicity). Here are some examples of the largest sub-array (using small arrays):
- [ 3, -5, 7, -4, 2] => [7], sum = 7
- [ 3, 5, 7, -4, 2] => [3, 5, 7], sum = 15
- [13, -5, 7, -4, 2] => [13, -5, 7], sum = 15
Solutions:
- #1, MATLAB code
- #2 - Kadane's Solution and Python code (In solution #1, this is used as comparison)
Create an RNG
Problem:
Suppose that you have a random number generator (RNG) that randomly generates a 1 or a 2 with uniform distribution. Use this RNG to create a second RNG that generates integer values between 1 and 7 with a uniform distribution.
Solutions:
- I'm still thinking about this one...
Tower of Hanoi
Problem:
Pseudo-code a solution for a Tower of Hanoi game where you start with n discs. In case you're unfamiliar with the game (or just need reminding :): Tower of Hanoi
Solutions: