add number code

tomcostello · Jul 4, 2019 · Jul 6, 2019 · Jul 8, 2019 · Jul 8, 2019 · Jul 9, 2019
commit 9fbed434af72072ef24a0cd7a9814cb7128b4982
diff --git a/solutions/algorithms/numbers/fibonacci/README.md b/solutions/algorithms/numbers/fibonacci/README.md
@@ -15,6 +15,75 @@ The Fibonacci spiral: an approximation of the golden spiral created by drawing c
 
 ![Fibonacci Spiral](https://upload.wikimedia.org/wikipedia/commons/2/2e/FibonacciSpiral.svg)
 
+
+## Implemetation
+
+The simple implementation of Fibinacci is recursive. Write 
+
+Note how we need two base cases, as the recursive defintion calls `Fib(n-2)`.   This solution is very slow, as the call to `Fib(n-1)` redoes all the work of the call to `Fib(n-2)`.  In fact, a call to `Fib(n)`  makes an exponential numnber of recursive calls to itself, hence it is O(2^n), very slow.  However, there is a simple way to speed it up.  We can remember the intermediate results.  `mem` is an array that records the value of `Fib(n)` in position n.  If `mem[n]` is null, we do not know the value yet.
+
+
+Write  a recursive `fibonacciMem(n,mem)` and write `fibonacciM(n)` using it.
+
+This seems like a minor change, but this changes the complexity of the algorithm to linear.  This kind of change, adding memoization, is a very important skill that is expected in interviews.  All recursive solutions can have this applied, and if they repeatedly call the same arguments, this will result in a huge speed up.
+
+We are not done yet.  We now can change this to an iterative solution.  Rather than go backwards from n, we can compute the Fibonacci numbers forwards, iteratively.  This is simpler. 
+
+```
+FibI(){
+
+      var fib = [0,1];
+
+      for (var i = 2; i <=n;i++)
+      	  fib.push(fib[i-1]+fib[i-2];
+      return fib[n];	 
+}
+```
+
+Write `fibonacci` in this style so it returns the array of Fibonacci numbers.
+
+This uses an array of length n.  We only ever look at the last two values of that array, so we can minimize the space we use by just storing them.
+
+```
+fibonacciNth((){
+	var twoBack = 0;
+      	var oneBack = 1;
+      for (var i = 2; i <=n;i++){
+      	  oneBack = oneBack+twoBack;
+	  twoBack = oneBack;
+	  }
+      oneBack;	 
+}
+```
+
+
+Write  `fibonacciNth` so it computes the nth Fibonacci number in this style.
+
+
+This seems very efficient.  Can we do better? Of course, but for now, this will be fast enough.  
+
+It is rare that someone is asked about a textbook problem in an interview.  It is common, however, to be asked a textbook problem with the words changed.  Consider the following interview question asked at Facebook:
+
+"Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, count the number of ways it can be decoded."
+
+The nunber 11 could either be the string "aa" or the string "k", so can be parsed in 2 ways.  The string "111" can be parsed as "aaa","ka", or "ak", so three ways.  "11111" can be parsed as k, followed by "111", or "a" followed by "1111", so can be parsed 5 ways.  In general, a string of n 1s can be parsed Fib(n) ways.  This problem is just the Fibonacci problem with some edge cases.  
+
+Let `nwd(s,p)` be the number of ways of decoding a string starting from position p.  Write this recursively, with memoization, using an array and finally using just 2 variables.
+
+
+
+
+This pattern, or writing a recursive program that does the problem
+simply, followed by memoization, transforming the program to an
+iterative one, and finally using constant space, is very common in
+interviews.  If you are asked a question where you can do this, you
+can easily fill an hour with intelligent code that improves each time.
+This usually results in a good outcome.
+
+
+
+
+
 ## References
 
 [Wikipedia](https://en.wikipedia.org/wiki/Fibonacci_number)
diff --git a/solutions/algorithms/numbers/fibonacci/fibonacciNth.js b/solutions/algorithms/numbers/fibonacci/fibonacciNth.js
@@ -16,7 +16,7 @@ export default function fibonacciNth(n) {
 
   while (iterationsCounter) {
     currentValue += previousValue;
-    previousValue = curre ntValue - previousValue;
+    previousValue = currentValue - previousValue;
 
     iterationsCounter -= 1;
   }

diff --git a/solutions/algorithms/numbers/prime/README.md b/solutions/algorithms/numbers/prime/README.md
@@ -19,6 +19,44 @@ a computationally difficult problem, whereas primality testing
 is comparatively easy (its running time is polynomial in the 
 size of the input). 
 
+
+
+
+## Implementation
+
+
+##Trial Division
+
+[Trial Division](https://en.wikipedia.org/wiki/Trial_division) is the oldest primarlity algortihm.  It works by successively dividing the number, n,  by larger and larger numbers until a divisor is found.  If no divisor is found by the time you reach the square or n, then n is prime.  
+
+Write `function trialDivision(number)`.
+
+##Fermat's Method
+
+Every number odd number n can be written as the difference of two squares, so there are a and b, such that n = a^2 - b^2.   If n  = c*d, n can be written as ((c+d)/2)^2 * ((c-d)/2)^2.    This can be checked by simple algebra. The idea of Fermat's method is to guess a value for a, and try to work out what b is.  The usual starting place is the first number larger than the square root of n.  If we check all numbers up to to (n+1)/2 without finding a divisor, the number is prime.
+
+Write `fermatTest(n)`.
+
+
+
+This function returns false if the nunber is prime, otherwise it returns a divisor.  This method is slower than Trial Division, but a combination of both methods is faster.  This method can be extended in various ways to make better algorithms, like the quadratic sieve, which are too complicated for us.
+
+
+#Primality Tests 
+
+There are algorithms that test whether a nunber if prime with high probablility, but which are sometimes wrong.  These are much faster than Trial Division.  These are what is used to find the large prime numbers that are used in cryptography.
+
+## Fermat's Primality Test
+
+Fermat's little theorem tells us that  if p is prime and a is not divisible by p, then a^{p-1} mod p  = 1.  To check a number is prime we can choose an a, and check whether a^{p-1} mod p is equal to 1.  If this is true for several different numbers, we can be fairly confident that p is prime.
+
+Write `fermatPrimality(n)`.
+
+
+
+
+
+
 ## References
 
 - [Prime Numbers on Wikipedia](https://en.wikipedia.org/wiki/Prime_number)