All Questions
47,703
questions
0
votes
0
answers
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 ...
- 5,690
0
votes
0
answers
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 ...
- 52
0
votes
0
answers
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 ...
- 5,690
0
votes
1
answer
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
1
vote
0
answers
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 ...
- 12.5k
-4
votes
0
answers
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|...
0
votes
1
answer
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 ...
- 101
-1
votes
1
answer
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 &...
- 1
-1
votes
0
answers
10
views
about C language [closed]
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 ...
- 1
0
votes
1
answer
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 ...
- 1,417
0
votes
0
answers
5
views
Greedy algorithm for criptocurrency problem
Assume the following hypothetic scenario:
You know the values $v_1^0, \ldots, v_n^0$ of $n$ criptocurrencies. You know the
values this currencies will have for the following $m$ days; this is, $v_0^1,...
- 181
0
votes
0
answers
4
views
Understanding atomic requests/transactions in a snooping coherence protocol
I've been reading the book "A Primer on Memory Consistency and Cache Coherency", and it contains the following paragraph:
The Atomic Requests property states that a coherence request is
...
- 111
0
votes
0
answers
25
views
Complexity of topological sorting with a special restriction
Let $G = (V, E)$ be a connected DAG (representing a circuit) with every vertex may be one of the following three types:
Input variable, with in-degree $0$ and out-degree $\geqslant 1$.
A gate, with ...
- 13
0
votes
0
answers
20
views
How do i make a 2d array as same as i possibly can with another one?
Say i have an 2d array A of nxn size, int values already given for each item.these values can be the same or different.
There's gonna be another nxn array B being input. I can only interchange one row ...
0
votes
2
answers
89
views
Could this novel algorithm be qualified to be published in Nature or Science
I recently designed an algorithm for single-source shortest paths in graph structures, which can limit the number of transfers as Bellman-Ford while approaching the performance of SPFA. Of course, it ...
-1
votes
0
answers
8
views
How to do this in address translation of paging?
Consider a memory-management system based on paging.
The total size of the physical memory is 2 GB, laid out over pages of size 8 KB.
The logical address space of each process has been limited to 256 ...
- 99
0
votes
0
answers
10
views
Necklace Alignment Problem
We are given two cyclic $\{0,1\}$ strings $X$ and $Y$ with both length $n$, containing $k$ 0s and $n-k$ 1s. Suppose positions in $X$ are $x_0,\dots,x_{k-1}$, for $Y$ are $y_0,\dots,y_{k-1}$. We assume ...
- 1
-1
votes
0
answers
12
views
Clique to SAT example explanation
We are at college trying to implement the reduction of the clique problem to a SAT problem but I dont quite get the examples of the slides if someone can give me a not so technical explanation of what'...
0
votes
1
answer
24
views
What's the Time Complexity and total no of iterations?
for a=1 to m means for(a=1;a<=m;a++)
for i=1 to n
for j=i to n
c= c+1;
The total no of iterations is O(n^2)
...
-2
votes
0
answers
7
views
Construct a pda
Construct the pda that accept following language
L * 1 = {a ^ m * b ^ n / 2 * n <= m <= 3n, n >= 1}
Trace the operation of M on the string aaaaabb
1
vote
0
answers
29
views
Why bisection width of star connected network is 1?
This may seem like a simple question, but I can neither find the answer on the internet nor AI tools can give a proper answer. I was reading a book about static networks and I saw that the bisection ...
- 11
1
vote
0
answers
16
views
How do I prove relations of two CTL formulas?
If I have two CTL equations, how do I prove they're equivalent or that one implies the other?
What's the general approach? Disproving is obvious, but I am unable to figure out how to prove the ...
- 121
0
votes
3
answers
51
views
Testing whether a number (N) is prime or not can be made very fast but it will require storage space
Testing whether a number (N) is prime or not can be made very fast but it will require storage space.
If there is a central repository that stores all prime numbers found till now and if there is a ...
0
votes
1
answer
230
views
What is the simplified form of this big o
$O(\sum_{l=0}^{log_2n} l*2^l)$. I took the integral of the term which I think is $O(n*log(n))$
- 17
0
votes
0
answers
10
views
O(n^3) Algorithm for Maximum Weighted Cycle Cover for Undirected Complete Graph with Triangle Inequality
I have been trying to implement an approximation algorithm for the max traveling salesman problem with triangle inequality, and each paper I've read references the step of finding the max cycle cover ...
0
votes
0
answers
14
views
better ways to integer interpolation?
I made some code about "integer interpolation" for running approximate alpha blending at FPGA which have low quantities of logic gate.
Let's refer to "II" as integer interpolation.
...
- 1
0
votes
0
answers
8
views
Morton-code based Linear BVH: Why do triangle's bounding boxes' centroids give higher-quality trees than triangles' centroids?
I've implemented linear BVH as described in Karras 2012, and I was using triangles' centroids for Morton Code generation. I found recent papers and implementations use triangles' bounding boxes' ...
0
votes
1
answer
28
views
What is the practical use of list.clear() method in Python?
I was wondering if there is a reason behind clearing all the values in a list and reusing it, as opposed to deleting the list and creating a new one. Are there any practical advantages of using ...
- 101
-2
votes
1
answer
82
views
If Q* can break encryption would that prove P=NP?
At 12:11 in this video the creator talks about unverified rumors the Q* algorithm can break AES-192 encryption. If this is true, would this mean P = NP?
- 99
0
votes
1
answer
18
views
Regarding CPU ILP: what actually consistitutes "the current instruction"?
If a CPU is able to execute multiple instructions in parallel, and fetching/decoding/scheduling instructions happen in batches, and there's multiple execution units, etc. What does the IP register ...
- 457
0
votes
0
answers
14
views
maximum step of sorting network
How to calculate the maximum step of sorting network?
Based on image below, it has most comparators at second index which is 9 comparators than another indices. That's mean, overall networks need 9 ...
0
votes
0
answers
12
views
Why is the block size chosen to be q-1 for Reed-Solomon codes?
Consider a Reed-Solomon code over a finite field of $\mathbb{F}_q$. Why is the typical block size chosen to be $q-1$ [1][2][3]? The reasoning I saw around this is ...
- 101
0
votes
0
answers
23
views
What's the intuition behind MIP* being bigger than MIP?
It is well-known that $\mathsf{MIP} = \mathsf{NEXPTIME}$, and recently there was a breakthrough stating that $\mathsf{MIP^*} = \mathsf{RE}$.
This was very confusing because it seemed like the (...
- 325
1
vote
1
answer
43
views
Complexity of satisfiability for relational logic on the booleans
I know that propositional satisfiability is NP-complete and that if I add first-order quantifiers I get the complete problems for the polynomial hierarchy and PSPACE. What happens if my formulas are ...
- 2,184
-3
votes
0
answers
40
views
shortest path question
suppose directed graph $G = (V,E)$
Let $C$ be a cycle with weight 0. The weight of the minimum cycle in the graph is also 0. Prove that for every pair of nodes $u,v$ $(u \neq v)$ in the cycle $C$:
$\...
- 1
0
votes
1
answer
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
1
answer
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 ...
- 185
1
vote
0
answers
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,417
1
vote
0
answers
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 ...
- 11
1
vote
2
answers
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 ...
- 11
0
votes
2
answers
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 ...
-2
votes
0
answers
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)...
-2
votes
0
answers
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....
- 19
0
votes
1
answer
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 ...
- 1
0
votes
1
answer
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$...
- 25
1
vote
0
answers
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 ...
- 33
0
votes
1
answer
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\}^*$ ...
- 3
1
vote
1
answer
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 ...
- 11
0
votes
1
answer
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 ...
- 25
2
votes
0
answers
12
views
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 $...
- 532