Class slides week 11 WDI March

Computer_Science_Notes_6-3-13.markdown

Polymorphism

stackoverflow discussion

Subtype Polymorphism

  class Account
    attr_accessor :balance
    def initialize(balance)
      self.balance = balance
    end
    def interest
    end
  end

  class SavingsAccount < Account
    def interest
      balance * 0.06
    end
  end

  class CheckingAccount < Account
    def interest
      balance * 0.01
    end
  end

Create some accounts

  $ a = []
  $ a << SavingsAccount.new(10000)
  $ a << CheckingAccount.new(2500)

Calculate the total interest

  $ a.inject(0) {|total_interest, account| total_interest += account.interest}

Duck Typing

  class Document
    include ActiveModel::Conversion
  end

  class Video
    include ActiveModel::Conversion
  end

  class Audio
    include ActiveModel::Conversion
  end

  content = [Document.new, Video.new, Audio.new]
  puts content.to_json

Method Overloading

Doesnt fully exist in Ruby

  def do_stuff(cool_beans)
    puts cool_beans
  end

  def do_stuff(cool_beans, cool_bannans = nil)
    puts cool_beans
    puts cool_bannans if cool_beans
  end

Operator Overloading

  puts "this is" + " overloaded"
  => "This is overloaded"

  1 + 2 + 3
  => 6

  class Fixnum
    def +(arg)
      self - arg
    end
  end

  1 + 2 + 3
  => -4

Polymorphic Associations

Rails Guides Polymorphic Associations

  class Comment < ActiveRecord::Base
    belongs_to :commentable, :polymorphic => true
    belongs_to :user
  end

  class Artical < ActiveRecord::Base
    has_many :comments, :as => :commentable
  end

  class Product < ActiveRecord::Base
    has_many :comments, :as => :commentable
  end

  class User < ActiveRecord::Base
    has_many :comments
    has_many :acticles, :through => :comments, :source => :commentable, :source_type => 'Article'
  end

notes_6-4-13.markdown

Algorithms

Cool animated algorithms

What We'll Cover

• What is an Algorithm?
  • A step-by-step procedure towards a goal
  • Calculations, processing, reasoning
  • Equivalent of a function in mathematics
  • E.g. The bubble sort in week one was an algorithm

The Big O

• A means of reasoning about the complexity or cost of a function
• Memory or Time
• Generally measured in terms of time
  • How long with this algorithm take?
• Are not exact - ignores hardware and physical constraints
  • Benchmarking
• Gives a basis for comparison
• Used to measure the performance of a function in relation to its input size
  • how does this perform?
• Generally refrers to the worst-case scenario: often base-case performs much better
  • Plan for the worst, hope for the best!

O(1)

An algorithm is in constant time, O(1), if the complexity doesn't change significantly with size of the input

  x = 10
  y = 12

  if x > y
    1
  elsif x == y
    -1
  end

O(log n)

An algorithm is in logarithmic time, O(log n), if the complexity decreases as the input decreases such that T(n) = O(log n)

  def search(data, node)
    if node.nil? || data == node.data
      return node
    else
      search(data, node.left) || search(data, node.right)
    end
  end

O(n)

An algorithm is in linear time, O(n), if the complexity is proportional to the size of the input

  class Array
    def maximum
      self.each do |i|
        @maximum = i if @maximum.nil? or i > @maximum
      end
      @maximum
    end
  end

O(n**2)

An algorithm is in quadratic time, O(n2), if the complexity is proportianal to the square of the input, such that T(n) = O(n2)

  class Array
    def bubble_sort
      finnished = false

      while !finished
        self.each_with_index do |n, 1|
          pair = self[i, 2]
          if pair.first > pair.last
            self[i], self[i+1] = self[i+1], self[i]
            finnished = true
          end
          finnished = true
        end
      end
      self
    end
  end


  [1, 2, 3, 4, 5] 1

  [2, 1, 3, 4, 5] 1
   ^--^
  [1, 2, 3, 4, 5] 2

Inner loop will happen ruby n + n times

Insertion Sort

An O(n**2) algorithm for sorting lists

It works by comparing the subset of the list taht is already sorted with the next element, and finding the correct spot to place the element in the sorted list

1. Start with the first item in the list, considered to be sorted, the rest unsorted
2. Compare the next item in the list with the last sorted item: * If its larger or equal then take no action * If its smaller, then iterate over the sorted part of the list, looking for the rightful place in the sorted list (where it is less than the next sorted element) * Once found, make room for the new element by sifting all the subsquent elements in the sorted list along by one * Insert the element into the gap you just made
3. Repeat until all the elements are sorted

recursion.markdown

Recursion

What Is Recursion?

• A recursive method is a method that calls itself
• An application of "Divide and Conquer"
• Useful for cases where the size of the data is unknown
• Seeks to fulfil a 'base case' that determines once the recursive function is complete
• Potential for infinite loops!

Method calls and the Stack

• Everytime a method is called, it is pushed onto the Stack
• Therefore are generally less performant than iterative
• stack level too deep (SystemStackError) means too much recursion!

##Single Recursion Recursive function that generates 5! (e.g. 5 x 4 x 3 x 2 x 1)

  def factorial(i)
    i *= if i > 1
      factorial(i - 1)
    else
      1 # Hard-code 1 to avoid the infinite loop
    end
  end
  puts factorial(5)
  => 120

factorial(5)
          |
          ---> factorial(4)
                        |
                        ---> factorial(3)
                                      |
                                      ---> ....

factorial(5)
          |
 120       ---> factorial(4)
  ^                       |
  |-------------- 24      ---> factorial(3)
                  ^                      |
                  |-------------- 6      ---> ....
                                  ^             |
                                  |--------------

Multiple Recursion

Recursive function calls itself twice to calculate the Fibonacci sequence

  def fib(n)
    if n < 2
      return n
    else
      fib(n - 1) + fib(n - 2)
    end
  end

  def print_fib(start = 0, max = 35)
    print fib(start)
    print ", "
    print print_fib(start + 1) if start < max
  end

                  fib(3)=2
                    /\
                 1 /  \ 1
                  /    \
            fib(2)=1  fib(1)=1
                /\
             1 /  \ 0
              /    \
        fib(1)=1  fib(0)=0

Binary Trees

Binary Tree

• A data structure that consists of a group of nodes with up to two children
• A node stores one peice of data and a reference to its two child nodes
• A node without any child nodes is called a leaf node
• Many variations exist with their own properties
• Used to implement associative arrays e.g. Javascript Objects

Binary Search Tree

  class BinaryTree
    attr_accessor :root
    
    def insert_data(data)
      self.root = insert(data)
    end
    
    def insert(data, node = self.root)
      if node.nil?
        Node.new(data)
      else
        if data < node.data
          node.left = insert(data, node.left)
        else
          node.right = insert(data, node.right)
        end
        node
      end
    end

    def to_s
      self.root.to_s.squeeze(" ").strip
    end
  end

  class Node
    attr_accessor :data
    attr_accessor :left
    attr_accessor :right

    def initialize(data)
      self.data = data
    end

    def to_s
      [left,data,right].join(" ")
    end
  end