Iteration vs. Recursion

Code

def factorial_iter(n):
    num = 1
    while n >= 1:
        num = num * n
        n = n - 1
    return num
   
def factorial_recur(n):
    if n == 1:
        # base case that stops recursion
        print ('  return 1 (this is the top of the stack)')
        return 1
    else:
        print ('  return ' + str(n) + '*' + 'factorial_recur(' + str(n-1) + ')')
        # the function is calling ITSELF
        return n * factorial_recur(n-1)
       
number = 5

print ('-' * 20)
print ('Using Iteration. Factorial of ' + str(number))
print ('-' * 20)
print (str(factorial_iter(number)))

print (' ' * 20)

print ('-' * 20)
print ('Using Recursion. Factorial of ' + str(number))
print ('-' * 20)
print ("factorial_recur: stack trace")
print ("Note how the function calls itself. This is no different than calling another function")
print ("It is called RECURSION because the function is calling ITSELF")
print ("When it reaches the BASE CASE (n==1), it stops calling itself")
print ("The function MUST stop calling itself at some point, otherwise it will never end (likely run of out memory)")
print ("The innermost function call is evaluated first, where n=1 and then return 2 * 1, then return 3 * 2, and so on")
print ("This is called unwinding of the stack. Start from the BOTTOM and evaluate upwards. Think of a function evaluation as follows.")
print ("(5 * (4 * (3 * 2) * (1)))")
print ("Stack trace")
print (str(factorial_recur(number)))

Output

--------------------
Using Iteration. Factorial of 5
--------------------
120
                   
--------------------
Using Recursion. Factorial of 5
--------------------
factorial_recur: stack trace
Note how the function calls itself. This is no different than calling another function
It is called RECURSION because the function is calling ITSELF
When it reaches the BASE CASE (n==1), it stops calling itself
The function MUST stop calling itself at some point, otherwise it will never end (likely run of out memory)
The innermost function call is evaluated first, where n=1 and then return 2 * 1, then return 3 * 2, and so on
This is called unwinding of the stack. Start from the BOTTOM and evaluate upwards. Think of a function evaluation as follows.
(5 * (4 * (3 * 2) * (1)))
Stack trace
  return 5*factorial_recur(4)
  return 4*factorial_recur(3)
  return 3*factorial_recur(2)
  return 2*factorial_recur(1)
  return 1 (this is the top of the stack)
120

Approaches to solving computational problems

Given a computational problem, we need to determine the most appropriate approach.

Can the problem be solved analytically?

Say we need to find whether a given list is pre-sorted. We can solve this problem analytically by walking through the list and check if each subsequent list item is larger than the previous list item.

Say we are given a knapsack problem. We can solve such a problem by enumerating through all choices and picking the choice with the most optimal result. To optimize the processing time, we can employ Dynamic Programming.

If not, take a random walk

Can we determine the location of an ant on a Cartesian plane? Since we cannot predict which way an ant will move, we will need to resort to simulation to come up with a likely answer. Simulation is useful for:

• Problems that cannot be solved analytically
• We cannot enumerate all possibilities

We can use simulation, commonly referred to as Monte Carlo Simulation.

• Generate a sample representation of Scenarios
• Run the experiment several times
• Collate results

The results so obtained are Stochastic.

• The results are descriptive, not prescriptive i.e. they explain how things are in the experiment and not necessarily how they are supposed to be
• We can plot results to come with up an approximation of the result
• Not a technique to come up with an optimal solution but the simulation results can be used to help with optimization

The simulation is based on Inferential Statistics - random sample tends to exhibit the same behavior as the general population. For example, if we flip a coin numerous time, we expect a 50-50 head-tail result as an aggregate. By making more runs the results become more predictable.

If simulation can explain current behavior, can it predict future behavior?

• Statistical validity does not guarantee correctness of the result. For example, the assumptions behind the simulation may be incorrect to begin with.
• Always do a sanity check by comparing simulation results with physical reality.

Deterministic Simulation

With deterministic simulation, the same result is obtained from each run.

Facets of Simulation

• Static vs Dynamic (i.e. time plays role, for example, queing of requests in a network)
• Discrete (behavior of single entity) vs Continuous (flow of traffic, for example)
• Random walk (a Monte Carlo simulation) is dynamic, stochastic, and discreet

Estimate value of Pi using simulation

Even though Pi is not a random number, random walk simulation (stochastic) can be used to calculate value of Pi as first shown by Buffon, Laplace.

Π is a constant that is the ratio of circumference of a circle to its diameter.

Area of circle = Π r ²
Circumference = 2 Π r = Π d

• Take a unit circle and inscribe quarter of a circle in it. The radius of this circle is 1.
• Area under the arc is shaded.
• Throw darts at the square.
• Intuition suggests that the darts that land in the shaded area are in proportion to shaded area over the total area.
• darts in shaded area / total darts = shaded area / total area of square

Hit ratio = h = (Π r ² / 4) /  r ²

• Divided shaded area by 4 because we are dealing with quarter of a circle
• Numerator is the shaded area; denominator is the total area of the square

Simplifying,
Π = 4h

• In a computer program, get random x, y coordinates such that 0 <= x <=1 and 0 <= y <= 1.
• Get the random coordinates n number of times (simulating n darts thrown)
• Determine whether the coordinate is in the shaded region by calculating the distance of the coordinate from the center. If  the distance is less or equal to the radius (1 in case of unit circle), the dart is in the shaded region.

Using Pythagorean theorem, distance is the length of the hypotenuse.
d = √  (x ²+ y ²)

if d <= 1, the dart is in the shaded area.

Calculate hit ratio,
h = (num darts in shaded region) / (total darts thrown)

To arrive at the value of Π,
Π= 4h

Run the simulation many times and average the results. When simulation yields a value that does not change much (for required floating point accuracy), we have a good estimate of Π.

Dynamic Programming Algorithm

Given

•  0,1 Knapsack problem

Assuming

• We can divide the problem into optimal sub-structures 
• And there are overlapping solutions to the sub-structures

Problem

• We have n objects
• Each object has value, V
• Each object has weight, W
• We need to pick k items such that:
• We maximize the total value, TV, of k items picked
• But the total weight, TW, of the k items picked must be under a maximum weight limit of MW

Approach

• Since we have n items, we will need to evaluate value of all possible combinations of n items while maximizing value but still remaining under the maximum weight limit
• n items yield 2ⁿ combinations. Therefore, the complexity of this approach is O(2ⁿ)
  00000001
  00000010
  ...
  11111111
• Start a the tree with last item in the vector and move backwards in the vector
• Build a decision tree, depth-first, left-first where the left branch is the "don't take" branch
• When a node terminates (no more options), backtrack to the previous (upwards) nodes and complete the other branches

Example

∑_i=1ⁿ P_iX_i

where X_i is a vector of zeros and ones denoting whether an item is picked or not and P_i is the price or value of the item.

∑_i=1ⁿ W_iX_i <= C
where C is the maximum weight (constraint) and Wi is the weight of an item.

Additional constraints such as volume can be added to this algorithm.
∑_i=1ⁿ V_iX_i <= V_max
where V_max is the maximum volume (constraint) and Vi is the volume of an item.

Objective is the maximize the value!

Indices = [0, 1, 2]
Weights = [5, 3, 2]
Values = [9, 7, 8]

Constraint, MW = 5

The nodes represent a tuple of (index, capacity_remaining, cumulative_value)

Brute Force O(2ⁿ)

def solution_brute(w, v, i, aW)
$numCalls += 1
# puts 'called with index: ' + i.to_s + ' aW: ' + aW.to_s

if i == 0
if w[i] <= aW
return v[i]
else
return 0
end
end

without_i = solution_brute(w, v, i-1, aW)

if w[i] > aW 
return without_i
else
with_i = v[i] + solution_brute(w, v, i-1, aW - w[i])
end

[with_i, without_i].max
end

# Test
puts '----------------------------'
weights = [5, 3, 2]
values = [9, 7, 8]
startIndex = 2
aW = 5
$numCalls  = 0;
puts 'Weights: ' +  weights.inspect
puts 'Values: ' +  values.inspect
puts 'Optimal Value: ' +  (solution_brute weights, values, startIndex, aW).inspect
puts 'Total calls: ' + $numCalls.to_s
puts '----------------------------'

puts '----------------------------'
weights = [5, 3, 2, 4, 3, 6, 4, 2, 5, 3, 2, 4, 3, 6, 4, 2 ]
values = [9, 7, 8, 6, 5, 4, 3, 2, 9, 7, 8, 6, 5, 4, 3, 2 ]
startIndex = 15
aW = 21
$numCalls  = 0;
puts 'Weights: ' +  weights.inspect
puts 'Values: ' +  values.inspect
puts 'Optimal Value: ' +  (solution_brute weights, values, startIndex, aW).inspect
puts 'Total calls: ' + $numCalls.to_s
puts '----------------------------'

Result
----------------------------
Weights: [5, 3, 2]
Values: [9, 7, 8]
Optimal Value: 15
Total calls: 7
----------------------------
----------------------------
Weights: [5, 3, 2, 4, 3, 6, 4, 2, 5, 3, 2, 4, 3, 6, 4, 2]
Values: [9, 7, 8, 6, 5, 4, 3, 2, 9, 7, 8, 6, 5, 4, 3, 2]
Optimal Value: 49
Total calls: 21162
----------------------------

Optimized using Memoizatation O(n.s)

def solution_memo_helper(w, v, i, aW, m)
$numCalls += 1
# puts 'called with index: ' + i.to_s + ' aW: ' + aW.to_s

if m[[i, aW]] != nil
#puts 'found in memo'
return m[[i, aW]]
end

if i == 0
if w[i] <= aW
m[[i, aW]] = v[i]
return v[i]
else
m[[i, aW]] = 0
return 0
end
end

without_i = solution_memo_helper(w, v, i-1, aW, m)

if w[i] > aW 
m[[i, aW]] = without_i
return without_i
else
with_i = v[i] + solution_memo_helper(w, v, i-1, aW - w[i], m)
end

res = [with_i, without_i].max
m[[i, aW]] = res
res
end

def solution_memo(w, v, i, aW)
m = {}
return solution_memo_helper w, v, i, aW, m
end

# Test
puts '----------------------------'
weights = [5, 3, 2]
values = [9, 7, 8]
startIndex = 2
aW = 5
$numCalls  = 0;
puts 'Weights: ' +  weights.inspect
puts 'Values: ' +  values.inspect
puts 'Optimal Value: ' +  (solution_memo weights, values, startIndex, aW).inspect
puts 'Total calls: ' + $numCalls.to_s
puts '----------------------------'

puts '----------------------------'
weights = [5, 3, 2, 4, 3, 6, 4, 2, 5, 3, 2, 4, 3, 6, 4, 2 ]
values = [9, 7, 8, 6, 5, 4, 3, 2, 9, 7, 8, 6, 5, 4, 3, 2 ]
startIndex = 15
aW = 21
$numCalls  = 0;
puts 'Weights: ' +  weights.inspect
puts 'Values: ' +  values.inspect
puts 'Optimal Value: ' +  (solution_memo weights, values, startIndex, aW).inspect
puts 'Total calls: ' + $numCalls.to_s
puts '----------------------------'

Result
----------------------------
Weights: [5, 3, 2]
Values: [9, 7, 8]
Optimal Value: 15
Total calls: 7
----------------------------
----------------------------
Weights: [5, 3, 2, 4, 3, 6, 4, 2, 5, 3, 2, 4, 3, 6, 4, 2]
Values: [9, 7, 8, 6, 5, 4, 3, 2, 9, 7, 8, 6, 5, 4, 3, 2]
Optimal Value: 49
Total calls: 438
----------------------------

Comparison

Comparing the brute force verses memoized version of the algorithm, the following observations are made.

• Forthe second test case (16 items), with brute force 21,162 method calls were required to come up with an optimal solution
• For the second test case (16 items), with memoized approach only 438 method calls were required to come up with an optimal solution
• The efficiency gained with the memoized approach is at the expense of additional space required for memo entries. We have traded space for time.
• The complexity of the memoize approached is not strictly polynomial in the size of the input but rather in the size of the input, n, as well as the size of the solution, s. Such is the case because the eventual work done by the method is partly dependent on how many items are selected to come up with an optimal solution.

Solving Optimization Problems using Dynamic Programming

Examples

• Shortest path - Minimize Time, Distance; constraint drive under speed limit, avoid toll roads
• Traveling Sales Person (TSP) - Required to fly to a set of cities and return to origin. Find flights that minimize total fare.
• Bin Packing - What items to put in the bin and in what order (shipping domain)
• Sequence Alignment - Align DNA/RNA sequence
• Knapsack Problem - Backpacking, what items will fit in the backpack while maximizing the value of items in the pack

Optimization Problem

• A function to maximize or minimize
• A set of constraints to adhere to

The common theme among all these problems is that we have some function to minimize or maximize subject to some constraint. For example, in case of the shortest path problem we may wish to minimize the distance, or travel time subject to constraints such as not taking any toll roads.

Discrete vs. Non-Discrete Knapsack problems

In a non-discrete knapsack problem, the items are arbitrarily divisible into smaller quantities (for example, gold dust). In discrete, also called 0,1 knapsack problems, the items are not divisible into arbitrary quantities (for example, gold bricks).

Greedy Algorithm

In a greedy algorithm, we pick the most valuable item first. Greedy algorithm does not always yield the best solution but most of the time it does. In other words, locally optimal descisions (first pick, second pick,...) does not necessarily result in a globally optimal solution.

Brute force

In brute force algorithm, we conduct a exhaustive enumeration and valuation of all possibilities to come up with the best solution.

∑_i=1ⁿ P_iX_i

where X_i is a vector of zeros and ones denoting whether an item is picked or not and P_i is the price or value of the item.

∑_i=1ⁿ W_iX_i <= C
where C is the maximum weight (constraint) and Wi is the weight of an item.

Given 8 items, possible selections are as follows.
Pi  to P8
00000000
00000001
00000011
..
11111111

Number of possible combinations are 2⁸= 256
Therefore, to solve this sort of problem with brute force will require an exponential algorithm!

Dynamic Programming

• Careful brute force
• Divide problem into sub-problems; solve sub-problems; use results of sub-problems to solve the bigger problem; there must be overlapping sub-problems and optimal sub-structures
• Sub-problems must be acyclic (otherwise stuck in endless loop)
• Recursion + memoization + guessing (best guesses)

Solving Optimization Problems

There are preexisting dynamic programming algorithms. Map new problem to an old problem that has been solved and use a proven algorithm.

Using the Scientific Method and Bisection for Debugging Software

Scientific Method

1. Study available data (test results, and program text with a critical eye). Ask: what could have gone wrong?
2. Form a hypothesis as to why the program did not behave it should have based on the analysis of available data
3. Design and run a repeatable experiment (write a test)
4. The experiment must have the potential to refute the hypothesis - If the experiment is not capable of proving the hypothesis incorrect, it is of no use!
5. The expected (correct) result of the experiment must be established before the test
6. Run the experiment and check if it meets the expectation

Debugging

• Approach debugging systematically
• The objective is to reduce the search space - i.e. amount of the source code and data we need to look at to find the source of problem
• Use bisection (as used in binary search) to reduce the search space. Start around the middle of search space (source code and/or data).
• Establish in which section of the bisected search space does the root cause of the problem lie
• Repeat the bisection process in the selected section
• By using this approach we reduce the search space into half with each attempt thus getting to root cause in a systematic, and efficient manner

What to look for

1. Order of arguments passed to a method
2. Initialization of variables, especially the ones used in a loop. Did you intend to initialize these inside or outside the loop?
3. Comparison of objects and values. Did you intend the reference (address) or value?
4. Are multiple variables pointing to the same object and perhaps changing the object.
5. Look for side-effects. Is the method being called changing the arguments passed in?
6. When copying objects, did you intend to make shallow or deep copy of the object?
7. Do not exclusively rely on the code comments. Read the code.
8. Reconsider the assumptions. Are you looking at the correct part or version of the code? Are you using the right data to reproduce the problem?
9. Walk away and take a fresh look later
10. Don't rush to fix the bug. Look closely at the nature of the bug. Is is spread among other portions of the code. Does fixing this bug introduce other bugs? Are you adding a lot of code to fix the bug? Should you first clean up and refactor?

Comparing algorithms based on their complexity

Given

An unsorted list of items

Objective

Find a given item in the list

Algorithmic choices

Linear Search

Traverse the unsorted list from the beginning to the end to find a given item. The complexity of this algorithm is O(n)

Binary Search

• In order to perform a binary search, we must first sort the list.
• To sort the list, we have to look at each element at least once hence we will at least have O(n). At best, we can compare and rearrange elements in log n time. Therefore, the sorting will be order of O(n log n)
• Once sorted, we can find the desired item in log n time using binary search.
• Therefore, the sort and search will be of order O(n log n + log n)

Comparison

Which algorithm performs better?

Let's say we want to search the list k times.

• Linear Search is O(k.n)
• Sort and Binary Search is O (n log n + k log n)

Conclusion

• If we were to search the list only once (k = 1), the Linear Search performs better.
• However, if we were to search the list multiple times (k > 1), the Sort and Binary Search solution works better.

Computing Efficiency - Order of Growth

What is efficiency?

• How quickly does an algorithm execute as the problem input grows?
• Some problems can be solved very quickly despite the size of the input; other problems take longer and longer time to solve as the size of the input; the growth can be linear, quadratic, or exponential.
• Algorithms belong to different classes based on their efficiency.
• Given a problem, map the problem to an existing algorithm to predict the computing efficiency
• Efficiency is not measured in terms of time and space required to solve the problem on a particular machine or programming language.
• Efficiency is measured in terms of space and time required to solve a problem using the basic primitive steps of a computing machine.

Space

Space is the amount of memory used by algorithm to solve the problem, for example, memory used by variables and data structures excluding memory used by the input. Amount of time required to access any portion of memory (RAM) is considered to be a constant.

Time

Time required to solve a problem is measured in terms of basic primitive steps needed to solve the problem. The basic primitive steps are arithmetic, logical, comparisons, memory access, and other built-in operations of the machine.

For a solution to each problem, there are three scenario.

1. Best Case
2. Worst Case
3. Expected Case (average)

We usually focus on the worst case scenario when evaluating the efficiency of a solution to the problem. It is usually not possible to know the expected (average) case since the entire distribution for time and space required to solve the problem is unknown for all inputs.

Complexity

We try to map a given problem to an algorithm of known complexity to predict performance. We use classes of complexity to different efficiencies.
Given a problem:

1. Identify basic steps to solve the problem
2. Establish the relationship between the size of the input and the number of basic steps required to process the input
3. Focus on the worst case scenario since we are interested in asymptotic growth meaning we are interested in considering the performance of algorithms for very large input datasets

There are four major classes of complexity.

1. Linear - the time required grows in direct proportion to the size of input
2. Logarithmic - the time required grows with size of input but is reduced by some multiple of the input
3. Quadratic - the time required to solve problems grows with input size that comprises of two loops, m and n (an outer loop and an inner loop)
4. Exponential - the time required to solve the problem increases at a very high rate compared to increase in size of input

Linear O(n)

Let's say a problem requires the number of basis steps expressed by the following equation.
2 + 3b

• The problem requires 2 steps for any size of input plus the size of input times 3
• 2 is the additive constant
• 3 is the multiplicative constant
• Since we are interested in asymptotic growth, the additive and multiplicative constants are immaterial

Therefore, the equation can be simply reduced to the following.
b
The asymptotic notation frequently used to describe complexity is called Big O notation. The Big O notation provides an upper bound on the growth rate of the function. In Big O notation, linear algorithms are denoted as O(n).
Let say we have a algorithm represented by f(x). If the is algorithm is determined to be of linear complexity, the following holds true.
f(x) ∈ O(n)
f(x) is a element of class of algorithms of linear complexity.

Logarithmic O(log n)

How do we calculate exponentiation of a number? Say we want to calculate, 2^500. We can multiply out 2, 500 times (2*2*......*2). The complexity of this algorithmic approach would be linear. However, there is a shortcut to calculating exponentiation.
a^b = (a*a)^(b/2) when b is even
a^b = a * (a ^ (b-1) when b is odd
By using this algorithm, we have cut down the steps required into half. Thus, the complexity of this algorithm is log₂ b.
Binary search of a sorted list is another example of an algorithm of logarithmic (sub-linear) complexity.

Quadratic O(n²)

The general structure of these kinds of algorithm involve an inner loop and an outer loop.
For m=1 to 500
  For n=1 to 200
     <do something>
The number of steps required to solve such a problem is approximately m * n. In the worst case scenario, m = n, hence the complexity of the algorithm approaches O(n²).

Exponential O(2ⁿ)

For problems such as Knapsack, Traveling Salesman, and Towers of Hanoi fall into a class of problems that require time that is exponential in relation to the size of input.

Aside: O(1) are algorithms that execute in the same time (or space) regardless of the size of the input.

Comparison

• Let's say we have an input size, n, of 1000
• Let's assume we need to perform one basic operation for each input
• Let's further assume we require one nano second for each operation

Now let's try to solve this problem using an algorithm from each class of complexity. In fact, we do not need to write any code to predict the performance. We can deduce the performance from the order growth for each class of complexity as follows.

• Logarithmic - log₂ 1000 is 9.96 or the algorithm will require about 10 nano seconds
• Linear - will require 1 micro second (1000 * 1/1,000,000,000)
• Quadratic - will require 1 milli second (1000 * 1000 * 1/1,000,000,000)
• Exponential - will require 10^285 years!

Aside: Linear algorithms are not always faster than quadratic algorithms.

Finite State Machines (FSM)

• Each circle represents a state
• Circle with double-lines represents a terminal-successful state
• From each circle, there can only be one arrow for a given input (i.e. there cannot be two arrows labeled 0's or 1's) from a given state
• An arrow to the state itself leaves the state unchanged
• Each input transitions the state from one state (circle) to another
• When a "Dead" state is reached, the input string never reaches a terminal-successful state
• The machine terminates when there is no more input

• Binary Numbers that are divisible by 4 end in 00

Computational Models

Computational models in the order of increasing computing power they wield.

1. Finite State Machines (FSM)
2. Context free languages
3. Turing Machines
4. Undecidables

Finite State Machines (FSM)

To solve certain set of problems, e.g. is there a zero at the end of string.

Context free languages

A set of strings is a language. More powerful than FSM. Can tell whether a given set of strings is a valid program.

Turing Machines

Anything that can be computed can be computed with a Turing Machine. Includes P and NP problems.

Undecidables

Problems that cannot be solved with a computer.

Common Algorithms - Ruby implementation

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

Computer Languages

All computer languages, regardless of syntax, are built on the following foundation.

1. Data

All languages support number, string, and boolean data types. Other data types can be built on top of or by composing these data types (for example, into classes).

2. Operations

All languages support basic arithmetical (+, -, *, /) and boolean (and, or, not) operations.

3. Commands

All languages provide commands such as:

• Assignments of data to memory locations (variables)
• Input and output to various devices (screen, printer, etc.)
• Conditional statements to make decisions
• Loops and iterations to perform the same task repetitively

Any computer language that supports the above facility is Turing complete meaning the language can perform any computation that is possible with any other computing language.

Complex data types

Complex data types are built from primitive data types.

Tuple

• An immutable, ordered sequence of elements. 
• (1, 3, 5)
• Strings is an immutable ordered sequence of characters.

List

• A mutable, ordered sequence of heterogeneous elements. 
• [1, "astring", ["another", "list", "within"]]

Dictionaries

• A mutable, un-ordered container for key-value pairs
• Generalizes indexing - keys are hashed, and a value can be looked up by providing a key
• {'Chicago': 'Illinois', 'Sacramento': 'California', 'jack': 800}

Functional Programming

What is it?

Functional programming is a programming paradigm. It is a style of building the structures and elements of computer programs.

How it works?

Treat computation as the evaluation of mathematical functions. Functions can be chained, passed as parameters to other functions, and higher order functions can be composed from other functions.

Immutable

Functions avoid changing-state. They take in input and return out without changing input or any other global state.

Declarative

Functions are declarative. Function signature states what it needs for input and is clear about it returns. How the action is actually performed is encapsulated by the function and is of really interest to the user of the function.

Pure

Functions don't depend on any data other than what is passed in, and don't alter data other than what they returned. Return the same result for the parameter passed in.

// Not pure because the return value is different based on today's date
function daysTil(Date targetDate){
  // returns days til targetDate from now
}

// Pure because the return value is always the same regardless of today's date
function daysTil(Date targetDate, Date nowDate){
  // returns days til targetDate from nowDate
}

Characteristics

• Functional programming is inspired by Lambda calculus
• Functions are first-class citizens
• Functions can be assigned to variables
• Functions can be passed to other functions
• Functions can be returned from other functions
• Functions can accept other functions as arguments; the function accepting the argument is called a higher-order function
• Data is typically immutable, therefore, concurrent threads can access data without locking
• Pure functions are functions that always return the same result when same arguments are passed in
• Pure function have no side-effects i.e. they do not change any global state such as performing I/O
• Pure function can be executed over and over without affecting the global state
• Pure function, due to their very nature of not having side-effects, are well-suited for concurrent execution of code

Dynamic Programming

Dynamic programming (DP) is a style of programming suited for combinatorial optimization (for example, the knapsack problem). Instead of using brute force to try every possible combination to solve a problem, an implementation based on dynamic programming optimizes the solution by computing and caching intermediate results in order to avoid redundant computations. Recursion can be used exclusively to solve such a problem but at a higher computational cost.
Let's calculate a couple of members in the Fibonacci series using recursion and DP.

Fibonacci sequence

F_n = F_n-1 + F_n-2

1, 1, 2, 3, 5, 8, 21, ...

where the next number in the sequence is the sum of the previous two numbers.

Objective

Calculate the sixth and seventh number in the Fibonacci series. The corresponding numbers in the series are 8 and 21.

Fibonacci sequence using recursion

public int Calculate(int n)
{
    if (n <= 2)
        return 1;
    else
        return Calculate(n - 1) + Calculate(n - 2);
}

Call Stack - Calculate(6)

Calculate(6)
Calculate(5)
Calculate(4)
Calculate(3)
Calculate(2)
Calculate(1)
Calculate(2)
Calculate(3)
Calculate(2)
Calculate(1)
Calculate(4)
Calculate(3)
Calculate(2)
Calculate(1)
Calculate(2)

Call Stack - Calculate (7)

Calculate(7)
Calculate(6)
Calculate(5)
Calculate(4)
Calculate(3)
Calculate(2)
Calculate(1)
Calculate(2)
Calculate(3)
Calculate(2)
Calculate(1)
Calculate(4)
Calculate(3)
Calculate(2)
Calculate(1)
Calculate(2)
Calculate(5)
Calculate(4)
Calculate(3)
Calculate(2)
Calculate(1)
Calculate(2)
Calculate(3)
Calculate(2)
Calculate(1)

The Issue - Inefficiency

As n increases, so do the number of recursions to solve the problem. Compare the number of calls to Calculate() method in the two stack traces. Note the redundant calls to Calculate methods for n=5 and n=4.
Using recursion Fib(n) is solved in exponential time.

T(n) = T(n-1) + T(n-2) + Θ(1)

// Θ(1) constant part

Fibonacci sequence using DP

int?[] m_CachedResults = new int?[short.MaxValue + 1];
     
public int DPCalculate(int n)
{
    m_CachedResults[1] = 1;
    m_CachedResults[2] = 1;

    if (m_CachedResults[n] != null)
    {
        return m_CachedResults[n].GetValueOrDefault();
    }
    else
    {
        m_CachedResults[n] = Calculate(n);
        return m_CachedResults[n].GetValueOrDefault();
    }
}

private int Calculate(int n)
{
    if (n <= 2)
        return 1;
    else
    {
        if (m_CachedResults[n] != null)
            return m_CachedResults[n].GetValueOrDefault();
        else
            return Calculate(n - 1) + Calculate(n - 2);
    }
}

Call Stack - Calculate(6)

Calculate(6)

Calculate(5)

Calculate(4)

Calculate(3)

Calculate(2)

Calculate(1)

Calculate(2)

Calculate(3)

Calculate(2)

Calculate(1)

Calculate(4)

Calculate(3)

Calculate(2)

Calculate(1)

Calculate(2)

Call Stack - Calculate (7)

Calculate(7)

Calculate(6)

Calculate(5)

Calculate(4)

Calculate(3)

Calculate(2)

Calculate(1)

Calculate(2)

Calculate(3)

Calculate(2)

Calculate(1)

Result - Efficiency

Since the program utilizes DP and caches intermediate values (memoized values), the calculation of the subsequent fibonacci numbers in the sequence is much more efficient. As the cache results get filled out, the algorithm becomes progressively more efficient.

Memoized calls are constant Θ(1)
For a given n, only one recursion cycle is used. Over time and multiple accesses, this is essentially constant. Therefore, the DP algorithm for Fibonacci calculation is linear (n).