EcmaScript 6 Algorithms and Data Structures

This repository contains some popular Data Structures and Algorithms done in JavaScript ES6.

Data Structures

According to Wikipedia:

In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.

The following terms are the foundation terms of a data structure.

• Interface - This represents the set of operation supported by a data structure
• Implementation - This provides the definition of algorithms used in the operations of the data structure i.e. it provides the internal representation of the data structure

Characteristics of a Data Structure

1. Correctness - a data structure should implement its interface correctly
2. Time Complexity - execution time of operations of a data structure should be as small as possible
3. Space Complexity - memory usage of a data structure operation should be as little as possible

Data Structure Operations Complexity

Shown below are the data structures covered here:

• Array
• Linked List
• Doubly Linked List
• Stack
• Queue
• Priority Queue
• Set
• Disjoint Set
• Bloom Filter
• Skip List
• Hash Table
• Graph
• Tree
• Binary Search Tree
• AVL Tree
• Red Black Tree
• Splay Tree
• B-Tree
• Trie
• Min Heap
• Max Heap
• Binomial Heap
• Fibonacci Heap

Algorithms

This is a process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer.

The following are the algorithms covered here:

Algorithms by Topic

• Searching
  • Linear Search
  • Binary Search
  • Jump/Block Search
  • Interpolation Search
• Sorting
  • Shell Sort
  • Heap Sort
  • Quick Sort
  • Radix Sort
  • Merge Sort
  • Bubble Sort
  • Insertion Sort
  • Counting Sort
  • Selection Sort
• Sets
  • Longest Increasing Subsequence
  • Longest Common Subsequence (LCS)
  • Shortest Common Supersequence (SCS)
  • Permutations (with and without repetitions)
  • Combinations (with and without repetitions)
  • Combination Sum - find all combinations that form specific sum
  • Maximum Subarray - "Brute Force" and "Dynamic Programming" (Kadane's) versions
• Math
  • Factorial
  • Fibonacci
  • Integer Partition
  • Pascal's Triangle
  • Least Common Multiple (LCM)
  • Primality Test (trial division method)
  • Euclidean Algorithm - calculate the Greatest Common Divisor (GCD)
  • Sieve of Eratosthenes - finding all prime numbers up to any given limit
  • Is Power of Two - check if the number is power of two (naive and bitwise algorithms)
• Trees
  • Depth-First Search (DFS)
  • Breadth-First Search (BFS)
• Graphs
  • Depth-First Search (DFS)
  • Breadth-First Search (BFS)
  • Dijkstra Algorithm - finding shortest paths to all graph vertices from single vertex
  • Prim’s Algorithm - finding Minimum Spanning Tree (MST) for weighted undirected graph
  • Kruskal’s Algorithm - finding Minimum Spanning Tree (MST) for weighted undirected graph
  • Travelling Salesman Problem - shortest possible route that visits each city and returns to the origin city
• Others
  • Tower of Hanoi

Algorithms by Paradigm

An algorithmic paradigm is a generic method or approach which underlies the design of a class of algorithms. It is an abstraction higher than the notion of an algorithm, just as an algorithm is an abstraction higher than a computer program.

• Brute Force - look at all the possibilities and selects the best solution
  • Linear Search
  • Maximum Subarray
  • Travelling Salesman Problem - shortest possible route that visits each city and returns to the origin city
• Greedy - choose the best option at the current time, without any consideration for the future
  • Prim’s Algorithm - finding MST for weighted undirected graph
  • Dijkstra Algorithm - finding shortest path to all graph vertices
  • Kruskal’s Algorithm - finding Minimum Spanning Tree (MST) for weighted undirected graph
• Divide and Conquer - divide the problem into smaller parts and then solve those parts
  • Quick Sort
  • Merge Sort
  • Binary Search
  • Tower of Hanoi
  • Pascal's Triangle
  • Euclidean Algorithm - GCD
  • Tree Depth-First Search (DFS)
  • Graph Depth-First Search (DFS)
  • Permutations (with and without repetitions)
  • Combinations (with and without repetitions)
• Dynamic Programming - build up a solution using previously found sub-solutions
  • Fibonacci
  • Integer Partition
  • Maximum Subarray
  • Longest Increasing Subsequence
  • Shortest Common Supersequence
  • Longest Common Subsequence (LCS)
• Backtracking - similarly to brute force, try to generate all possible solutions, but each time you generate next solution you test if it satisfies all conditions, and only then continue generating subsequent solutions. Otherwise, backtrack, and go on a different path of finding a solution. Normally the DFS traversal of state-space is being used.
  • Combination Sum - find all combinations that form specific sum

Array Sorting Algorithms Complexity

Big-O Notation

This is a theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items. Informally, saying some equation f(n) = O(g(n)) means it is less than some constant multiple of g(n).

It is used in Computer Science to describe the performance or complexity of an algorithm. Big-O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm.

The most optimum algorithm scales in constant time and space. This means it does not care at all about the growth of its inputs. Next best is logarithmic time or space, then linear, linearithmic, quadratic, and exponential. The worst is factorial time or space. In Big-O notation:

1. Constant: O(1)
2. Logarithmic: O(log n)
3. Linear: O(n)
4. Linearithmic: O(n log n)
5. Quadratic: O(n²)
6. Expontential: O(2^n)
7. Factorial: O(n!)

Below is the list of some of the most used Big O notations and their performance comparisons against different sizes of the input data.

Installation

Clone this repo:

$ git clone https://github.com/akhenda/es6-data-structures-and-algorithms.git

Navigate to the es6-data-structures-and-algorithms directory:

$ cd es6-data-structures-and-algorithms

Install the required dependencies:

$ yarn install

Testing

To run both tests and linting, run:

yarn run validate

To run the tests alone:

yarn run test

To run ESLint:

yarn run lint

Usage

...

Resources

• Javascript Algorithms - Oleksii Trekhleb
• Data Structures and Algorithms Playlist on Youtube

License

The MIT License (MIT)

Copyright (c) 2016 Joseph Akhenda.

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.