5 ms·

... Why does nobody understand how the adversarial method works? What I'm basically saying is that the usage of the comparator to create elements on the fly IS

... Why does nobody understand how the adversarial method works? What I'm basically saying is that the usage of the comparator to create elements on the fly IS NOT LEGAL if you are trying to break randomized quicksort because this requires the adversary to have PRIOR KNOWLEDGE of the elements. He doesn't if its randomized.

sesqu 16y ago
First of all, we're not trying to break a proof of anything. There's a demonstrated attack on comparator-based sorts. Whether you want to allow the scenario doesn't much change the fact that that scenario is vulnerable. Second, this method does not require prior knowledge of the elements. In fact, it disallows a large amount of information (the ordering). What prior knowledge are you claiming the adversary doesn't have but requires? He provides the set, so he has full knowledge of the members of the set (though the sorter doesn't, so this is useless knowledge). It's an unordered set with a full ordering relation, so a random permutation on initial indices will have no effect. He is the comparator, and thus has full knowledge of that as well. There is nothing else to know. Now, you might object to the fact that the comparator is not a deterministic automaton, which is the assumption exploited, and I wish you good luck in enforcing that in your sorting routines.
- jchonphoenix 16y ago
  Sigh. I give up. I'll just suggest you open up a copy of clrs and read the section on randomized quick sort. There is a section dealing with this killer adversary exactly and why this adversary does not kill randomized quick sort. Your logic is failing because your thinking of this from a programmers perspective when, in reality this is an algorithm analysis problem which is theory.
  - sesqu 16y ago
    I don't have that book, so you'll have to explain the reasoning if you want to convince me. I did find the MIT OCW lecture transcript on randomized quicksort, based on the book, and it described how randomization probably defeats an adversary supplying a worst-case initial permutation when the pivoting algorithm is known. That's a different adversary to the one we are discussing, even if relaxed; it has to supply an input that is consistent and fixed. They also motivated the scenario in terms of competition, which I find less reasonable than actual malevolence, but that bears little relevance now. When theory and practise diverge, there is strong reason to hold the practise as more defensible than the theory. How would you say the practice should be amended to not suffer from this problem that is apparently not extant in theory? I hold that it cannot, for this adversary is more capable than the other.

sesqu 16y ago

First of all, we're not trying to break a proof of anything. There's a demonstrated attack on comparator-based sorts. Whether you want to allow the scenario doesn't much change the fact that that scenario is vulnerable. Second, this method does not require prior knowledge of the elements. In fact, it disallows a large amount of information (the ordering). What prior knowledge are you claiming the adversary doesn't have but requires? He provides the set, so he has full knowledge of the members of the set (though the sorter doesn't, so this is useless knowledge). It's an unordered set with a full ordering relation, so a random permutation on initial indices will have no effect. He is the comparator, and thus has full knowledge of that as well. There is nothing else to know. Now, you might object to the fact that the comparator is not a deterministic automaton, which is the assumption exploited, and I wish you good luck in enforcing that in your sorting routines.

jchonphoenix 16y ago
Sigh. I give up. I'll just suggest you open up a copy of clrs and read the section on randomized quick sort. There is a section dealing with this killer adversary exactly and why this adversary does not kill randomized quick sort. Your logic is failing because your thinking of this from a programmers perspective when, in reality this is an algorithm analysis problem which is theory.
- sesqu 16y ago
  I don't have that book, so you'll have to explain the reasoning if you want to convince me. I did find the MIT OCW lecture transcript on randomized quicksort, based on the book, and it described how randomization probably defeats an adversary supplying a worst-case initial permutation when the pivoting algorithm is known. That's a different adversary to the one we are discussing, even if relaxed; it has to supply an input that is consistent and fixed. They also motivated the scenario in terms of competition, which I find less reasonable than actual malevolence, but that bears little relevance now. When theory and practise diverge, there is strong reason to hold the practise as more defensible than the theory. How would you say the practice should be amended to not suffer from this problem that is apparently not extant in theory? I hold that it cannot, for this adversary is more capable than the other.