Judea Pearl

Judea Pearl is the newest winner of the Turing Award.
Judea Pearl's studies and advancements range from in artificial intelligence to philosophy
I recently listened to 1hr 41min interview by Stephen Ibaraki on behalf of ACM  here are the highlights

Education:



Counterfactuals:


Success:

3: First Order Recurrence Relations

Check out the project description here

First Order what?
First order recurrence is a type of a recursive equation that can be . The following equations have first order recurrence relations:

• The coefficients are constants and only to the first power
• The nth term depends only on term ( n - 1 )
• General Form: S(n) = cS( n - 1 ) + g(n)

Here is the equation to convert first order recursive equations into linear equations

• S(n) = C^n-1S(1) + ⁿΣ_i=2 [ C^n-i * g(n) ]

Quick example

• Original: S(n) = 2*S( n - 1 ) + 3
• Becomes: S(n) = 2^n-1 * S(1) + ⁿΣ_i=2 [ 2^n-i * 3 ]

Imagine inputing 5,000 for n. The second equation would have a significantly smaller big-O complexity

The Code
Due to the fact that my professor usually gives us read-in-files contain similar formats I decided to make a master parsing class that you can look at on github if you want.

• The code doesn't contain anything fancy.
• I love ruby's exponent operator **
• I love ruby's for loops

2: Second Order Recurrence Relations

Second Order What?
Second Order Recurrence Relations is a fancy way of saying, if recursive equation meets a specific criteria, it can be reduced to a no recursive equation.

Requirements:

• The nth term depends on the two previous terms
• Constant coefficients with exponents no greater than 1
• Must be homogeneous ( g(n) == 0 )
• General form: S(n) = C₁S( n - 1 ) + C₂S( n - 2 )

Process:

1. Find the roots of t² - C₁t - C₂ = 0
1. r₁ & r₂
2. Solve for p & q
1. S(1) = p + q
2. S(2) = p( r₁ ) + q( r₂ )
3. Plug answers in the solution formula
1. S(n) = p( r₁ )^{n - 1} + q( r₂ )^{n - 1}

Example:

   S(n) = 2S( n - 1 ) + 3S( n - 2 )
   S(1) = 3
   S(2) = 1

1.  t² - 2t - 3 = 0
• r₁ = 3
•  r₂  = -1
2. Solve for p & q
• 3 = q + p
• p( 3 ) + q( -1 ) = 1
• p = 1
• q = 2
3. Substitute
1. S(n) = 1( 3 )^n-1 + 2( -1 )^n-1

Code

• line 10: Love how you can simultaneously assign variables from an array
• Line 36: This isn't a true quadratic formula. It takes advantage of the fact that a == 1in all cases  
• I added a master parse file 
• I love the ||= assignment, this is amazing. It will only assign the variable if it doesn't exist