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
1
vote
1
answer
114
views
Choosing Fitness function for float output in Genetic algorithm
I have a NN that has ten outputs. The output values range between 0 and 1. The elements in the target array are all zeros except one element, which is "one".
I am searching for a Fitness Function ...
CommunityBot
- 1
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 ...
- 28.3k
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
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
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 ...
D.W.♦
- 156k
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 ...
D.W.♦
- 156k
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$ ...
D.W.♦
- 156k
64
votes
10
answers
34k
views
What is a safe programming language?
Safe programming languages (PL) are gaining popularity. What is the formal definition of safe PL? For example, C is not safe, but Java is safe. I suspect that the property “safe” should be applied to ...
- 135
0
votes
1
answer
497
views
Introductory books on Computer Networks
While I have come to learn some computer science, I find that I have next to no knowledge on computer networks.
Are there any good books at a basic level that cover some of the fundamental topics? ...
CommunityBot
- 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
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 ...
- 28.2k
-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
129
views
Stuck on Converting to Chomsky Normal Form,
I am supposed to be changing this to Chomsky Normal Form and then to Greibach form, but I am still having a few difficulties changing it to the first form.
Here is the language:
S → AA|SBBa|b
A → ...
CommunityBot
- 1
-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 &...
- 471
3
votes
4
answers
2k
views
Why isn't SAT in coNP?
I understand why NP=coNP if SAT is in coNP (How do I prove that SAT in coNP implies NP=coNP?).
But I'm missing why the following machine doesn't turing recognize the complementary of SAT:
Given a ...
-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
1
vote
1
answer
39
views
what are the necessary requirements for proving NP is closed under complement?
I've had the following question on a test and I answered: 'False', my answer was incorrect and I'm trying to understand why.
VC = {<G,k>| G = undirected graph with a vertex cover of size k}
IS = ...
CommunityBot
- 1
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
2
votes
2
answers
1k
views
Efficient algorithm to find minimum steps to cover all the given points in infinite 2D grid?
Problem statement: You are in an infinite 2D grid where you can move in any of the 8 directions :
...
CommunityBot
- 1
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
-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
0
votes
1
answer
1k
views
Determine if an NFA accepts infinite language in polynomial time
Question Statement: Given a NFA $N$, design an algorithm that runs in polynomial time such that it determines if $L(N)$ is infinite.
(Note that converting NFA to DFA is exponential time).
For any DFA,...
CommunityBot
- 1
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)
...
-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
3
answers
53
views
Transitioning from mathematics to computer science
I'm a mathematics undergraduate interested in theoretical computer science, machine learning, and neuroscience. I wish to pursue graduate studies in computer science but I fear I might not be able to ...
- 586
1
vote
1
answer
82
views
How are frames split up in an inverted page table?
For an inverted page table, it's number of entries = number of frames in main memory.
One frame in the main memory, could be shared by two (or more) processes, say process A and process B. Usually ...
CommunityBot
- 1
0
votes
3
answers
91
views
Can we further minimize this regular expression: a*(ac* + bc* + cc* + b*bc* + b*cc* ) + b*(bc* + cc*) + c*
I am trying to create the regular expression for the automaton named "full closure" in the following diagram using the arden's theorem:
Since, we have 3 accepting states, we would find 3 ...
CommunityBot
- 1
0
votes
1
answer
1k
views
Turing machine that recognizes the language $\{a^{n}b^{2n}c^{3n}|\ n\ge0\}$
I'm pretty sure that the Turing machine state diagram I drew accepts all strings in the language $\{a^{n}b^{2n}c^{3n}|\ n\ge0\}$, but how do you verify this? Likewise, how do you verify that this ...
-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
0
votes
2
answers
582
views
Turing machine for language $\{a^p | p~\text{is a prime number}\}$
I am trying to find a Turing Machine for the above language. I am trying to do it with one tape, to start with. However, I am not quite sure about how to keep track of the number of a's in the string. ...
- 11
1
vote
1
answer
45
views
GNI public coin interactive proof: why randomize y?
I've read this scribe that provides a public coin interactive proof for graph non-isomorphism.
In the proof, the verifier samples both a pairwise-independent hash function and a target $y$. Then it ...
CommunityBot
- 1
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
0
votes
1
answer
33
views
Struggling with Recurrence Relation using Telescoping Approach
I have the following recurrence relation that I am trying to solve using the telescoping approach:
$T(n) =
\begin{cases}
T(\frac{n}{4})+ n^2 & \text{for } n \geq 4
\\
1 & \text{otherwise}
\...
CommunityBot
- 1
1
vote
1
answer
43
views
Is it possible to measure how fast the humans are moving their bodies with different level(slow, normal, fast) from video?
Examples like
swinging both of their hands
squat
walking around
jump around
etc
Is it possible to perform this in real time under crowded scene without depth information?
I can find out the "...
CommunityBot
- 1
1
vote
2
answers
7k
views
DFA of (aa+bb)(a+b)* + (a+b)*(aa+bb)?
Our class teacher gave us a descriptive definition of a language in a Quiz today and ask us to make its DFA. In the middle of quiz he also told us the Regular Expression(RE) of that language but we ...
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
1
answer
91
views
Minimum number of skips needed for shortest path
In a directed, weighted graph with non-negative weights we are asked to find a path from a starting node s to node t that weights $\leq W$. In our given graph there is no such path but we have the ...
CommunityBot
- 1
0
votes
1
answer
66
views
Why does Java's HashSet have an underlying HashMap, not the other way around?
Why does Java's HashSet have an underlying HashMap, not the other way around? HashMap could ...
CommunityBot
- 1
1
vote
1
answer
61
views
Can we compute most significant digit of a binary number in O(1) on RAM model?
Consider we use a RAM model with word length w (or if you really want a more exact model, you can use Knuth's MMIX instructions).
Given a number n, we want to compute the most significant digit.
For ...
- 275k
0
votes
1
answer
124
views
Dynamic Time Warping and Similarity Measures
I have a multidimensional time series on which I would like to perform some clustering. I have been looking at DTW as a distance metric since my series are not always aligned in time. The problem I ...
CommunityBot
- 1
1
vote
1
answer
555
views
CFG for the language {w ∈ {0, 1}∗ : w is a palindrome and |w| is divisible by 3}
The question is the following:
Construct CFG for the L = {w ∈ {0, 1}∗ : w is a palindrome and |w| is divisible by 3}.
I am able to construct CFG for the set of all palindromes as below:
S --> aSa | ...
CommunityBot
- 1
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))$
- 586
1
vote
1
answer
62
views
Is there a good way to hash abstract binding trees?
The hash function should be invariant under alpha-renaming. Using de Bruijn notation seems to be possible, but it requires alpha-converting the whole tree when a binding is created, and has the ...
CommunityBot
- 1
2
votes
1
answer
207
views
Sub-exponential time algorithm to compute playoff chances
There are 10 teams, Team A through Team J, playing in a triple round robin pool (each team plays thrice against each other team, for a total of a 27 games per team). After the round robin pool, the ...
CommunityBot
- 1
0
votes
2
answers
82
views
What is a good method for modelling combinatorial tree (sport competition results)?
Probably newbie question here, please point me out to relevant theories/tutorials if needed :
let say I want to evaluate the probabilities of the final rankings for a sport competition
the ...
CommunityBot
- 1
2
votes
1
answer
35
views
Time complexity of an uneven binary search
I have a concept binary search which doesn't split at the midpoint of a list, but at a ratio of 1:2.
If we abstract the search function time complexity into $T(n)$ then the function can recurse into ...
CommunityBot
- 1