User contributions for Admin
Jump to navigation
Jump to search
10 April 2023
- 08:3208:32, 10 April 2023 diff hist −12 Czumaj (Approximate MCOP Matrix Chain Multiplication) No edit summary Tags: Manual revert Reverted
- 08:3008:30, 10 April 2023 diff hist +2 Fourier–Motzkin elimination ( Linear Programming) No edit summary current
- 08:3008:30, 10 April 2023 diff hist 0 Brute-force search (3-Graph Coloring Graph Coloring) No edit summary current
- 08:3008:30, 10 April 2023 diff hist +11 Coppersmith–Winograd algorithm (Matrix Multiplication Matrix Product) No edit summary Tag: Manual revert
- 08:3008:30, 10 April 2023 diff hist −38 Strassen's algorithm (Matrix Multiplication Matrix Product) No edit summary Tags: Manual revert Reverted
- 08:3008:30, 10 April 2023 diff hist −11 Coppersmith–Winograd algorithm (Matrix Multiplication Matrix Product) No edit summary Tags: Manual revert Reverted
- 08:3008:30, 10 April 2023 diff hist +38 Strassen's algorithm (Matrix Multiplication Matrix Product) No edit summary Tags: Manual revert Reverted
- 08:3008:30, 10 April 2023 diff hist +3 Galil & Naamad ( Maximum Flow) No edit summary current
- 08:3008:30, 10 April 2023 diff hist +3 Edmonds & Karp ( Maximum Flow) No edit summary current
- 08:3008:30, 10 April 2023 diff hist −34 Wagner and Fischer (LCS Longest Common Subsequence) No edit summary current
- 08:3008:30, 10 April 2023 diff hist +66 Dynamic Programming Algorithm (S. S. Godbole) (Matrix Chain Ordering Problem Matrix Chain Multiplication) No edit summary current
- 08:3008:30, 10 April 2023 diff hist +1 Brute Force (Matrix Chain Ordering Problem Matrix Chain Multiplication) No edit summary current
- 08:3008:30, 10 April 2023 diff hist +4 Hoare's Selection Algorithm (QuickSelect) (kth Order Statistic kth Order Statistic) No edit summary current
- 08:3008:30, 10 April 2023 diff hist −13 Naive Selection (kth Order Statistic kth Order Statistic) No edit summary current
- 08:2908:29, 10 April 2023 diff hist +2 Heap Sort (Comparison Sorting Sorting) No edit summary current
- 08:2908:29, 10 April 2023 diff hist +2 Intro Sort (Comparison Sorting Sorting) No edit summary current
- 08:2908:29, 10 April 2023 diff hist 0 Bubble Sort (Comparison Sorting Sorting) No edit summary current
- 08:2908:29, 10 April 2023 diff hist +2 Merge Sort (Comparison Sorting Sorting) No edit summary current
- 08:2908:29, 10 April 2023 diff hist 0 Selection Sort (Comparison Sorting Sorting) No edit summary current
- 08:2908:29, 10 April 2023 diff hist 0 Naive sorting (Comparison Sorting Sorting) No edit summary current
- 08:2908:29, 10 April 2023 diff hist +388 N Nivasch (Cycle Detection Cycle Detection) Created page with "== Time Complexity == $O(\mu + \lambda)$ == Space Complexity == $O(\log\mu)$ Stack size (https://www.gabrielnivasch.org/fun/cycle-detection) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == not mentioned == Year == 2004 == Reference == https://drive.google.com/file/d/16H_lrjeaBJqWvcn07C_w-6VNHldJ-ZZl/view" current
- 08:2908:29, 10 April 2023 diff hist +400 N Sedgewick; Szymanski; and Yao (Cycle Detection Cycle Detection) Created page with "== Time Complexity == $(\mu + \lambda)({1}+\Theta({1}/sqrt(M)))$ == Space Complexity == M Memory cells (https://epubs.siam.org/doi/abs/10.1137/0211030?journalCode=smjcat) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1982 == Reference == https://epubs.siam.org/doi/abs/10.1137/0211030?journalCode=smjcat" current
- 08:2908:29, 10 April 2023 diff hist +380 N Eppstein (Subset Sum The Subset-Sum Problem) Created page with "== Time Complexity == $\tilde{O}(n max(S))$ == Space Complexity == $O(t logt)$ (https://dl.acm.org/doi/pdf/10.1145/3329863, Table 1) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S019667749690841X?via%3Dihub" current
- 08:2908:29, 10 April 2023 diff hist +305 N Compression/Clustering (Vector Quantization) (k-ANNS Nearest Neighbor Search) Created page with "== Time Complexity == Varies by codebook structure == Space Complexity == Varies by codebook structure (Table 2) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1992 == Reference ==" current
- 08:2908:29, 10 April 2023 diff hist +418 N Projected radial search (k-ANNS for a dense 3D map of geometric points Nearest Neighbor Search) Created page with "== Time Complexity == $O(k)$ == Space Complexity == $O({1})$ words (Derived: There are 5 local variables and no tables or lists aside from input/output) == Description == == Approximate? == Approximate Approximation Factor: ? == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2013 == Reference == http://www.araa.asn.au/acra/acra2013/papers/pap148s1-file1.pdf" current
- 08:2908:29, 10 April 2023 diff hist +474 N Locality-sensitive hashing (k-ANNS Nearest Neighbor Search) Created page with "== Time Complexity == $O(nLkt)$ (pre-processing) $O(L(kt+dnP_2^k))$ (query-time) == Space Complexity == $O(nL)$ hash table cells (https://en.wikipedia.org/wiki/Locality-sensitive_hashing#LSH_algorithm_for_nearest_neighbor_search) == Description == == Approximate? == Approximate Approximation Factor: c == Randomized? == No, deterministic == Model of Computation == == Year == 2010 == Reference == http://infolab.stanford.edu/~ullman/mmds/ch3n.pdf" current
- 08:2908:29, 10 April 2023 diff hist +419 N Hierarchical Navigable Small World (HNSW) (k-ANNS Nearest Neighbor Search) Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(M)$ bytes of memory (https://arxiv.org/abs/1603.09320, "Memory usage is proportional to choice of M") == Description == == Approximate? == Approximate Approximation Factor: ? experimental results == Randomized? == No, deterministic == Model of Computation == == Year == 2018 == Reference == https://doi.org/10.1109/TPAMI.2018.2889473" current
- 08:2808:28, 10 April 2023 diff hist +2 All-Integers 3SUM No edit summary current
- 08:2808:28, 10 April 2023 diff hist +2 3SUM' No edit summary current
- 08:2808:28, 10 April 2023 diff hist +4 Real 3SUM No edit summary current
- 08:2808:28, 10 April 2023 diff hist +4 3SUM No edit summary current
- 08:2808:28, 10 April 2023 diff hist +6 Bichromatic Hamming Close Pair No edit summary current
- 08:2808:28, 10 April 2023 diff hist +2 Dynamic Dihedral Rotation Queries No edit summary current
- 08:2808:28, 10 April 2023 diff hist +2 Static Dihedral Rotation Queries No edit summary current
- 08:2808:28, 10 April 2023 diff hist +55 Generalized Büchi Games No edit summary current
- 08:2808:28, 10 April 2023 diff hist +55 Disjunctive coBüchi Objectives No edit summary current
- 08:2808:28, 10 April 2023 diff hist −19 Disjunctive Queries of Safety in Graphs No edit summary current
- 08:2808:28, 10 April 2023 diff hist +6 Safety in Graphs No edit summary current
- 08:2808:28, 10 April 2023 diff hist −19 Conjunctive Safety Queries in MDPs No edit summary current
- 08:2808:28, 10 April 2023 diff hist −19 Disjunctive Safety Queries in MDPs No edit summary current
- 08:2808:28, 10 April 2023 diff hist +6 Safety in MDPs No edit summary current
- 08:2808:28, 10 April 2023 diff hist −19 Conjunctive Reachability Queries in MDPs No edit summary current
- 08:2808:28, 10 April 2023 diff hist −19 Disjunctive Reachability Queries in MDPs No edit summary current
- 08:2808:28, 10 April 2023 diff hist +6 Reachability in MDPs No edit summary current
- 08:2808:28, 10 April 2023 diff hist +2 RNA Folding No edit summary current
- 08:2808:28, 10 April 2023 diff hist +4 Ap-reach No edit summary current
- 08:2808:28, 10 April 2023 diff hist +4 2-sensitive incremental st-reach No edit summary current
- 08:2808:28, 10 April 2023 diff hist +4 1-sensitive incremental ss-reach No edit summary current
- 08:2808:28, 10 April 2023 diff hist +4 Constant sensitivity incremental ST-Reach No edit summary current
- 08:2808:28, 10 April 2023 diff hist +4 St-Reach No edit summary current