Nathan Feaver .com
The Web's Leading Resource on Nathan Feaver

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: