User contributions for Admin

15 February 2023

• 11:1711:17, 15 February 2023 diff hist +316‎ N WalkSAT (CNF-SAT Boolean Satisfiability) ‎ Created page with "== Time Complexity == $O(n*mt*mf)$ == Space Complexity == $O(n)$ (same as above) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == == Year == 1994 == Reference == https://www.aaai.org/Papers/AAAI/1994/AAAI94-051.pdf" current
• 11:1711:17, 15 February 2023 diff hist +327‎ N GSAT (CNF-SAT Boolean Satisfiability) ‎ Created page with "== Time Complexity == $O(n*mt*mf)$ == Space Complexity == $O(n)$ (derived in notes) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == == Year == 1992 == Reference == http://www.cs.cornell.edu/selman/papers/pdf/92.aaai.gsat.pdf" current
• 11:1711:17, 15 February 2023 diff hist +268‎ N Conflict-Driven Clause Learning (CDCL) (CNF-SAT Boolean Satisfiability) ‎ Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1999 == Reference == https://ieeexplore.ieee.org/document/769433" current
• 11:1711:17, 15 February 2023 diff hist +337‎ N Davis-Putnam-Logemann-Loveland Algorithm (DPLL) (CNF-SAT Boolean Satisfiability) ‎ Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n)$ Binary Search Tree (https://en.wikipedia.org/wiki/DPLL_algorithm) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1961 == Reference == https://dl.acm.org/doi/10.1145/368273.368557" current
• 11:1711:17, 15 February 2023 diff hist +277‎ N Zwick 2002 (Directed, Unweighted All-Pairs Shortest Paths (APSP)) ‎ Created page with "== Time Complexity == $O(V^{2.575})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2002 == Reference == https://dl.acm.org/doi/abs/10.1145/567112.567114" current
• 11:1711:17, 15 February 2023 diff hist +298‎ N Johnson's algorithm (Directed, Weighted (Arbitrary weights) All-Pairs Shortest Paths (APSP)) ‎ Created page with "== Time Complexity == $O(V^{2} log V + VE)$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == == Year == 1977 == Reference == https://dl.acm.org/doi/10.1145/321992.321993" current
• 11:1711:17, 15 February 2023 diff hist −22‎ Vaidya ( Linear Programming) ‎No edit summary
• 11:1711:17, 15 February 2023 diff hist 0‎ Fomin; Gaspers & Saurabh ( ‎No edit summary Tags: Manual revert Reverted
• 11:1711:17, 15 February 2023 diff hist +1‎ Goldberg & Rao (Parallel) (Integer Maximum Flow Maximum Flow) ‎No edit summary Tags: Manual revert Reverted
• 11:1711:17, 15 February 2023 diff hist −1‎ Goldberg & Rao (Parallel) (Integer Maximum Flow Maximum Flow) ‎No edit summary Tags: Manual revert Reverted
• 11:1711:17, 15 February 2023 diff hist −30‎ Kathuria, Liu, Sidford ( Maximum Flow) ‎No edit summary Tag: Manual revert
• 11:1711:17, 15 February 2023 diff hist +30‎ Kathuria, Liu, Sidford ( Maximum Flow) ‎No edit summary Tags: Manual revert Reverted
• 11:1711:17, 15 February 2023 diff hist +2‎ Chan (Boolean Matrix Multiplication (Combinatorial) Matrix Product) ‎No edit summary
• 11:1711:17, 15 February 2023 diff hist −9‎ Bansal, Williams (Boolean Matrix Multiplication (Combinatorial) Matrix Product) ‎No edit summary Tags: Manual revert Reverted
• 11:1711:17, 15 February 2023 diff hist +337‎ N Binary representation search with matrix multiplication (Unweighted Graph Diameter) ‎ Created page with "== Time Complexity == $O(V^omega log(V)$) where omega is the exponent on matrix multiplication == Space Complexity == $O(V^{2} logV)$ words (storing all the matrices) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -" current
• 11:1711:17, 15 February 2023 diff hist +255‎ N Dense APSP algorithm (Arbitrary edge weights, Dense graph Graph Diameter) ‎ Created page with "== Time Complexity == $O(V^{3} / {2}^(logV)$^{0.5}) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -" current
• 11:1711:17, 15 February 2023 diff hist +243‎ N Sparse APSP algorithm (Arbitrary edge weights, Sparse graph Graph Diameter) ‎ Created page with "== Time Complexity == $O(V^{2}logV+VE)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -" current
• 11:1711:17, 15 February 2023 diff hist +539‎ N Longest distance first (LDF) page replacement algorithm (Online Page Replacements) ‎ Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + information related to position of pages) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2017 == Reference == https://www.researchgate.net/profile/Gyanendra-Kumar-3/publication/319467661_A_Novel_Longest_Distance_First_Page_Replacement_Algorithm/links/59b209f1aca2728472d146..." current
• 11:1711:17, 15 February 2023 diff hist +470‎ N ARIES (Steal, No-Force Recovery) ‎ Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$? words (Uses write-ahead logging, so keeps track of transaction log, whose entries may be augmented with O(1) more information each. During recovery, needs to keep track of variable/page states) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1992 == Reference == https://dl.acm.org/doi/10.1145/128765.128770" current
• 11:1711:17, 15 February 2023 diff hist +292‎ N Aging (Online Page Replacements) ‎ Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + reference counters only) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==" current
• 11:1711:17, 15 February 2023 diff hist +292‎ N Not frequently used (NFU) (Online Page Replacements) ‎ Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + reference counters only) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==" current
• 11:1711:17, 15 February 2023 diff hist +254‎ N Random (Online Page Replacements) ‎ Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(k)$? words (Need to keep track of cache?) == Description == == Approximate? == Exact == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1940 == Reference ==" current
• 11:1711:17, 15 February 2023 diff hist +325‎ N Least recently used (Online Page Replacements) ‎ Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + info related to time last referenced for each of k pages) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==" current
• 11:1711:17, 15 February 2023 diff hist +288‎ N Second-chance (Online Page Replacements) ‎ Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + reference bits only) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==" current
• 11:1711:17, 15 February 2023 diff hist +304‎ N Clock (Online Page Replacements) ‎ Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + reference bits only (plus iterator)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==" current
• 11:1711:17, 15 February 2023 diff hist +288‎ N First-in, first-out (Online Page Replacements) ‎ Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + reference bits only) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==" current
• 11:1711:17, 15 February 2023 diff hist +288‎ N Not recently used (Online Page Replacements) ‎ Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + reference bits only) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==" current
• 11:1711:17, 15 February 2023 diff hist +370‎ N The theoretically optimal page replacement algorithm (Offline Page Replacements) ‎ Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(k)$ words (Need to keep track of cache; linear scan for searching for page not being used for the longest only requires O(1) auxiliary space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==" current
• 11:1711:17, 15 February 2023 diff hist +444‎ N Banker's Algorithm (Deadlock Avoidance Deadlock avoidance) ‎ Created page with "== Time Complexity == $O(mn^{2})$ == Space Complexity == $O(mn)$ words (Main space-consuming arrays needed include "Max," "Allocation," and "Need," which are all n*m arrays. Other arrays are either O(n) or O(m)-sized) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1966 == Reference == https://www.cs.utexas.edu/users/EWD/ewd01xx/EWD108.PDF" current
• 11:1711:17, 15 February 2023 diff hist +288‎ N Multilevel queue scheduling (Unweighted Interval Scheduling, Online?? Interval Scheduling) ‎ Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above; also level information for each task) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==" current
• 11:1711:17, 15 February 2023 diff hist +231‎ N Work-conserving schedulers (Unweighted Interval Scheduling, Online?? Interval Scheduling) ‎ Created page with "== Time Complexity == $O(n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==" current
• 11:1711:17, 15 February 2023 diff hist +250‎ N Round-robin scheduling (Unweighted Interval Scheduling, Online?? Interval Scheduling) ‎ Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==" current
• 11:1711:17, 15 February 2023 diff hist +250‎ N First come, first served (Unweighted Interval Scheduling, Online?? Interval Scheduling) ‎ Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==" current
• 11:1711:17, 15 February 2023 diff hist +250‎ N Shortest remaining time first (Unweighted Interval Scheduling, Online?? Interval Scheduling) ‎ Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==" current
• 11:1711:17, 15 February 2023 diff hist +367‎ N Priority scheduling (Unweighted Interval Scheduling, Online?? Interval Scheduling) ‎ Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (Keep track of (sorted, based on criteria) list of (unscheduled, running, etc.; just un-done) tasks, along with machine statuses) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==" current
• 11:1711:17, 15 February 2023 diff hist +320‎ N $O(n\log n)$ Dynamic Programming (Weighted Activity Selection Problem Interval Scheduling) ‎ Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Keep track of answers to O(n) subproblems (cache), and sorted list of intervals) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1953 == Reference =="
• 11:1711:17, 15 February 2023 diff hist +320‎ N $O(n^2)$ Dynamic Programming (Weighted Activity Selection Problem Interval Scheduling) ‎ Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Keep track of answers to O(n) subproblems (cache), and sorted list of intervals) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1953 == Reference ==" current
• 11:1711:17, 15 February 2023 diff hist +391‎ N Fixed priority shortest job first (Unweighted Interval Scheduling, Online?? Interval Scheduling) ‎ Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n+k)$? words (Keep track of (sorted, based on criteria) list of (unscheduled, running, etc.; just un-done) tasks, along with machine statuses and task priorities) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==" current
• 11:1711:17, 15 February 2023 diff hist +295‎ N $O(n^3)$ Dynamic Programming (Weighted Activity Selection Problem Interval Scheduling) ‎ Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Keep track of answers to O(n^2) subproblems (i, j)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1953 == Reference ==" current
• 11:1711:17, 15 February 2023 diff hist +292‎ N Brute force algorithm (Weighted Activity Selection Problem Interval Scheduling) ‎ Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n)$ words (Need to keep track of which subset is being checked) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==" current
• 11:1711:17, 15 February 2023 diff hist +386‎ N Sthele, Zimmermann (Greatest Common Divisor Greatest Common Divisor) ‎ Created page with "== Time Complexity == $O(n log^{2} n log log n)$ == Space Complexity == $O(n)$?? bits (Depends on Schonhage-Strassen multiplication) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? words size O(1) == Year == 2006 == Reference == https://hal.inria.fr/file/index/docid/71533/filename/RR-5050.pdf"
• 11:1711:17, 15 February 2023 diff hist +338‎ N Binary GCD algorithm (Greatest Common Divisor Greatest Common Divisor) ‎ Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ bits (Store only the current values being iterated on) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? words size O(1) == Year == 1967 == Reference == https://arxiv.org/abs/0910.0095" current
• 11:1711:17, 15 February 2023 diff hist +304‎ N Euclid's algorithm (Greatest Common Divisor Greatest Common Divisor) ‎ Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ bits (Store only the current values being iterated on) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? words size O(1) == Year == -300 == Reference ==" current
• 11:1711:17, 15 February 2023 diff hist +352‎ N Lehmer's GCD algorithm (Greatest Common Divisor Greatest Common Divisor) ‎ Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ bits (Store only the current values being iterated on, and an O(1)-sized matrix with O(n)-bit numbers) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? words size O(1) == Year == 1940 == Reference ==" current
• 11:1711:17, 15 February 2023 diff hist +349‎ N Calvetti, Reichel (2-D Polynomial Interpolation Polynomial Interpolation) ‎ Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$? words ((maybe similar to the other O(n^2) algorithms?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1993 == Reference == https://link.springer.com/article/10.1007/BF01990529" current
• 11:1711:17, 15 February 2023 diff hist +399‎ N Bjorck (2-D Polynomial Interpolation Polynomial Interpolation) ‎ Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (https://academic.oup.com/imajna/article/8/4/473/758789?login=true) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1970 == Reference == https://www.jstor.org/stable/2004623?origin=crossref&seq=5#metadata_info_tab_contents" current
• 11:1711:17, 15 February 2023 diff hist +379‎ N Higham (2-D Polynomial Interpolation Polynomial Interpolation) ‎ Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (https://academic.oup.com/imajna/article/8/4/473/758789?login=true) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1988 == Reference == https://academic.oup.com/imajna/article/8/4/473/758789?login=true" current
• 11:1711:17, 15 February 2023 diff hist +316‎ N Gaussian elimination (2-D Polynomial Interpolation Polynomial Interpolation) ‎ Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Requires computation of inverse of O(n^2)-sized Vandermonde matrix) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == -150 == Reference ==" current
• 11:1711:17, 15 February 2023 diff hist +529‎ N Rijndael / AES (Block Ciphers Block Ciphers) ‎ Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$? bits (Network generally operates on the O(n) bits over O(k) rounds, each round having roughly the same structure (so structure of rounds require O(1) bits to describe)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2001 == Reference == https://csrc.nist.gov/csrc/media/projects/cryptographic-standards-and-guid..." current
• 11:1711:17, 15 February 2023 diff hist +416‎ N Blowfish (Block Ciphers Block Ciphers) ‎ Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$? bits (Network has a constant number of rounds and operates on O(n) bits, thus structure should require O(n) bits to describe) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference == https://link.springer.com/chapter/10.1007/3-540-58108-1_24" current