algorithms.md

computing: not knowing how to solve a specific problem but to create a series of steps

#recursion Uses stack - LIFO - puts a call on stack, which is a part of the memory

def sum(array)
  if array.empty?
    0
  else
    array[0] + sum(array[1..-1])
  end
end

factorial

def factorial(n)
  if n == 0
    1
  else
    n * factorial(n-1)
  end
end

multiply array

 def multiply_arr(arr)
   if arr.empty?
      0
   elsif !arr[0].is_a? Array
     p arr[0] * arr[0]
     multiply_arr(arr[1..-1])
   else
      multiply_arr(arr[0])
      multiply_arr(arr[1..-1])
   end
 end


# multiply_arr([1,2,3,[4,5],[6,7,8,9]])

reverse a string

def reverse(string)
  if string.empty?
    return ""
  else
    string[-1].to_s + reverse(string[0...-1])
  end
end

#benchmark

require "benchmark"

def factorial_recursive(n)
  if n == 0
    1
  else
    n * factorial_recursive(n-1)
  end
end

def factorial_loop(n)
  product = 0
  (1..n).each do |num|
    product *= num
  end
end

Benchmark.bm do|x|
  x.report do
    1000000.times {factorial_recursive(8)}
  end
end


Benchmark.bm do|x|
  x.report do
    1000000.times {factorial_loop(8)}
  end
end

#functional programming write immutable data, eg. recursive

#Big O Notation ##O(1) constant time regardless of input size

def method_1(array)
  array.size + 1
end
puts method_1([1,2,3]) #same run time as
puts method_1((1..10000000000))

##O(n) number of operations increase by number of input x

def method_2(array)
  array.each do |x|
    p x
  end
end

##array vs linked list

###Array. access: O(1); insert/delete O(n) -Disadvantage of array: not flexible when expanding size or inserting object in the middle of the array. -Advantage is that the size and the last element is easily calculated

###linkedlist. access: O(n); insert/delete O(1) -each block stores a pointer that points to the location of the next block. -Two blocks don't have to be adjacent in memory. -Disadvantage is that you have to iterate through each element to find the last element instead of doing a calculation on the memory size to find the last element like arrays can do.

##O(n;^2) 1 nested in a loop

##O(log(n)) log;_2 1024 = 10

jennli/algorithms.md