Data Structure Skillboost exercises

binary.rb

## SOLUTION

def binary(value, data, low, high)
  center = low + (high - low) / 2 # C
  if center < low # C
    nil # C
  elsif data[center] == value # C
    center # C
  elsif data[center] > value # C
    binary(value, data, low, center - 1) # T(n/2) + C
  else
    binary(value, data, center + 1, high) # T(n/2) + C
  end
end

# The time complexity function of this recursive method can be obtained
# using the following recurrence:
#
#       / C for n <= 1
# T(n) {
#      \  C + T(n/2) for n > 1

# Solving the recurrence
# T(n) = C + T(n/2)
#      = C + C + T(n/4)
#      = C + C + C + T(n/8)
#      = C + C + C + T(n/2^3)
#      = Ci + T(n/2^i)

# What value of i would get us to T(1)?
# 2^i = n
# Math says that 
# i = log2n

# So we know that the recurrence will converge at log2n
# This means that the time complexity function for binary search is:

# T(n) = Clog2n + C

# And the Time Order of the Algorithm is:
# O(n) = log2n

factorial.rb

## SOLUTION

def factorial(n)
  if n <= 1 # C
    1 # C
  else
    n * factorial(n-1) # C + T(n-1)
  end
end

# The time complexity function of this recursive method can be obtained
# using the following recurrence:
#
#       / C for n <= 1
# T(n) {
#      \  C + T(n-1) for n > 1

# Solving the recurrence
# T(n) = C + T(n-1)
#      = C + C + T(n-2)
#      = C + C + C + T(n-3)
#      = Ci + T(n-i)

# What value of i would get us to T(1)?
# i = n-1

# So we know that the recurrence will converge at n -1
# This means that the time complexity function for factorial is:

# T(n) = C(n-1) + C
# T(n) = Cn - C + C
# T(n) = Cn

# And the Time Order of the Algorithm is:
# O(n) = n

mat_prod.rb

## SOLUTION

def matrix_product(matrix_a, matrix_b)
  if matrix_a.size != matrix_b.size # C
    raise "Incompatible Matrices" # C
  else
    n = matrix_a.size # C
    result = Array.new(n) { Array.new(n) { 0 } } # Cn^2

    for i in (0...n)
      for j in (0...n)
        for k in (0...n)
          result[i][j] = result[i][j] + matrix_a[i][j] * matrix_b[k][j] # Cn^3
        end
      end
    end

    result # C
  end
end

# Since we have a conditional, we take the path of highest weight
# T(n) = C + C + Cn^2 + Cn^3 + C
# T(n) = C + Cn^2 + Cn^3

# And the Time Order of the Algorithm is:
# O(n) = n^3

mergesort.rb

def mergesort(data)
  if data.size == 1
    data[0]
  else
    # split is O(c)
    first_half, second_half = split(data)
    # merge is O(n)
    merge(mergesort(first_half), mergesort(second_half))
  end
end

only_odds.rb

## SOLUTION

def only_odds(n)
  x, y = 0, 0 # C

  for i in (1..n)
    if i % 2 == 0 # C
      for j in (i..n)
        x += 1 # C
      end

      for j in (1..i)
        y += 1 # C
      end
    end
  end
end

# This example has some special characteristics
# The conditional in line 7 can be safely considered as something that's
# goint to happen n/2 times.
# Both loops in line 8 and 12 also have special characteristics
# one of them decreases linearly with succesive iterations of i
# while the other one increases linearly.

# The number of operations for both loops 8 and 12 is going to end up
# being n + 1 per iteration of i

# This means that the time complexity function for this Algorithm is:

# T(n) = C + Cn*(n+1)/2
# T(n) = C + (Cn^2)/2 + Cn/2
# T(n) = C + Cn^2 + Cn/2

# And the Time Order of the Algorithm is:
# O(n) = n^2

special.rb

## SOLUTION

def special(n)
  for i in (1...n)
    for j in (i + 1..n)
      for k in (1..j)
        print "i: #{i}, j: #{j}, k: #{k}" # C
      end
    end
  end
end

# To get the time complexity function of this method, it's easier to
# use summations

# NOTE: For ease, I'll write the summations in the same syntax that would be used to
# solve them in a texas instrument

# T(n) = ∑( ∑( Cj, j, i + 1, n), i, 1, n-1)
# And because of math, this is equal to:

# T(n) = Cn * (n^2 - 1)/3
#      = C/3 * n^3 - C/3 * n
#      = Cn^3 - Cn

# And the Time Order of the Algorithm is:
# O(n) = n^3

special_recursion.rb

## SOLUTION

def special_recursion(n)
  if n <= 1 # C
    1 # C
  else
    special_recursion(n - 1) + special_recursion(n - 1) # C + 2T(n-1)
  end
end

# The time complexity function of this recursive method can be obtained
# using the following recurrence:
#
#       / C for n <= 1
# T(n) {
#      \  C + 2T(n-1) for n > 1

# Solving the recurrence
# T(n) = C + 2T(n-1)
#      = C + 2(C + 2T(n-2))
#      = C + 2(C + 2(C + 2T(n-3)))
#      = C + 2C + 4C + 8T(n-3)
#      = 2^0*C + 2^1*C + 2^2*C + 2^3*T(n-3)
#      = 2^0*C + 2^1*C + 2^2*C + ... + (2^i-1)*C + 2^i*T(n-i)
#      = ∑(2^k*C, k, 0, i-1) + 2^i*T(n-i)

# After solving the first factor of the previous expression we get:
# T(n) = 2^i*C - 1 + 2^i*T(n-i)

# At what value of i will the recurrence converge?
# i = n - 1

# Substituting i
# T(n) = 2^(n-1) * C + 2^(n-1) * C
#      = 2 * (2^(n-1) * C)
#      = 2^n*C

# And the Time Order for the Algorithm is:
# O(n) = 2^n