User contributions for AlgorithmSoup

Search for contributionsshowhide

⧼contribs-top⧽

Username, IP address or CIDR range:

Namespace:

Invert selection

Associated namespace

Tag filter:

Invert selection

Only show edits that are latest revisions

Only show edits that are page creations

Hide minor edits

⧼contribs-date⧽

From date:

To date:

Show only edits pending review

Hide probably good edits

15:2415:24, 27 December 2024 diff hist −5 m Randomized algorithm No edit summary Tags: Visual edit Mobile edit Mobile web edit

21:3621:36, 10 December 2023 diff hist +23 m Hash table →History Tag: Visual edit

05:5205:52, 13 November 2023 diff hist +565 Linear probing →Primary Clustering: Expanded discussion of primary clustering. Tag: Visual edit
05:4805:48, 13 November 2023 diff hist +1,107 Linear probing No edit summary Tag: Visual edit: Switched
05:0705:07, 13 November 2023 diff hist −16 m Quadratic probing Fixed citations Tag: Visual edit
05:0405:04, 13 November 2023 diff hist +434 Quadratic probing Added historical reference for invention of quadratic probing. Tag: Visual edit
04:5804:58, 13 November 2023 diff hist +660 Quadratic probing Added citations for comparison to linear probing. Tag: Visual edit
04:3904:39, 13 November 2023 diff hist +603 List-labeling problem →Lower bounds and open problems: Added reference to state-of-art randomized upper bound Tag: Visual edit
04:3204:32, 13 November 2023 diff hist +711 Bloom filter →Alternatives: Fixed mistake in Pagh et al. bound, and added reference to succinct hash tables. Tag: Visual edit
04:1804:18, 13 November 2023 diff hist −164 Bloom filter →Alternatives: Put in correct sources for filters based on compact hash tables, and shortened the discussion to avoid zooming in on any overly specific results. Tag: Visual edit
03:5603:56, 13 November 2023 diff hist +1,307 Bloom filter →Alternatives: Added sources for filter space usage and for quotient filters; compressed cuckoo filters, which was previously discussed twice, to be discussed once. Tag: Visual edit

01:5501:55, 12 November 2023 diff hist +645 Perfect hash function →Minimal perfect hash function: Added discussion of theoretical bounds. Tag: Visual edit
01:3301:33, 12 November 2023 diff hist −525 NP-hardness Removed incorrect oracle-based definition. Note that the source that was cited for the oracle-based definition (see page 135 of the cited book "A First Course in Computability") actually gives the many-one reduction definition (which is the correct one). Tag: Visual edit
01:2901:29, 12 November 2023 diff hist +476 Talk:NP-hardness →Problem with definition: Reply Tag: Reply
01:0401:04, 12 November 2023 diff hist +561 Talk:NP-hardness →Problem with definition: Reply Tag: Reply

17:3417:34, 28 April 2023 diff hist −1 m Tombstone (disambiguation) →Other uses Tag: Visual edit
17:3317:33, 28 April 2023 diff hist +129 Tombstone (disambiguation) Added other use for lazy deletions Tag: Visual edit
17:3117:31, 28 April 2023 diff hist +252 Lazy deletion Added tombstone terminology Tag: Visual edit
17:2717:27, 28 April 2023 diff hist +319 Primary clustering →Effect on performance: Added clarification for how lazy deletions effect bounds. Tag: Visual edit
16:5616:56, 28 April 2023 diff hist 0 m Cuckoo filter →Algorithm description Tag: Visual edit
16:5616:56, 28 April 2023 diff hist +3 Cuckoo filter →Algorithm description Tag: Visual edit
16:1316:13, 28 April 2023 diff hist +962 Cuckoo filter →Algorithm description: Corrected some inaccuracies in the previous version of the article. Added the bin-size parameter b, and included citations to mathematical analyses on the minimum fingerprint size that must be used. Tag: Visual edit
15:1215:12, 28 April 2023 diff hist −29 Splay tree No edit summary
14:3914:39, 28 April 2023 diff hist +620 Splay tree →Variants: Added a citation connecting to succinct data structures. Tag: Visual edit
14:3314:33, 28 April 2023 diff hist +8 m Succinct data structure →Entropy-compressed solutions Tag: Visual edit
14:3014:30, 28 April 2023 diff hist +3,727 Succinct data structure →Succinct indexable dictionaries: Added literature on succinct hash tables, and removed C string example which, as pointed out in the talk section, was incorect. Tags: possible vandalism Visual edit
13:3813:38, 28 April 2023 diff hist +1,295 Succinct data structure →Succinct indexable dictionaries: Made section titles more precise and added space bounds for rank-only dictionaries. Tags: possible vandalism Visual edit

17:0817:08, 27 April 2023 diff hist +4 Primary clustering →Techniques for avoiding primary clustering Tag: Visual edit
17:0617:06, 27 April 2023 diff hist −138 m Primary clustering →Common misconceptions Tag: Visual edit
16:5916:59, 27 April 2023 diff hist +4 m Randomized algorithm →Number Theory Tag: Visual edit
16:3816:38, 27 April 2023 diff hist +7 m Primary clustering →Techniques for Avoiding Primary Clustering Tag: Visual edit
16:3616:36, 27 April 2023 diff hist +10 m Primary clustering →Effect on Performance Tag: Visual edit
16:2816:28, 27 April 2023 diff hist +3 m Primary clustering →Effect on Performance Tag: Visual edit
16:2716:27, 27 April 2023 diff hist −62 m Primary clustering →Causes of Primary Clustering Tag: Visual edit
16:2616:26, 27 April 2023 diff hist +6,357 Primary clustering Rewrote the article to no longer be a stub. Tag: Visual edit
00:4900:49, 27 April 2023 diff hist +30 Linear probing →Analysis: The previous version erroneously claimed a successful search time of O(1 + 1/(1 - \alpha)). But actually, that's the expected time to query a *random* key sucessessfully. I've fixed the typo. Tag: Visual edit
00:4300:43, 27 April 2023 diff hist −59 m Perfect hash function →Order preservation Tag: Visual edit
00:3300:33, 27 April 2023 diff hist +536 Perfect hash function →Order preservation: (1) Fixed an erroneous reference to Cuckoo hashing; (2) Fixed the discussion of [10]'s work, which was incorrect; (3) Added a citation to recent work establishing a lower bound of n \log \log \log n. Tags: possible vandalism Visual edit
00:1700:17, 27 April 2023 diff hist +6 Randomized algorithm →Data Structures: Improved the writing in the final paragraph Tag: Visual edit
00:0800:08, 27 April 2023 diff hist +434 Randomized algorithm →Data Structures: Added the bloom filter Tag: Visual edit
00:0300:03, 27 April 2023 diff hist +1 m Randomized algorithm →Number Theory Tag: Visual edit

23:5123:51, 26 April 2023 diff hist −14 m Randomized algorithm →Data Structures Tag: Visual edit
23:5023:50, 26 April 2023 diff hist 0 m Randomized algorithm →Sorting Tag: Visual edit
23:3523:35, 26 April 2023 diff hist 0 Randomized algorithm →Data Structures Tag: Visual edit
23:3423:34, 26 April 2023 diff hist −2 m Randomized algorithm →Number Theory Tag: Visual edit
23:3023:30, 26 April 2023 diff hist +5,000 Randomized algorithm →History: The history previously focused almost entirely on primality testing, and included a bunch of technical discussion that was orthogonal to the history. I've reduced the discussion of randomized primality testing to focus only on the historical aspects, and I have added historical discussion of several other major early directions. Tag: Visual edit

27 December 2024

10 December 2023

13 November 2023

12 November 2023

28 April 2023

27 April 2023

26 April 2023