The repository contains a variety of javascript-based algorithms and data structures.

Each algorithm and data structure has its own README with instructions as well as further reading and YouTube videos.

The data structure

Data structure is a special way to organize and store data in a computer, which can be accessed and modified efficiently. More specifically, a data structure is a collection of data values whose relationships, functions, or operations can be applied to the data.

algorithm

An algorithm is a clear specification of how to solve a class of problems. An algorithm is a set of rules that precisely define a sequence of operations.

Algorithm theme

  • mathematics
    • factorial
    • Fibonacci number
    • Prime detection (elimination method)
    • Euclidean algorithm – Computing the Greatest Common Divisor (GCD)
    • Least Common multiple (LCM)
    • Integer split
  • A collection of
    • Cartesian product – multiple set results
    • Power set – all subsets of the set
    • Permutation (with/without repetition)
    • Combination (with/without duplication)
    • Shuffle algorithm – random permutation of finite sequences
    • Longest Common Subsequence (LCS)
    • Longest increasing subsequence
    • Shortest Common Supersequence (SCS)
    • Backpack problem – “0/1” and “Unbound” ones
    • Maximum subsequence problem – BF algorithm and dynamic programming
  • string
    • Lewenstein distance – The minimum edit distance between two sequences
    • Hamming distance – number of positions with different symbols
    • Knuss-morris-pratt algorithm – substring search
    • Quick string lookup – substring search
    • Longest common substring
  • search
    • Binary search
  • The sorting
    • Bubble sort
    • Selection sort
    • Insertion sort
    • Heap sort
    • Merge sort
    • Quick sort
    • Hill sorting
  • The tree
    • Depth-first Search (DFS)
    • Breadth First Search (BFS)
  • figure
    • Depth-first Search (DFS)
    • Breadth First Search (BFS)
    • Dykstra algorithm m – Find the shortest path to all graph vertices
    • Behrman-ford algorithm – Find the shortest path to all graph vertices
    • Lapsing algorithm – for directed and undirected graphs (based on DFS and non-intersecting versions)
    • Prinn algorithm – Finding the Minimum Spanning Tree (MST) of Weighted Undirected Graphs
    • Kruskel algorithm – Finding the Minimum Spanning Tree (MST) of Weighted Undirected Graphs
    • Topological sort – DFS method
    • Node-tarjan algorithm (Based on DFS)
    • Bridge – Algorithm based on DFS
    • Euler path with one stroke problem – Fleury’s algorithm – access each edge once
    • Hamiltonian diagram – Visits each vertex exactly once
    • Strongly connected component – Kosaraju algorithm
    • Traveling salesman problem – visit each city by the shortest possible route and return to the original city
  • unclassified
    • Hanoi
    • Eight Queens problem
    • Knight patrol

The algorithm paradigm

An algorithm paradigm is a generic method or method algorithm for class-based design. This is a higher abstraction than an algorithm concept, just as an algorithm is a higher abstraction than a computer program.

How to use the warehouse

Install dependencies

npm install
Copy the code

Perform the test

npm test
Copy the code

Execute tests by name

npm test -- -t 'LinkedList'
Copy the code

Playground

You can be in. / SRC/playground/playground. Js file operation data structure and algorithm, and in the. / SRC/playground / __test__ / playground. Test. Write a test in js.

Then, just run the following command to test your Playground:

npm test -- -t 'playground'
Copy the code

Useful information

reference

▶ YouTube

Big O notation

The growth order of the algorithms specified in the big O notation.

Source: Big O Cheat Sheet.

Here is a list of some of the most common big O notations and how they compare to input data of different sizes.

Big O notation Count 10 elements Count 100 elements Count 1000 elements
O(1) 1 1 1
O(log N) 3 6 9
O(N) 10 100 1000
O(N log N) 30 600 9000
O(N^2) 100 10000 1000000
O(2^N) 1024 1.26 e+29 1.07 e+301
O(N!) 3628800 9.3 e+157 4.02 e+2567

Complexity of data structure operations

The data structure The connection To find the insert delete
An array of 1 n n n
The stack n n 1 1
The queue n n 1 1
The list n n 1 1
Hash table – n n n
Binary search tree n n n n
B tree log(n) log(n) log(n) log(n)
Red and black tree log(n) log(n) log(n) log(n)
AVL tree log(n) log(n) log(n) log(n)

The complexity of array sorting algorithms

The name of the The optimal On average, The worst memory stable
Bubble sort n n^2 n^2 1 Yes
Insertion sort n n^2 n^2 1 Yes
Selection sort n^2 n^2 n^2 1 No
Heap sort n log(n) n log(n) n log(n) 1 No
Merge sort n log(n) n log(n) n log(n) n Yes
Quick sort n log(n) n log(n) n^2 log(n) No
Hill sorting n log(n) Dependent on gap sequence n (log(n))^2 1 No