puts '-- PALINDROME -- '
# is word a palindrome?
def palindrome(s)
if s== nil or s.length == 0 or s.length == 1
ans = 'yes'
else
if s[0] == s[s.length-1]
ans = palindrome s[1..s.length-2]
else
ans = 'no'
end
end
end
# test
puts '<nil>' + ' ' + palindrome(nil)
puts '' + ' ' + palindrome('')
puts 'm' + ' ' + palindrome('m')
puts 'mm' + ' ' + palindrome('mm')
puts 'mom' + ' ' + palindrome('mom')
puts 'racecar' + ' ' + palindrome('racecar')
puts 'notapalindrome' + ' ' + palindrome('notapalindrome')
puts '-- FIBONACCI -- '
# fibonacci series
def fib(n)
if n == 0 or n == 1 then
1
else
fib(n-1) + fib(n-2)
end
end
#test
(0..20).each do |n|
puts 'n=' + n.to_s + ' fib=' + fib(n).to_s
end
puts '-- FACTORIAL - RECURSIVE -- '
# factorial
def fac(n)
if (n == 1 || n == 0) then
1
else
n * fac(n.abs-1)
end
end
#test
puts '-5' + '! = ' + fac(-5).to_s
puts '-4' + '! = ' + fac(-4).to_s
puts '0' + '! = ' + fac(0).to_s
puts '1' + '! = ' + fac(1).to_s
puts '3' + '! = ' + fac(3).to_s
puts '4' + '! = ' + fac(4).to_s
puts '5' + '! = ' + fac(5).to_s
puts '-- SQRT - BISCECTOR METHOD -- '
def sqrt_bisectormethod(n, epsilon)
ans = "Unable compute within " + epsilon.to_s
low = 0.0
high = [n, 1.0].max
guess = (low + high) / 2.0
100.times do
candidate = (guess ** 2)
if (candidate - n).abs < epsilon then
ans = guess
return ans
end
if candidate < n
low = guess
else
high = guess
end
guess = (low + high) / 2.0
end
ans
end
# test
[0.25, 0.5, 1,2,3,4,5,6,7,8].each do |n|
puts 'sqrt of ' + n.to_s + ' = ' + sqrt_bisectormethod(n, 0.0001).to_s + " (Math.sqrt =" + Math.sqrt(n).to_s + ')'
end
puts '-- SQRT - NEWTON RAPHSON METHOD -- '
def sqrt_newton_raphson(n, epsilon)
# equation: x^2 = 16 => y = x^2 - 16
# Find roots at y intercept: f(x) = y
# Find slope using derivatives at various points
ans = "Unable compute within " + epsilon.to_s
guess = n / 2.0
100.times do
diff = guess ** 2 - n
if diff.abs <= epsilon then
ans = guess
return ans
end
guess = guess - diff / (2.0 * guess)
end
ans
end
# test
[0.25, 0.5, 1,2,3,4,5,6,7,8].each do |n|
puts 'sqrt of ' + n.to_s + ' = ' + sqrt_newton_raphson(n, 0.0001).to_s + " (Math.sqrt =" + Math.sqrt(n).to_s + ')'
end
puts '-- EXPONENT - LINEAR -- '
def exp_linear(x, y)
ans = 1
1.upto(y) do |i|
ans *= x;
end
return ans
end
#test
puts '2^0=' + exp_linear(2, 0).to_s
puts '2^1=' + exp_linear(2, 1).to_s
puts '2^8=' + exp_linear(2, 8).to_s
puts '-- EXPONENT - RECURSIVE -- '
def exp_rec(x, y)
if y < 1
return 1
end
if y <= 1
return x
else
return x * exp_rec(x, y - 1)
end
end
#test
puts '2^0=' + exp_rec(2, 0).to_s
puts '2^1=' + exp_rec(2, 1).to_s
puts '2^8=' + exp_rec(2, 8).to_s
puts '-- EXPONENT - Log N -- '
def exp_logn(x, y)
if y < 1
return 1
end
if y == 1
return x
end
if ((y / 2) * 2) == y # even y
exp_logn(x*x, y/2)
else # odd y
x * exp_logn(x*x, y-1)
end
end
#test
puts '2^0=' + exp_logn(2, 0).to_s
puts '2^1=' + exp_logn(2, 1).to_s
puts '2^8=' + exp_logn(2, 8).to_s
puts '-- TOWERS OF HANOI -- '
def towers(size, fromTower, toTower, spareTower)
if (size == 1)
puts "Move disk from " + fromTower.to_s + " to " + toTower.to_s
else
towers size - 1, fromTower, spareTower, toTower
towers 1, fromTower, toTower, spareTower
towers size - 1, spareTower, toTower, fromTower
end
end
#test
puts "1 Disk"
towers 1, 1, 2, 3
puts "2 Disks"
towers 2, 1, 2, 3
puts "3 Disks"
towers 3, 1, 2, 3
puts "4 Disks"
towers 4, 1, 2, 3
puts '-- BINARY SEARCH -- '
# An example of "Divide and Conquer" algorithm
# Split problem into several sub-problems of the same type
# Solve each problem independently
# Combine intermediate results to arrive at the solution
# The INPUT must be PRE-SORTED
def bsearch(s, e, first, last)
if (last - first) < 2
return (s[first] == e or s[last] == e)
end
mid = first + (last - first) / 2
if s[mid] == e
return true
end
if s[mid] > e
return bsearch(s, e, first, mid - 1)
end
return bsearch(s, e, mid + 1, last)
end
def bsearchMain(s, e)
bsearch(s, e, 0, s.length - 1)
end
#test
puts '100 in []: ' + bsearchMain([], 100).to_s
puts '100 in [100]: ' + bsearchMain([100], 100).to_s
puts '1 in [1,2,3,4,100]: ' + bsearchMain([1,2,3,4,100], 1).to_s
puts '100 in [1,2,3,4,100]: ' + bsearchMain([1,2,3,4,100], 100).to_s
puts '3 in [1,2,3,4,100]: ' + bsearchMain([1,2,3,4,100], 3).to_s
puts '2 in [1,2,3,4,100]: ' + bsearchMain([1,2,3,4,100], 2).to_s
puts '4 in [1,2,3,4,100]: ' + bsearchMain([1,2,3,4,100], 2).to_s
puts '20 in [1,2,3,4,100]: ' + bsearchMain([1,2,3,4,100], 20).to_s
puts '-- BUBBLE SORT -- '
# O(n^2)
# Bubble the largest values to the end
def bubble_sort(l)
l.length.times do
0.upto(l.length - 2) do |i|
if l[i] > l[i+1]
temp = l[i]
l[i] = l[i+1]
l[i+1] = temp
end
end
end
l
end
#test
puts (bubble_sort []).inspect
puts (bubble_sort [1]).inspect
puts (bubble_sort [2,1]).inspect
puts (bubble_sort [2,1,6,4,3,5]).inspect
puts '-- BUBBLE SORT OPTIMIZED -- '
# still O(n^2)
def bubble_sort_opt(l)
swapped = true
while swapped
swapped = false # optimization - if no swapping happened, the rest of the list is already in order
0.upto(l.length - 2) do |i|
if l[i] > l[i+1]
temp = l[i]
l[i] = l[i+1]
l[i+1] = temp
swapped = true
end
end
end
l
end
#test
puts (bubble_sort_opt []).inspect
puts (bubble_sort_opt [1]).inspect
puts (bubble_sort_opt [2,1]).inspect
puts (bubble_sort_opt [2,1,6,4,3,5]).inspect
puts '-- SELECTION SORT -- '
# o(n^2)
# Keep track of minimum index and minimum value
# more efficient than bubble sort which has more swaps
def sel_sort(l)
0.upto(l.length - 1) do |i|
minIndex = i
minVal = l[i]
j = i + 1
while j < l.length
if minVal > l[j]
minIndex = j
minVal = l[j]
end
j += 1
end
temp = l[i]
l[i] = l[minIndex]
l[minIndex] = temp
end
l
end
#test
puts (sel_sort []).inspect
puts (sel_sort [1]).inspect
puts (sel_sort [2,1]).inspect
puts (sel_sort [2,1,6,4,3,5]).inspect
puts '-- MERGE TWO SORTED ARRAYS OF EQUAL SIZE -- '
def merge_sorted_arrays (l, r)
# l and r sorted lists
result = []
i=0
j=0
while i < l.length and j < r.length
if l[i] <= r[j]
result << l[i]
i = i + 1
else
result << r[j]
j = j + 1
end
end
# left over elements - i, j values incremented previously
while i < l.length
result << l[i]
i += 1
end
while j < r.length
result << r[j]
j += 1
end
result
end
#test
puts (merge_sorted_arrays [1, 3, 5], [2, 4, 6]).inspect
puts '-- MERGE SORT -- '
# Divide list into half
# Continue the list is a singleton
# Combine singleton lists in sorted order
# O
# / \
# O O
# / \ / \
# O O O O
# O(n) items to merge items each level
# There are O(log n) levels
# Total Complexity: O( n log n)
# Compared to Merge Sort,Hashing provides O(1)
def merge_sort(l)
if l.length < 2
return l
else
middle = l.length / 2
left = merge_sort l[0..middle-1]
right = merge_sort l[middle..l.length-1]
together = merge_sorted_arrays left, right
end
end
#test
puts (merge_sort [1]).inspect
puts (merge_sort []).inspect
puts (merge_sort [2,1]).inspect
puts (merge_sort [2,1,3]).inspect
puts (merge_sort [2,1,3,6,4,5]).inspect
# puts [1,2,3,4,5][0..2].inspect
puts '-- DECIMAL TO BINARY -- '
def dec_to_bin (dec)
continue = true
l = []
div = dec
while continue
remainder = div % 2
div = div / 2
l << remainder
if div < 1
continue = false
end
end
l.reverse.join
end
#test
puts 'dec 0 = ' + (dec_to_bin 0)
puts 'dec 1 = ' + (dec_to_bin 1)
puts 'dec 2 = ' + (dec_to_bin 2)
puts 'dec 4 = ' + (dec_to_bin 4)
puts 'dec 8 = ' + (dec_to_bin 8)
puts 'dec 29 = ' + (dec_to_bin 29)
puts 'dec 100 = ' + (dec_to_bin 100)
puts '-- BINARY TO DECIMAL -- '
def bin_to_dec(bin)
dec = 0
pos = bin.length - 1
bin.split("").each do |i|
dec += 2**pos * i.to_i
pos -= 1
end
dec
end
#test
puts 'bin 0 = ' + bin_to_dec("0").to_s
puts 'bin 1 = ' + bin_to_dec("1").to_s
puts 'bin 10 = ' + bin_to_dec("10").to_s
puts 'bin 100 = ' + bin_to_dec("100").to_s
puts 'bin 1000 = ' + bin_to_dec("1000").to_s
puts 'bin 11101 = ' + bin_to_dec("11101").to_s
puts 'bin 1100100 = ' + bin_to_dec("1100100").to_s
puts'bin_to_dec(dec_to_bin(12345345)) = ' + bin_to_dec(dec_to_bin(12345345)).to_s
