# All Questions

47,703 questions
Filter by
Sorted by
Tagged with
4 views

### Computing the centroid of an "ellipsoid slice"

It is easy to compute the centroid (center-of-mass) of an ellipsoid in $\mathbb{R}^d$. I want to compute the centroid of a body of the following form: $$E\cap H_1\cap \cdots H_T$$ where $E$ is an ...
12 views

### Potential method for proving that dynamic table deletion runs in amortized constant time

Suppose we have a dynamic table that may contract when the load factor drops below a threshold value. Let $num_i$ be the number of elements after the $i$th operation and $size_i$ be the table capacity ...
8 views

### Subset sum problem with big items

Consider the variant of the Subset Sum problem, where the input is a list of $2 m + 1$ positive integers of sum $2 S$, and the goal is to find a subset with the largest sum that is at most $S$. The ...
4 views

### Variant of Bounded Subset Product

Consider the following decision problem: Given $([b_1, \cdots, b_n],t)$, where $[b_1, \cdots b_n]$ is an array of natural numbers and $t \le n^c$, do there exists natural numbers $f_1, \cdots f_n$ ...
1 vote
13 views

### Borůvka's step in linear time

I am trying to understand this Expected linear time MST algorithm, and I have a problem in the implementation of the Borůvka's step. My problem is with the removal of duplicate edges between merged ...
11 views

### DFA testing exercice ASAP please [duplicate]

I have a question : If my word can be only AA or BB or A or B how i will write my regular expression ? And if 0 is a par number it also may be to include ? it is something like this : A|B|epsilon) (AA|...
22 views

### Complexity of multiplying 3 matrices

There are algorithms that speed up matrix multiplication over the naive $n^3$ algorithm. But supposing you have 3 matrices $A$, $B$ and $C$, is there a way to compute $ABC$ that is asymptotically ...
19 views

### CFGs and Pushdown Automata

Is this the CFG for part (a), S -> AxxyxxA A -> Ax|ε If this is the answer then this grammar would accept &...
10 views

is true or false in C language, 1- External data structures are stored in main memory 2- If the OPERATE module uses an integer parameter passed by reference, I can call that module by passing an ...
11 views

### What is the largest "allowed" seed for a PRNG to not give any extra power to a deterministic machine?

Suppose a polynomial time machine that has an access to a polynomially long string of bits independent on the input. On average, it's impossible to compress this string to a subpolynomially long ...
5 views

54 views

### Can you compute a majority function of n-bits using an O(n) size circuit?

Are you able to construct a boolean circuit that computes the majority function of n bits where the circuit only takes up O(n) space? If so, what would that circuit look like? I have a feeling it has ...
1 vote
56 views

### Trouble Understanding Yao's "Basic Model" for Hashing

I am trying to understand the probing model proposed by Yao in the paper "Should Tables Be Sorted?". Yao suggests a "Basic Model" (in the section appropriately titled "Basic ...
1 vote
29 views

### Complexity class of a problem asking for a chance of receiving an item

I have asked a question on math.SE about if there is a way to do it better than by brute force, but this time I am interested in the complexity of the problem itself. I will repeat the problem, with a ...
1 vote
27 views

### Lower bounds on max-flow and assignment problems

As far as I know, all existing strongly polynomial algorithms for flows and assignment problem have $\Omega(V^3)$ complexity in the arithmetic model (assuming the graph is dense). I'm interested in ...
1 vote
84 views

### NP-hardness of modified distance-colouring of graphs

Given a graph $G =(V,E)$, a set of colors $\mathcal{C}=\{0,1,2,3,...,c-1\}$, and an integer $r$, I want to know if I can find a coloring procedure that can assign a color to each nodes (all nodes must ...
40 views

### Trying to implement BFS and I am stuck

I am trying to write down a code which would blindly search for a condition using breadth first search.I have been thinking of it for quite some time and I cant figure out how to continue. On the one ...
7 views

### Solve using checklist

Prove the correctness property of the following program using checklist. Identify inv P, bound function t. {{Q / n >= 0}} a:=0;b:= n + 1 {inv P / 2 ?\ (bound t: ??} b = a + 1 \rightarrow m:= (a + b)...
19 views

### Machine Learning Model for Multi-Lavel Classification

I am building a project to predict several labels that have continuous numbers in them. This is an example of the data. {'agent': {'center': [0.0018608339596539736, 0.1233854740858078, -3....
34 views

### How to create a 'hashing' function that maps up to 1 to N numbers uniquely to numbers 1 to N

I would like to use or create a hashing algorithm that takes K inputs from 1 to N and maps them uniquely to different numbers on 1 to N. K can be 1 to N. Ideally I would like the hashing alg to be ...
36 views

### supplying water for all houses of a city with either a well or pipe

Consider $n$ houses in a city which each house's water can be supplied with either a well or pipes from other houses. Constructing a well in a house $i$ costs $w_i$ and connecting a pipe from house $i$...
1 vote
45 views

### How to find the learned clause from a UIP cut

I would guess that this question is going to make some people wonder how I haven't already found a solution looking through papers -- but I do not see a clear algorithm. In implementing CDCL, I read ...
23 views

### $NL$ Leaf languages and $PSPACE$

I am reading Papadimitriou's Computational Complexity and got stuck on part d) of the following exercise (pg. 505) 20.2.14 A panorama of complexity classes. ... A language $L \subseteq \{0, 1\}^*$ ...
1 vote
38 views

### Communication complexity of Dyck language

I've been reading papers on streaming algorithms and ran across the following question which I haven't been able to answer: Consider the Dyck language $Dyck(2)$ over the alphabet $A = \{(,),[,]\}$ and ...
44 views

### Proving heaviest edge in mst is not heavier than heaviest edge of any possible spanning tree?

How to prove that the heaviest edge in mst is not heavier than heaviest edge of any possible spanning tree? by heaviest edge of any Spanning tree i mean considering any possible Spanning tree, we have ...
### Windowed LogLog/HyperLogLog algorithm to get a count of the cardinality of the set of the last $k$ elements?
LogLog/HyperLogLog provides a great way for estimating the cardinality of the set of $n$ objects. At its simplest, you hash all $n$ objects into binary strings, find the largest number of leading 0's \$...