# 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 ...
1 vote
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$ ...
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 ...
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? ...
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 ...
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 ...
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|...
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 → ...
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 &...
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 ...
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 ...
1 vote
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 = ...
5 views

1 vote
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 "...
1 vote
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
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 ...
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 ...
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 ...
1 vote
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 ...
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 ...
1 vote
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 | ...
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))$
1 vote
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 ...
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 ...
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 ...
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 ...