4 votes

Functional programming with branches that have no order?

Here's the problem: You always need some way to resolve ambiguity when there are overlapping clauses There is no easy syntactic way to ensure that clauses don't overlap. So, if you can think of a ...
Joey Eremondi's user avatar
3 votes
Accepted

Lamport Timestamps and Causality

No, there is no inherent logical/temporal inconsistency in the events described in the question, although it can be considered "unfair" that process P2 can receive and broadcast messages ...
John L.'s user avatar
  • 38.8k
3 votes
Accepted

Designing a Queue that efficiently tracks position

One simple data structure is a balanced binary tree, with members stored in the leaves, and augmented so that each internal node also stores the number of leaves under it. Now you can implement all ...
D.W.'s user avatar
  • 158k
3 votes
Accepted

Understanding the bandwidth problem on graphs

I think you got the definition of bandwidth wrong. Here is your definition of the bandwidth of an ordering of the vertices: The bandwidth is the maximum distance in the graph between adjacent nodes ...
Yuval Filmus's user avatar
2 votes

Functional programming with branches that have no order?

If you restrict yourself to using constructors of datatypes, the compiler knows what can happen during pattern matching. For instance, assume your integer type is defined by this: ...
Raphael's user avatar
  • 72.3k
2 votes

Algorithm for detecting overlaps

@Tassle algorithm works great but needs more explaining for vectors ordering. To do so, put all your starting and ending times in a vector and sort them in increasing order, breaking ties by ...
Eduardo Yamauchi's user avatar
2 votes
Accepted

Algorithm for detecting overlaps

I suppose you want to delete as little EmptyEvents as possible. In that case, you can achieve what you want in O(nlog(n)) time, where ...
Tassle's user avatar
  • 2,442
2 votes
Accepted

Random observations of a total ordering, how much they tell us?

Answer to Question 1 We can assume without loss of generality that the original ordering is the usual one: $a_1 < a_2 < \cdots < a_n$. Some ordering $\pi$ is compatible with our observations ...
Yuval Filmus's user avatar
2 votes
Accepted

Extend reachability to total ordering

You can compute a topological ordering of the vertices in linear time.
Yuval Filmus's user avatar
2 votes
Accepted

Sort by typical position?

As I understand your question, your problem statement is: Given a set of ordered lists $\{L_1,L_2,\ldots,L_n\}$, learn the relation $r(a,b)$ for the partial order of each $L_1,L_2,\ldots,L_n$. Then ...
giusti's user avatar
  • 220
2 votes
Accepted

How to sort objects based only on "less than" relationships?

What you are looking for is a comparison sort. Please take a look at that article. Let us state clearly the requirement for any two given objects, object i and object j when they appear in the final ...
John L.'s user avatar
  • 38.8k
2 votes

totally ordered semigroups

Monogenic semigroups. Consider the case of a [monogenic semigroup](monogenic semigroup), that is, a semigroup $S$ generated by a single element $s$. If $S$ is finite, then it can be totally ordered if ...
J.-E. Pin's user avatar
  • 6,089
2 votes

How come the set of all binary strings is uncountable?

Suppose you have the set of all the infinite binary strings (i.e. $\Sigma^{\omega}$), then whatever enumeration $E = (s_1, s_2, s_3, ... )$ you build for them you can build a string $s'$ that is not ...
Vor's user avatar
  • 12.5k
2 votes
Accepted

Producing a total or partial order from an inconsistent relation

It's hard to say without more context and more modelling. It will require some assumptions on how the results of the comparison function relate to the (hidden) desired total order. It's possible you ...
D.W.'s user avatar
  • 158k
2 votes

Generating Unique Ids for Objects

A simple observation is that when an object is assigned an id, that id never increases, i.e., it either stays the same or decreases. So keep a global counter $g$ for giving ids, initially set to 0. ...
Juho's user avatar
  • 22.5k
2 votes
Accepted

What happens when two different nodes have the same Lamport clock ID

tl;dr As Lamport writes at the top of page 561 of Time, Clocks, and the Ordering of Events in a Distributed System: To break ties, we use any arbitrary total ordering $\prec$ of the processes. To ...
Kai's user avatar
  • 855
2 votes
Accepted

Efficient ways to sort pairwise distances for set of points in Euclidean space?

A better solution could be as follows: Create a min heap over $n^2$ line segments. Take the top element of the heap, check if it satisfies condition $C$. If it does not satisfy it, pop it out. If it ...
Inuyasha Yagami's user avatar
1 vote

Interactive sort for only top elements

A similar question has been considered in the literature: given a poset $P$ and a list of elements whose order is consistent with $P$, how many comparisons are needed in order to order the list? If ...
Yuval Filmus's user avatar
1 vote

Partition an array in two groups while keeping the relative order within both groups

Yes, there is such an algorithm. Hint:
D.W.'s user avatar
  • 158k
1 vote
Accepted

Is there a sub-NP algorithm to satisfy or prove unsatisfiable a set of a<b<c OR c<b<a constraints

This is known as the betweenness problem. It is in NP (you can easily check the correctness of any proposed solution in polynomial time), and is NP-hard.
D.W.'s user avatar
  • 158k
1 vote
Accepted

How come the set of all binary strings is uncountable?

Ok more theoretic proof here If you are only looking at finite strings by definition $$\Sigma_{bool}^* = \bigcup_{i \in \mathbb{N}} \Sigma_{bool}^i$$ (where $\Sigma_{bool}^i$ is the set of strings of ...
tbrugere's user avatar
  • 126
1 vote
Accepted

Black-Box Machine

This answer supposes that you know $n$ in advance, but can be adapted to the general case. ...
Yuval Filmus's user avatar
1 vote

Which order is "lexicographic order"?

I think this is the rule: if it is said to be lexicographic, then it is, it follows a particular order, as if the items are printed in a dictionary or phone book. So for example: ...
nonopolarity's user avatar
1 vote

Which order is "lexicographic order"?

There is no one universally accepted lexographical ordering. Any author is free to introduce their own ordering, as long as it is consistent within their scope of discussion. It's just like binary ...
RandomPerfectHashFunction's user avatar
1 vote

Creating a numbered list, divided into types, without need for shifting or re-ordering - is this a re-occuring problem

You might be looking for an enum. See https://en.wikipedia.org/wiki/Enumerated_type.
D.W.'s user avatar
  • 158k

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