# All Questions

42,733 questions
Filter by
Sorted by
Tagged with
19 views

### When Triangulating monotone polygons, how can diagonals be added to a DCEL in constant time?

I am working on the polygon triangulation algorithms from "Computational Geometry - Algorithms and applications 3rd ed", chapter 4. I've managed to turn polygons into y-monotone polygons ...
15 views

### Efficient way to do self join with minimum support?

In the apriori algorithm there's the self join step, So, say we have 1 3 2 3 3 5 2 5 If I were to do an exhaustive join I'd end up with a tuple including (1, 3, ...
37 views

### Find all combinations of adjacent records matching a graph template

I have a graph theory or combinatorics problem that probably has a solution, but I haven't been able to find it. The problem can be simple: in the second figure below, choose one yellow block from ...
38 views

### A question about hash problems in CLRS book

Consider the following problem 11.2-6 from CLRS book: Suppose we have stored $n$ keys in a hash table of size $m$, with collisions resolved by chaining, and that we know the length of each chain, ...
41 views

### How do I use the definition of the "Big-Oh" notation to prove the following statements? [closed]

I need help figuring out how to prove the following statement using the definition of "Big-Oh" notation which says that ...
1k views

### Does the Minimum Spanning Tree include the TWO lowest cost edges?

Wikipedia's Minimum Spanning Tree reads: Minimum-cost edge If the minimum cost edge e of a graph is unique, then this edge is included in any MST. Proof: if e was not included in the MST, removing ...
19 views

### How to build a minimal string matching DFA with limited memory?

I am working on finite state machine pruning, a problem that requires me to build finite state machines (in the manner of the Aho Corasic algorithm) to match an evolving input string against a set of ...
21 views

26 views

### File Format and data type

Why different format type for different data is needed?? Is each one useful for different things, or are they just being promoted by different software vendors?
52 views

### Graph coloring problem with violations

I would like a name for the following problem. We consider a relaxed vertex coloring problem, where Let $k$ be the number of colors Let $B$ be the set of edges violating coloring, i.e., B := \{(u,...
48 views

### Automated Query Equivalence Solver (MongoDB)

The query-equivalence problem is undecidable. However there are theorem provers that attempt to solve instances of undecidable problems. I am curious how I could go about using an automatic theorem ...