Category: Algorithms

Breadth-First Search (BFS)

technologeo

Programming Language:

Javascript (JS)

Solution:

/* A Queue object for queue-like functionality over JavaScript arrays. */
var Queue = function() {
    this.items = [];
};
Queue.prototype.enqueue = function(obj) {
    this.items.push(obj);
};
Queue.prototype.dequeue = function() {
    return this.items.shift();
};
Queue.prototype.isEmpty = function() {
    return this.items.length === 0;
};

/*
 * Performs a breadth-first search on a graph
 * @param {array} graph - Graph, represented as adjacency lists.
 * @param {number} source - The index of the source vertex.
 * @returns {array} Array of objects describing each vertex, like
 *     [{distance: _, predecessor: _ }]
 */
var doBFS = function(graph, source) {
    var bfsInfo = [];

    for (var i = 0; i < graph.length; i++) {
	    bfsInfo[i] = {
	        distance: null,
	        predecessor: null };
    }

    bfsInfo[source].distance = 0;

    var queue = new Queue();
    queue.enqueue(source);

    // Traverse the graph
    
    // As long as the queue is not empty:
    while (!queue.isEmpty()) {
    //  Repeatedly dequeue a vertex u from the queue.
        var currentVertex = queue.dequeue();
    //  For each neighbor v of u that has not been visited:
    //     Set distance to 1 greater than u's distance
    //     Set predecessor to u
    //     Enqueue v
    //     v = currentNeighbor
    //     u = currentVertex
        for (var i = 0; i < graph[currentVertex].length; i++) {
            var currentNeighbor = graph[currentVertex][i];
            
            if (bfsInfo[currentNeighbor].distance === null) {
                bfsInfo[currentNeighbor].distance = bfsInfo[currentVertex].distance + 1;
                bfsInfo[currentNeighbor].predecessor = currentVertex;
                queue.enqueue(currentNeighbor);
            }
        }
    }    
    return bfsInfo;
};


var adjList = [
    [1],
    [0, 4, 5],
    [3, 4, 5],
    [2, 6],
    [1, 2],
    [1, 2, 6],
    [3, 5],
    []
    ];
var bfsInfo = doBFS(adjList, 3);
for (var i = 0; i < adjList.length; i++) {
    println("vertex " + i + ": distance = " + bfsInfo[i].distance + ", predecessor = " + bfsInfo[i].predecessor);
}


Program.assertEqual(bfsInfo[0], {distance: 4, predecessor: 1});
Program.assertEqual(bfsInfo[1], {distance: 3, predecessor: 4});
Program.assertEqual(bfsInfo[2], {distance: 1, predecessor: 3});
Program.assertEqual(bfsInfo[3], {distance: 0, predecessor: null});
Program.assertEqual(bfsInfo[4], {distance: 2, predecessor: 2});
Program.assertEqual(bfsInfo[5], {distance: 2, predecessor: 2});
Program.assertEqual(bfsInfo[6], {distance: 1, predecessor: 3});
Program.assertEqual(bfsInfo[7], {distance: null, predecessor: null});

Quicksort

technologeo

Programming Language:

Javascript (JS)

Solution:

// This function partitions given array and returns 
// the index of the pivot.
//var partition=function(array, p, r){
// This code has been purposefully obfuscated,
// as you will implement it yourself in next challenge
//    var e=array,t=p,n=r;var r=function(e,t,n){var r=e[t];e[t]=e[n];e[n]=r;};var i=t;for(var s=t;s<n;s++){if(e[s]<=e[n]){r(e,s,i);//i++;}}r(e,n,i);return i;
//};

// Swaps two items in an array, changing the original array
var swap = function(array, firstIndex, secondIndex) {
    var temp = array[firstIndex];
    array[firstIndex] = array[secondIndex];
    array[secondIndex] = temp;
};

// This function partitions given array and returns 
// the index of the pivot.
var partition = function(array, p, r) {
    // Compare array[j] with array[r], for j = p, p+1,...r-1
    var q = p;

    // maintaining that:
    // array[p..q-1] are values known to be <= to array[r]
    // array[q..j-1] are values known to be > array[r]
    // array[j..r-1] haven't been compared with array[r]
    // If array[j] > array[r], just increment j.
    // If array[j] <= array[r], swap array[j] with array[q],
    // increment q, and increment j. 
    for (var j = p; j < r; j++) {
        if (array[j] <= array[r]) {
            swap(array, j, q);
            q++;
        }
    }
    // Once all elements in array[p..r-1]
    //  have been compared with array[r],
    //  swap array[r] with array[q], and return q.
    swap(array, r, q);
    return q;
};

var array = [9, 7, 5, 11, 12, 2, 14, 3, 10, 4, 6];
var q = partition(array, 0, array.length-1);
println("Array after partitioning: " + array);
Program.assertEqual(q, 4);
Program.assertEqual(array, [5, 2, 3, 4, 6, 7, 14, 9, 10, 11, 12]);

var array = [-9, 7, 5, 11, 12, 2, 0, 3, 10, 4, -6];
var q = partition(array, 0, array.length-1);
println("Array after partitioning: " + array);
Program.assertEqual(q, 1);
Program.assertEqual(array, [-9, -6, 5, 11, 12, 2, 0, 3, 10, 4, 7]);

var quickSort = function(array, p, r) {
    if(p < r) {
        var pivotIndex = partition(array, p, r);
        quickSort(array, p, pivotIndex - 1);
        quickSort(array, pivotIndex + 1, r);
    }
};

var array = [9, 7, 5, 11, 12, 2, 14, 3, 10, 6];
quickSort(array, 0, array.length-1);
println("Array after sorting: " + array);
Program.assertEqual(array, [2,3,5,6,7,9,10,11,12,14]);

var array = [-9, 75, 54, 1, 12, 2, 18, 3, 0, -6];
quickSort(array, 0, array.length-1);
println("Array after sorting: " + array);
Program.assertEqual(array, [-9, -6, 0, 1, 2, 3, 12, 18, 54, 75]);

Sierpinski’s Gasket

technologeo

HTML 5/JS (Javascript)

<canvas id="sierpinski_canvas" width="750" height="750" style="border:1px solid #888;"></canvas>

<script>
var canvas = document.getElementById("sierpinski_canvas");
var canvasInfo = document.getElementById("sierpinski_canvas").getBoundingClientRect();
var canvasWidth = canvasInfo.width;
var canvasHeight = canvasInfo.height;
var ctx = canvas.getContext("2d");
var rectDim = 750;
var rectMinSize = 7;

function drawGasket(x, y, rectDim) {
    if (rectDim <= rectMinSize) {
            var randomColor = Math.floor(Math.random()*16777215).toString(16);
            ctx.fillStyle = "#" + randomColor;
	    ctx.fillRect(x, y, rectDim, rectDim);
    }
    else {
	    var newRectDim = rectDim / 2;
	    drawGasket(x, y, newRectDim);
	    drawGasket(x + newRectDim, y, newRectDim);
	    // drawGasket(x, y + newRectDim, newRectDim);
	    drawGasket(x + newRectDim, y + newRectDim, newRectDim);
    }
};
drawGasket(0, 0, rectDim);
</script>

Insertion Sort

technologeo

Programming Language:

Javascript (JS)

Solution:

var insert = function(array, rightIndex, value) 
{
    for(var i = rightIndex; i >= 0 && array[i] > value; i--)
    {array[i + 1] = array[i];}   
    array[i + 1] = value;
};

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

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

var array = [2, 131, 99, 8218, -1, 0, 42];
insertionSort(array);
println("Array after sorting:  " + array);
Program.assertEqual(array, [-1, 0, 2, 42, 99, 131, 8218]);

Selection Sort

technologeo

Programming Language:

Javascript (JS)

Solution:

var swap = function(array, firstIndex, secondIndex) {
    var temp = array[firstIndex];
    array[firstIndex] = array[secondIndex];
    array[secondIndex] = temp;
};

var indexOfMinimum = function(array, startIndex) {

    var minValue = array[startIndex];
    var minIndex = startIndex;

    for(var i = minIndex + 1; i < array.length; i++) {
        if(array[i] < minValue) {
            minIndex = i;
            minValue = array[i];
        }
    } 
    return minIndex;
}; 

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]);

var array = [-7, 9, 1, 2, -2, 0, 99];
selectionSort(array);
println("Array after sorting:  " + array);
Program.assertEqual(array, [-7, -2, 0, 1, 2, 9, 99]);

Binary Search

technologeo

Programming Language:

Javascript (JS)

Solution:

/* 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 countguess = 0;

    while(min <= max)
        {
            guess = Math.floor((max+min)/2);
            countguess++;
            println(guess);
            if(array[guess] < targetValue)
            {min = guess+1;}
            else if (array[guess] > targetValue)
            {max = guess-1;}
            else
            {println(countguess);return 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, 71), 19);
Program.assertEqual(doSearch(primes, 2), 0);