Introduction

Provided are some toy implementations for some basic computer science problems.

Tree data structures

• Node - references children nodes only
• ChildNode - references parent and children nodes
• Tree - tracks the root node; provides df_search and bf_search
• NaryTree - enforces number of children per node via child_slots
• BinaryTree - NaryTree with child_slots == 2; provides to_s
• CompleteBinaryTree - efficient Array implementation

Heap data structure

Implemented with a CompleteBinaryTree for storage using simple arithmetic to determine array indices for parent and children. See the heap example which can be executed (among other examples) via rake examples.

Both minheaps and maxheaps are supported. The primary operations are Heap#push and Heap#pop. My basic Vagrant VM gets around 500k pushes per second, constant up past 1M pushes.

Fibonacci functions

• Fibonacci.classic(n) - naive, recursive
• Fibonacci.cache_recursive(n) - as above, caching already computed results
• Fibonacci.cache_iterative(n) - as above but iterative
• Fibonacci.dynamic(n) - as above but without a cache structure
• Fibonacci.matrix(n) - matrix is magic; beats dynamic around n=500

Timer functions

• Timer.now - uses Process::CLOCK_MONOTONIC if available
• Timer.since - provides the elapsed time since a prior time
• Timer.elapsed - provides the elapsed time to run a block
• Timer.loop_avg - loops a block; returns final value and mean elapsed time

require 'compsci/timer'

include CompSci

overall_start = Timer.now

start = Timer.now
print "running sleep 0.01 (50x): "
_answer, each_et = Timer.loop_avg(count: 50) {
  print '.'
  sleep 0.01
}
puts
puts "each: %0.3f" % each_et
puts "elapsed: %0.3f" % Timer.since(start)
puts "cumulative: %0.3f" % Timer.since(overall_start)
puts


start = Timer.now
print "running sleep 0.02 (0.3 s): "
_answer, each_et = Timer.loop_avg(seconds: 0.3) {
  print '.'
  sleep 0.02
}
puts
puts "each: %0.3f" % each_et
puts "elapsed: %0.3f" % Timer.since(start)
puts "cumulative: %0.3f" % Timer.since(overall_start)
puts

running sleep 0.01 (50x): ..................................................
each: 0.010
elapsed: 0.524
cumulative: 0.524

running sleep 0.02 (0.3 s): ...............
each: 0.020
elapsed: 0.304
cumulative: 0.828

Fit functions

• Fit.sigma - sums the result of a block applied to array values
• Fit.error - returns a generic r^2 value, the coefficient of determination
• Fit.constant - fits y = a + 0x; returns the mean and variance
• Fit.logarithmic - fits y = a + b*ln(x); returns a, b, r^2
• Fit.linear - fits y = a + bx; returns a, b, r^2
• Fit.exponential fits y = ae^(bx); returns a, b, r^2
• Fit.power fits y = ax^b; returns a, b, r^2