maandag 4 september 2017

Algorithms at Khan Academy part 1

Binary search is an efficient algorithm for finding an item from an ordered list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one.

Implement binary search in Javascript:
/* Returns either the index of the location in the array,
  or -1 if the array did not contain the targetValue */
var doSearch = function(array, targetValue) {
    var min = 0;
    var max = array.length - 1;
    var guess;
    var i = 1;
    while(min <= max) {
    guess = Math.floor((max + min) / 2);

    if (array[guess] === targetValue) {
        println("Total guesses " +i);
        return guess;
    }
    else if (array[guess] < targetValue) {
        min = guess + 1;
    }
    else {
        max = guess - 1;
    }
    i = i+1;
    println(guess);   
}
   


    return -1;
};

var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
        41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];

var result = doSearch(primes, 73);
println("Found prime at index " + result);

Program.assertEqual(doSearch(primes, 73), 20);
Program.assertEqual(doSearch(primes, 97), 24);
Program.assertEqual(doSearch(primes, 11), 4);


We use big-Θ notation to asymptotically bound the growth of a running time to within constant factors above and below.

We use big-O notation for asymptotic upper bounds, since it bounds the growth of the running time from above for large enough input sizes. It basically means "the running time grows at most this much, but it could grow more slowly."

We can say that the running time of binary search is always O(lgn) O(\lg n) O(lgn). We can make a stronger statement about the worst-case running time: it's Θ(lgn) \Theta(\lg n) Θ(lgn).

We use big-Ω notation to say that an algorithm takes at least a certain amount of time, without providing an upper bound. So the running time is "big-Ω of f(n) f(n) f(n)f, left parenthesis, n, right parenthesis." We use big-Ω notation for asymptotic lower bounds, since it bounds the growth of the running time from below for large enough input sizes.

IMPORTANT: We can say that binary search always runs in O(lgn) O(\lg n) O(lgn) time but not that it always runs in Θ(lgn) \Theta(\lg n) Θ(lgn) time. Θ(f(n)) automatically implies O(f(n)) O(f(n)) O(f(n))O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis AND Ω(f(n)) \Omega(f(n)) Ω(f(n)).



Here is a list of functions in asymptotic notation that we often encounter when analyzing algorithms, listed from slowest to fastest growing.
  1. Θ(1) \Theta(1) Θ(1)
  2. Θ(lgn) \Theta(\lg n) Θ(lgn)
  3. Θ(n) \Theta(n) Θ(n)
  4. Θ(nlgn) \Theta(n \lg n) Θ(nlgn)
  5. Θ(n2) \Theta(n^2) Θ(n2)
  6. Θ(n2lgn) \Theta(n^2 \lg n) Θ(n2lgn)
  7. Θ(n3) \Theta(n^3) Θ(n3)
  8. Θ(2n) \Theta(2^n) Θ(2n)
  • A function has "constant" growth if its output does not change based on the input, the nn. The easy way to identify constant functions is find those that have no nn in their expression anywhere, or have n0n^0 --> 11 and 100010001000 are constant.
  • A function has "linear" growth if its output increases linearly with the size of its input. The way to identify linear functions is find those where nnn is never raised to a power (although n1n^1 n, start superscript, 1, end superscriptis OK) or used as a power. --> 3n3n3, n and (3/2)nleft parenthesis, 3, slash, 2, right parenthesis, n are linear.
  • A function has "polynomial" growth if its output increases according to a polynomial expression. --> 2n32n^32, n, start superscript, 3, end superscript and 3n23n^2 are polynomial.
  • A function has "exponential" growth if its output increases according to an exponential expression. The way to identify exponential functions is to find those where a constant is raised to some expression involving nnn. --> 2n2^n and (3/2)n(3/2)^nleft parenthesis, 3, slash, 2, right parenthesis, start superscript, n, end superscript are exponential.
Find minimum in subarray:
var indexOfMinimum = function(array, startIndex) {
    // Set initial values for minValue and minIndex,
    // based on the leftmost entry in the subarray: 
    var minValue = array[startIndex];
    var minIndex = startIndex;

    // Loop over items starting with startIndex,
    // updating minValue and minIndex as needed:
    for (var i = minIndex+1; i<array.length;i++){
if(array[i]<array[minIndex]){
minIndex = i;
minValue=array[i];} }
    return minIndex;
};

var array = [18, 6, 66, 44, 9, 22, 14];  
var index = indexOfMinimum(array, 2);

//  For the test array [18, 6, 66, 44, 9, 22, 14],
//  the value 9 is the smallest of [..66, 44, 9, 22, 14]
//  Since 9 is at index 4 in the original array,
//  "index" has value 4
println("The index of the minimum value of the subarray starting at index 2 is " + index + "."  );
Program.assertEqual(index, 4);
Program.assertEqual(indexOfMinimum(array, 5), 6);
Program.assertEqual(indexOfMinimum(array, 3), 4); 


Implement selection sort:
var selectionSort = function(array) {
  var minIndex;
  for (var i = 0; i < array.length; i++) {
    minIndex = indexOfMinimum(array, i);
    swap(array, i, minIndex);
  }
};

var array = [22, 11, 99, 88, 9, 7, 42];
selectionSort(array);
println("Array after sorting:  " + array);

Program.assertEqual(array, [7, 9, 11, 22, 42, 88, 99]);
array = [22, 11, 99, 88, 9, 7, 42,1];
selectionSort(array);
Program.assertEqual(array, [1, 7, 9, 11, 22, 42, 88, 99]);
array = [22, 11, 0, 88, 9, 7, 42,1];
selectionSort(array);
Program.assertEqual(array, [0, 1, 7, 9, 11, 22, 42, 88]);
 

Computing summations from 1 to n:
A faster way to calculate 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36 is:
(8+1)+(7+2)+(6+3)+(5+4)=9+9+9+9
                                          =49=36 .

Add the smallest and the largest number and then multiply by the number of pairs.
What if the sequence to sum up goes from 1 to n n n? We call this an arithmetic series. The sum of the smallest and largest numbers is n+1n, plus, 1. Because there are n n nn numbers altogether, there are n/2 n/2 pairs (whether n n nn is odd or even). Therefore, the sum of numbers from 1 to n is (n+1)(n/2), which equals n2/2+n/2n, start superscript, 2, end superscript, slash, 2, plus, n, slash, 2.

  1. Call insert to insert the element that starts at index 1 into the sorted subarray in index 0.
  2. Call insert to insert the element that starts at index 2 into the sorted subarray in indices 0 through 1.
  3. Call insert to insert the element that starts at index 3 into the sorted subarray in indices 0 through 2.
  4. Finally, call insert to insert the element that starts at index n1 n-1 n1n, minus, 1 into the sorted subarray in indices 0 through n2 n-2 n2n, minus, 2.


Implement insert sort (running time Θ(n2)):
var insert = function(array, rightIndex, value) {
   var i;
  for (i = rightIndex; i >= 0 && array[i] > value; i--) {
    array[i + 1] = array[i];
  }
  array[i + 1] = value;
};


var insertionSort = function(array) {
 for (var i = 1; i < array.length; i++) {
    insert(array, i - 1, array[i]);
  }
};

var array = [3, 5, 7, 11, 13, 2, 9, 6];

insert(array, 4, 2);
println("Array after inserting 2:  " + array);
Program.assertEqual(array, [2, 3, 5, 7, 11, 13, 9, 6]);



Difference between Insertion and Selection sort:
  • Insertion sort: inserts the next element at the correct position;
  • Selection sort: selects the smallest element and exchange it with the current item;
The running times for insertion sort:
  • Worst case: Θ(n2).
  • Best case: Θ(n) \Theta(n) . <--almost sorted array
  • Average case for a random array: Θ(n2) \Theta(n^2) .
  • "Almost sorted" case: Θ(n) \Theta(n) .
Recursion:  solve a problem by solving a smaller instance of the same problem, unless the problem is so small that we can just solve it directly.See part 2.