Dijkstra’s Algorithm is an algorithm to find the shortest path between vertices in a graph. It was created by Edsger W. Dijkstra, a Dutch computer scientist. Given a source vertex, the algorithm will find the shortest path between that vertex and all other vertices in the graph (returning infinity if there is no path between the source vertex and a given vertex). This is known as the shortest-path tree. It can be modified to find the shortest distance between the source vertex and a target vertex, simply by stopping once the shortest path is found for the target vertex.

Step by Step Example

Dijkstra’s…

I recently came across an implementation of an undirected weighted graph using an adjacency matrix. Prior to this, I was used to seeing graphs represented using adjacency lists. To keep this blog focused, today I’ll only be writing about representing a weighted graph using an adjacency matrix, and will assume that the reader is already aware of how to represent a graph using an adjacency list. By the end of this blog, the goal will be that you will be able to build a Graph class which utilizes an adjacency matrix.

What is an Adjacency Matrix?

Square Matrix

An adjacency matrix, is a square matrix which is…

Last week I took a quick look at bit manipulation. I learned about bitwise operators, as well as how to represent positive base 10 numbers in binary (base 2). Today I want to dig a little deeper, and talk about negative numbers represented in binary, as well as a few clever bit manipulation tricks.

Negative Numbers

In my last blog I discussed how using the NOT (~) bitwise operator on a number in your code, would get you a different result than what I had shown. …

Recently, while doing leetcode problems I came across a problem in which the most optimal solution was the result of bit manipulation. I knew bits were the 0’s and 1’s in binary, but that was about it. I decided to dig a little deeper and share what I’ve found here.

What are Bits?

Bit is a portmanteau of binary digit. Binary meaning two. A single bit therefor has 2 states, most often true or false, this is generally represented as 1 or 0. Through a series of bits one may represent a piece of data such as a number. …

A hash table is a data structure which consists of key and value pairs. A good analogy is thinking of it like a dictionary (the book), the keys are the words and the values are the definitions. If you think that sounds familiar, you’re correct, JavaScript Objects are an example of a hash table. That being said, using JavaScript’s built in Object or Map, is going to be faster and more optimal than what I implement here. This blog is more about understanding the concepts behind a hash table.

Pros and Cons of a Hash Table

Pros

• Fast lookup
• Fast insertion
• Fast deletion

Cons

• Hash Collisions (particularly when there…

Last week I wrote about implementing a max heap in JavaScript, now we’re going to put that knowledge to the test and write a heap sort algorithm. Understanding the implementation, and time and space complexities of a max heap will make understanding the heap sort algorithm quite simple.

Step by Step Example

The Process

We know in a max heap, the largest element is stored at the root. So these will be the steps of heap sort:

• Move the element at index 0 to the end of the array
• Re-heapify the array, excluding the last element
• Continue this process of swapping and re-heapifying each time excluding…

Last week I wrote about implementing quicksort in JavaScript, the next sorting algorithm I would like to cover is heap sort. However, in order to do so, we need to understand the heap data structure. A heap is a tree based structure. Specifically we will be looking at a max heap, which is a form of binary heap that satisfies the heap property. The heap property states that every child node will be less than (or greater than, in the case of a min heap) its parent node. This means that the root node will always be the maximum element…

Last week I covered implementing merge sort in JavaScript. This week I’m going to look at quicksort, which is another commonly used sorting algorithm. Like merge sort, quicksort is another comparison sort algorithm that takes a divide and concur approach.

Step by Step Example

The steps to perform quicksort on an array are as follows:

• Pick a an element from the array, called the pivot.
• Reorder the array so that the elements less than the pivot come before it, and the elements greater than come after. This is called partitioning as now the array is in two partitions.
• Recursively call quicksort on the two…