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

	# PROJECT: Second Order Recurrence Relations
	$LOAD_PATH << '../lib'
	require 'parseFile.rb'
	class Sorr
	def initialize(inputs)
	s1 = inputs["S(1)"]; s2 = inputs["S(2)"]
	c1 = inputs['C1']; c2 = inputs['C2']
	r1,r2 = quadratic(c1,c2)
	puts "r1 = #{r1}"
	puts "r2 = #{r2}"
	unless r1 == r2
	q = ((s2 - (s1 * r1) ) / ( ( -r1 ) + r2 ))
	p = s1 - q
	puts "p = #{p}"
	puts "q = #{q}"
	puts "S(n) = (#{p})(#{r1})^(n-1) + (#{q})(#{r2})^(n-1)"
	for i in 1..10 do
	puts "S(#{i}) = #{(p*r1**(i-1) + q*r2**(i-1))}"
	end
	else
	p = s1
	q = ( s2 - p*r1 ) / r1
	puts "p = #{p}"
	puts "q = #{q}"
	puts "S(n) = #{r1}^(n-1) + #{q}(n-1)*#{r1}^(n-1)"
	for i in 1..10 do
	puts "S(#{i}) = #{r1**(i-1) + q*(i-1)*r1**(i-1)}"
	end
	end #unless
	end #initialize
	def quadratic(b,c)
	[ ( b + Math.sqrt(b**2 + 4 * c) ) / 2,
	( b - Math.sqrt(b**2 + 4 * c) ) / 2 ]
	end #quadratic
	end #class Sorr
	begin
	parsed = Master::ParseFile.new(Hash)
	if parsed.getFile.instance_of?(Hash) then Sorr.new(parsed.getFile) end
	end

view raw SORR.rb hosted with ❤ by GitHub