JavaScript Algorithms and Data Structures

This repository provides fundamental implementations and documentation for various computer science concepts in JavaScript. Each implementation includes detailed explanations and external resources.

Data Structures

Includes implementations for:

• Linear structures: Linked List, Queue, Stack.
• Non-linear structures: Hash Table, Heap, Priority Queue, Trie, Tree (Binary Search Tree, AVL Tree, Red-Black Tree), Graph (Directed and Undirected), and Disjoint Set.

Algorithms

Algorithms are categorized by topic and paradigm:

By Topic:

• Math: Factorial, Fibonacci, Primality Test, Euclidean Algorithm (GCD), Least Common Multiple (LCM), Integer Partition.
• Sets: Cartesian Product, Power Set, Permutations, Combinations, Fisher-Yates Shuffle, Longest Common Subsequence (LCS), Longest Increasing Subsequence, Shortest Common Supersequence (SCS), Knapsack Problem, Maximum Subarray.
• Strings: Levenshtein Distance, Hamming Distance, KMP Algorithm, Rabin-Karp Algorithm, Longest Common Substring.
• Search & Sort: Binary Search, Bubble Sort, Selection Sort, Insertion Sort, Heap Sort, Merge Sort, Quick Sort, Shell Sort.
• Trees & Graphs: DFS/BFS (Tree and Graph), Dijkstra, Bellman-Ford, Cycle Detection, Prim's and Kruskal's (MST), Topological Sorting, Articulation Points, Bridges, Eulerian Path/Circuit, Hamiltonian Cycle, Strongly Connected Components, Travelling Salesman, Floyd-Warshall.
• Uncategorized: Hanoi Tower, N-Queens, Knight's Tour.

By Paradigm:

• Brute Force: Maximum Subarray, Travelling Salesman.
• Greedy: Knapsack, Dijkstra, Prim's, Kruskal's.
• Divide and Conquer: Binary Search, Hanoi Tower, Euclidean Algorithm, Permutations/Combinations, Merge Sort, Quick Sort, DFS (Tree/Graph).
• Dynamic Programming: Fibonacci, Levenshtein Distance, LCS, Longest Common Substring, Longest Increasing Subsequence, SCS, Knapsack (0/1), Integer Partition, Maximum Subarray, Bellman-Ford.
• Backtracking: Hamiltonian Cycle, N-Queens, Knight's Tour.
• Branch & Bound

The repository contains a wide range of algorithms categorized by their mathematical or computational domain. Algorithms are marked with difficulty levels: B for Beginner and A for Advanced.

Available Topics:

• Mathematics: Bit manipulation, Factorials, Fibonacci, Primality testing, Euclidean algorithm (GCD), LCM, Sieve of Eratosthenes, Power of two, Pascal's triangle, Complex numbers, Radian/Degree conversion, Fast powering, Horner's method, Integer partition, Square root (Newton's method), Liu Hui's π algorithm, and Discrete Fourier Transform.
• Sets: Cartesian product, Fisher-Yates shuffle, Power set, Permutations, Combinations, Longest Common Subsequence (LCS), Longest Increasing Subsequence, Shortest Common Supersequence (SCS), Knapsack problem, Maximum Subarray, and Combination Sum.
• Strings: Hamming distance, Levenshtein distance, Knuth-Morris-Pratt (KMP), Z-algorithm, Rabin-Karp, Longest Common Substring, and Regular Expression matching.
• Search Operations: Linear search, Jump search, Binary search, and Interpolation search.
• Sorting: Bubble Sort, Selection Sort, Insertion Sort, Heap Sort, Merge Sort, Quicksort, Shellsort, Counting Sort, and Radix Sort.
• Linked Lists: Straight Traversal and Reverse Traversal.
• Trees: Depth-First Search (DFS) and Breadth-First Search (BFS).
• Graphs: DFS, BFS, Kruskal’s Algorithm (MST), Dijkstra Algorithm (Shortest Path), Bellman-Ford Algorithm, Floyd-Warshall Algorithm, Cycle Detection, Prim’s Algorithm (MST), Topological Sorting, Articulation Points (Tarjan's), Bridges, Eulerian Path/Circuit, Hamiltonian Cycle, Strongly Connected Components (Kosaraju), and Travelling Salesman Problem.
• Cryptography: Polynomial Hash and Caesar Cipher.
• Machine Learning: NanoNeuron (Forward/Backward propagation).
• Uncategorized: Tower of Hanoi, Square Matrix Rotation, Jump Game, Unique Paths, Rain Terraces, Recursive Staircase, N-Queens Problem, and Knight's Tour.

The repository provides a wide range of JavaScript implementations for various algorithmic categories. You can find implementations for:

• Mathematics: Bit manipulation, floating point, factorials, Fibonacci, prime numbers (Sieve of Eratosthenes, primality tests), GCD (Euclidean algorithm), LCM, Pascal's triangle, complex numbers, matrices, and Fourier transforms.
• Sets: Cartesian products, Fisher-Yates shuffle, power sets, permutations, combinations, Longest Common Subsequence (LCS), Knapsack problem, and Maximum Subarray.
• Strings: Hamming distance, Palindrome checking, Levenshtein distance, pattern matching (KMP, Z-algorithm, Rabin-Karp), and Regular Expression matching.
• Searching: Linear search, Jump search, Binary search, and Interpolation search.
• Sorting: Bubble sort, Selection sort, Insertion sort, Heap sort, Merge sort, Quick sort, Shell sort, Counting sort, Radix sort, and Bucket sort.
• Data Structures: Linked list traversals, Trees (DFS, BFS), and Graphs (DFS, BFS, Kruskal, Dijkstra, Bellman-Ford, Floyd-Warshall, topological sorting, etc.).
• Cryptography: Polynomial hash, Rail-fence cipher, Caesar cipher, and Hill cipher.
• Machine Learning: k-NN, k-Means, and NanoNeuron.
• Image Processing: Seam Carving.
• Statistics: Weighted random selection.

A Bloom Filter is a space-efficient probabilistic data structure used to test whether an element is a member of a set. It is designed for high speed and minimal memory usage, but it introduces the possibility of false positives (reporting an element is in the set when it is not). It guarantees no false negatives (if it says an element is not in the set, it definitely is not).

Core Mechanics

1. Initialization: An empty Bloom Filter is represented by a bit array of size m, where all bits are initially set to 0.
2. Hash Functions: You must define k independent hash functions (h1, ..., hk) that map each element to one of the m positions in the array with a uniform distribution.
3. Adding an Element: To add an element e, set the bits at positions h1(e), ..., hk(e) to 1.
4. Membership Testing: To check if an element e is in the set, inspect the bits at positions h1(e), ..., hk(e):
   • If any of these bits are 0, the element is definitely not in the set.
   • If all these bits are 1, the element is probably in the set (it could be a false positive caused by other elements setting those same bits).

Trade-offs

• Memory vs. Accuracy: Increasing the size of the bit array m reduces the probability of false positives.
• Complexity: The choice of k (number of hash functions) and m (array size) determines the error rate.