Timeline for Deterministic linear time algorithm to check if one array is a sorted version of the other
Current License: CC BY-SA 4.0
26 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 3, 2018 at 21:13 | vote | accept | Albert Hendriks | ||
| May 3, 2018 at 21:12 | history | edited | Albert Hendriks | CC BY-SA 4.0 |
deleted 139 characters in body
|
| May 18, 2016 at 10:20 | history | edited | Albert Hendriks | CC BY-SA 3.0 |
deleted 62 characters in body
|
| May 18, 2016 at 8:44 | comment | added | Yuval Filmus | @AlbertHendriks You (most probably) can't sort an array in $O(n\log n)$ on a Turing machine. Some lower bounds on SAT (e.g. cs.cmu.edu/~ryanw/automated-lbs.pdf) are actually for the RAM machine, sorry for my misleading earlier comment. | |
| May 18, 2016 at 8:41 | comment | added | Yuval Filmus | @atayenel $1+4 = 2+3$. | |
| May 18, 2016 at 7:17 | comment | added | atakanyenel | Why don't you just sum the items in the array and then compare the summation ? Regarding your title, it is linear and answers the question 'is one array the sorted version of other? '. I'm aware that it is not the Turing machine model, but a practical solution. | |
| May 18, 2016 at 6:55 | comment | added | Albert Hendriks | ah, then that's the model I'm looking for. I adjusted the question. | |
| May 18, 2016 at 6:55 | history | edited | Albert Hendriks | CC BY-SA 3.0 |
deleted 306 characters in body
|
| May 17, 2016 at 22:27 | comment | added | Yuval Filmus | The statement you quote is about the Turing machine model, which is only of theoretical interest. Algorithms are usually analyzed with respect to the RAM model. | |
| May 17, 2016 at 18:43 | history | edited | Albert Hendriks | CC BY-SA 3.0 |
clarification about models.
|
| Jan 6, 2016 at 10:53 | history | edited | Albert Hendriks | CC BY-SA 3.0 |
added 1 character in body
|
| Jan 6, 2016 at 10:47 | history | edited | Albert Hendriks | CC BY-SA 3.0 |
added 233 characters in body
|
| Jan 6, 2016 at 10:19 | answer | added | Yuval Filmus | timeline score: 10 | |
| Jan 6, 2016 at 10:04 | history | edited | Albert Hendriks | CC BY-SA 3.0 |
added 40 characters in body
|
| Jan 6, 2016 at 7:29 | history | edited | Albert Hendriks | CC BY-SA 3.0 |
added 71 characters in body
|
| Jan 5, 2016 at 18:31 | comment | added | KWillets | FWIW the probabilistic approach is hashing with an order-independent hash function. Carter and Wegman wrote one of the original papers on this (sciencedirect.com/science/article/pii/0022000081900337), but I haven't seen anything in the citations of that paper that suggests a deterministic algorithm (so far). | |
| Jan 5, 2016 at 16:21 | answer | added | Yuval Filmus | timeline score: 14 | |
| Jan 5, 2016 at 1:28 | history | edited | Raphael |
edited tags
|
|
| Jan 4, 2016 at 21:13 | history | edited | D.W.♦ | CC BY-SA 3.0 |
Improve problem statement, to make it reflect the original intent more closely. Add tag.
|
| S Jan 4, 2016 at 21:09 | history | suggested | costrom | CC BY-SA 3.0 |
Edited title for spelling
|
| Jan 4, 2016 at 21:08 | review | Suggested edits | |||
| S Jan 4, 2016 at 21:09 | |||||
| Jan 4, 2016 at 21:06 | history | edited | Kaveh | CC BY-SA 3.0 |
deleted 85 characters in body; edited tags; edited title
|
| Jan 4, 2016 at 20:44 | history | tweeted | twitter.com/StackCompSci/status/684113182617632770 | ||
| Jan 4, 2016 at 20:24 | history | edited | Juho | CC BY-SA 3.0 |
improved presentation
|
| Jan 4, 2016 at 20:20 | history | edited | Albert Hendriks | CC BY-SA 3.0 |
edited body
|
| Jan 4, 2016 at 20:09 | history | asked | Albert Hendriks | CC BY-SA 3.0 |