# Tag Info

### 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 ...
• 29.7k
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 ...
• 38.8k
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 ...
• 158k
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 ...
• 276k

### 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: ...
• 72.3k

### 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 ...
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 ...
• 2,442
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 ...
• 276k
Accepted

### Extend reachability to total ordering

You can compute a topological ordering of the vertices in linear time.
• 276k
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 ...
• 220
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 ...
• 38.8k

### 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 ...
• 6,089

### 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 ...
• 12.5k
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 ...
• 158k

### 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. ...
• 22.5k
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 ...
• 855
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 ...
• 6,112
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 ...
• 276k
1 vote

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

Yes, there is such an algorithm. Hint:
• 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.
• 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 ...
• 126
1 vote
Accepted

### Black-Box Machine

This answer supposes that you know $n$ in advance, but can be adapted to the general case. ...
• 276k
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: ...
• 403
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 ...
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.
• 158k

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