# All Questions

28,863 questions
15 views

### Johnson-Lindenstrauss and k-means

I have a question about Johnson-Lindenstrauss and k-means. I m study a resource that explain a link between Johnson-Lindenstrauss and k-means. From what I understand, Johnson-Lindenstrauss helps us ...
63 views

### “Mathematical Physics”'s equivalent for Computer Science

Mathematical Physics is a well defined scientific fields that deals with the application of mathematics , mathematical tools , and mathematical methods in the theories and the problems of physics. Is ...
12 views

### How do we obtain a dfa to accept strings of a’s and b’s such that l = {w| w ∈ (a + b)* } such that na(w) mod 3 = 0 and nb(w) mod 2 = 0?

It's an assignment question but I do not completely understand how to do it. I have basic knowledge in the subject, I just need some help as soon as possible.
17 views

### Complementary of graph invariant

Graph invariant is a property that holds for two isomorphic graphs. For example, degree sequence is graph invariant. We can write $d(G) \ne d(G') \Rightarrow G \ncong G'$, although $d(G) = d(G')$ ...
27 views

### How much of the x86 instruction set does blender use? [closed]

I'm trying to better understand benchmarks that are commonly used for computer hardware. I've been unable to find an answer to this question. Extra credit if you can provide a breakdown in ...
32 views

102 views

### Optimal dividing of K people into N groups

A teacher at a school has to do this on a regular basis. Let's say 12 students should be divided into either 4 groups of 3, or ...
114 views

### Why researchers don't study the parameterizations of the problems unlikely to be NP-Hard?

I have seen the parameterization of the very well known problems like vertex cover, hitting set etc which are NP-hard (NP-complete precisely). Many researchers in the past have been studied the ...
33 views

### What is the probability of two integers having identical values? [on hold]

There are two sets of 32 bit unsigned integer. Each set has 4000 numbers. Two sets could either be identical or they can different values. All 4000 numbers from each set are added and then the ...
18 views

### Why is the objective in a multi-armed bandit problems to minimize (cumulative) regret?

In a multi-armed bandit, the objective is to maximize the expected cumulative reward. This objective is usually (equivalently?) stated in terms of expected cumulative regret. Question: Why not just ...
151 views

### Drawbacks of adding type equality to 1ML

In the 1ML – Core and Modules United (F-ing First-Class Modules) paper, the author gives the following example for why module types do not form a lattice under subtyping: ...
14 views

### Associative cache finding the tag and word number

An associative cache has a block size of 16 words. The capacity of the cache is 32 Kbytes and main memory can store 4 Mbytes. The word (the addressable unit) size is 2 bytes. I'm unsure how to find ...
21 views

### Kiln optimization problem

Say I have a kiln for making castings. There are 3 shapes. I need to produce the following castings: 102 of A 364 of B 70 of C I can put 50 molds in the kiln at a time. I can have 75 molds made in ...
21 views

### How to create a jump code for the following boolean expression?

I want to create a jump code statement for the following boolean expression how can I do that? Can someone give me an example which helps me to solve further problems related to the same? ...
13 views

### Testing for a symmetric property $P$

We'll say $P$ is a symmetric property if $\forall x\in \{0,1\}^n:x\in P\iff \forall \pi \in S(n): f_{\pi }(x)\in P$ where $\forall i\in [n]:f_\pi (x)_i=x_{\pi(i)}$. Given a symmetric property $P$ we ...
15 views

### How to accomodate decision trees with infinite options

I know that once I have a graph or decision tree representation of a problem, there are many different ways I can get a computer to solve the problem. They're called search algorithms, and go by names ...
53 views

### Buchi automata in formal software verification

As I am studying the application of Buchi automata in formal software verification, I am interested in the computational complexity (or links to papers) for the algorithms used to solve the problem in ...
28 views

### Does NTIME($n^\alpha$) $\subset$ EXPTIME imply NP $\subset$ EXPTIME?

I think I'm able to prove NTIME($n^\alpha$) $\subset$ EXPTIME for arbitrary $\alpha$. Is this a new result? If it was, would there be a way to deduce NP $\subset$ EXPTIME from it?
31 views

### Is there a relation between A+B and log(A)+log(B)? (exact/approximate relation) [on hold]

If I have the value of log(A)+log(B), is there a way to get the value of A+B ? where A and B are floating point numbers
17 views

### Finding if a given problem is a Np-Hard problem - recruitment problem

I have to prove that the following Recruiting problem a NPC-problem. Input: n candidates and m positions and a matrix A $\in {Q^{n\times n}}$. Each entry $A_{ij}$ with i < j tells how much gets ...
15 views

### Is the statement “Control unit controls overall operations of computer.” true or false

I was tutoring a grade 4 student about CPU and I got confused as there are also the other units of a cpu like arithmetic and logic unit and memory unit. So, is the above statement actually true even ...
49 views

### Is every subset of a RE language also RE, in general?

I'm trying to understand the question in my title in an intuitive way: If I have an RE language A, then some TM, say TM(A) accepts on it. If I take a subset of A, say A2, then all elements of A2 will ...
30 views

### Proof of a lower bound of the recurrence relation (the CLRS's 4.6-2 exercise)

I am trying to find a solution to the ex. 4.6-2 of the Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein (the third edition). It requires, for recurrence relations $T(n)=aT(n/b)+f(n)$ ...
17 views

### Formal definition of an empty stack accepting PDA

PDA's are usually defined using the 7-tuple convention. $M=(Q, \Sigma, \Gamma, \delta, q_{0}, Z, F)$ F is the set of accepting states. I want to design a PDA accepting by empty stack, so using ...
30 views

### Max Weight Path in a Graph

I know that this problem is a known NP-Complete problem, but I'm curious as to why a particular algorithm won't work. Given a graph $G = (V,E)$, and edge weights $w(e)$, why can we not create a new ...
27 views

### Get grammar from his LALR(1) parsing table

I have a problem with this exercise. This is the LALR(1) parsing table for the grammar G. How can i get the productions of G? Thanks :)