# Tag Info

38

The standard algorithm for finding a maximum still works. Start with $a_1$ and go over the elements, if you see a larger value, update the maximum to be that value. The reason this works is that every element you skipped is smaller than at least one element, and can thus not be the maximum. To be clear, by the "standard algorithm" I mean the following: max ...

24

As Ariel notes, the standard maximum-finding algorithm given below: def find_maximum(a): m = a[0] for x in a: if x > m: m = x return m will in fact work without modification as long as: any pair of elements can be compared, and the input is guaranteed to contain a maximal element, i.e. an element that is pairwise greater than any ...

11

You asked: Can we run a sorting algorithm, feeding it a non-transitive comparator? The answer: Of course. You can run any algorithm with any input. However, you know the rule: Garbage In, Garbage Out. If you run a sorting algorithm with a non-transitive comparator, you might get nonsense output. In particular, there is no guarantee that the output will ...

5

You want to know the orbits of the action of the automorphism group of a graph on its vertices. This is equivalent to graph isomorphism, for which no really simple algorithms are known. Practical graph isomorphism algorithms, which work fast in practice, are known – check nauty for example. Apparently nauty can compute the automorphism group directly, from ...

4

"greatest means the element must be greater than every other element" is a huge hint on how to do this in $O(n)$. If you go through your list comparing elements, any element that "loses" a comparison can be immediately discarded as, in order to be the greatest, it must be greater than ALL other elements so the single loss disqualifies it. Once you think of ...

4

There's a very simple algorithm for this: for each edge (u,v) in the graph: for each edge (v,w) in the graph: if (u,w) is not in the graph, return "Not transitive" return "Transitive" Basically, if the graph is not transitive, then you can always find some path of length two $u\to v \to w$ such that the edge $u \to w$ is not present in the ...

4

Given a set of elements and a binary ordering relation, transitivity is required to totally order the elements. In fact, transitivity is even required to define a partial order on the elements. http://en.m.wikipedia.org/wiki/Total_order You would need a much broader definition of what "sorted" means in order to sort elements without transitivity. It is ...

3

I assume that the relation antisymmetric for at least a single element (which guarantees the existence of the greatest element), otherwise the task is impossible. If all elements in the finite set are comparable then usual finding-maximum procedure works. If some elements are not comparable then the following procedure will work max = nil For i=1 to n ...

2

It sounds as though what you want is to arrange items such that all discernible rankings are correct, but items which are close might be considered "indistinguishable". It is possible to design sort algorithms which will work with such comparisons, but unless there are limits to how many comparisons may report that things are indistinguishable, there is no ...

2

As an addition to Ariel's answer about the concerns raised by Emil Jeřábek: If we allow $A<B$ and $B<A$ then there is no O(n) algorithm: Assume you have elements $A_1 ... A_n$. Your algorithm will in each step query $A_i<A_j$ for some pair i and j. No matter in which order you query them, there is always a relation where you have to query all ...

1

There's a $O(n^\omega)$-time algorithm that outputs a count, for each vertex, of the number of triangles that include that vertex. Here $O(n^\omega)$ is the running time for matrix multiplication. See, e.g., Number of triangles in an undirected graph, Is it a valid graph canonical form?, https://cstheory.stackexchange.com/q/9972/5038. This may or may not ...

1

I'm going to cheat and call the number of A > B entries $n$ and you need to look at every entry at least once. That way you can loop over just the entries and remove the element that is less than the other from the set of possible solutions. With a hashset or similar this is possible in $O(n)$

1

(Note: I'm not 100% sure about the Alloy syntax since I never used it -- what follows is accurate on the general principles but the syntax could be slightly different) Basically, S.*bar means starting from S and using .bar any number $n\geq 0$ of times. Instead, S.^bar means starting from S and using .bar any positive number $n > 0$ of times. It is ...

Only top voted, non community-wiki answers of a minimum length are eligible