Tuesday 4-0ct

Post date: Oct 04, 2011 10:50:36 PM

Announcements

• • CodingBat server was down

    • CodingBat homework extended to Wednesday night

Homework

• • Work on Project 5: LoopFun

Lecture Outline

• • More for loops

    • With a list: Increment all list elements in a list and return that new list

    • increment(list, amount)

    • squareRoot (x) algorithm:

      • App₁ = x / 2

      • make n approximations using the average of a higher and lower guess

        • App_n = (App_n-1 + x / App_n-1) / 2.0

• For loop in a Monte Carlo Method (From Wikipedia): Monte Carlo Methods are a class of computational algorithms that rely on repeated random sampling to compute their results. Monte Carlo methods are often used in simulating physical and mathematical systems. Because of their reliance on repeated computation of random or pseudo-random numbers, these methods are most suited to calculation by a computer and tend to be used when it is unfeasible or impossible to compute an exact result with a deterministic algorithm.

• Monte Carlo Methods are used in a wide variety of simulations

• Approximate PI by "throwing darts":

  • Area of a circle = PI * r²

  • Assuming a 1 inch radius, the area of this circle is PI*1² = PI*1= PI

  • The square is 2*2 = 4

    • • • |------- r = 1 --------|

• • • If we could the determine the ratio of the circle to the square we can determine pi

      • The ratio we seek is the area of the circle divided by the area of the square

      • With a radius of 1, that is PI / 4.0

    • If the circle area were 78% of the square area, then the ratio would be 0.78

      • PI would be that ratio times 4, or 0.78 * 4 = 3.12

    • Let's pretend to throw darts at this board keeping track if which ones are in the red and which are in the green.

      • This is the ratio, which should be around 78%

• IN CLASS: def fibonacci(n)