All Questions

0
votes
0answers
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 ...
1
vote
2answers
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 ...
-1
votes
0answers
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.
2
votes
0answers
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')$ ...
1
vote
0answers
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 ...
1
vote
1answer
32 views

How does quicksort with 3-way partitioning ~ $(2 ln 2) NH$ become linear time complexity with many duplicated keys?

From Algorithms 4th: Quicksort with 3-way partitioning uses ~$(2\ln 2)NH$ compares to sort $N$ items, where $H$ is the Shannon entropy, defined from the frequencies of key values. $ H = -(p_{1}\...
3
votes
1answer
32 views

Solving recurrence relations with two variables

I am trying to solve this recurrence relation with two variables: $$T(n, k) = T(n - 1, k - 1) + T(n - 1, k)$$ The base cases are: $T(n, k) = 1$ if $k = 0$ $T(n, k) = 0$ if $k > n$ I was ...
1
vote
0answers
59 views

What algorithm is appropriate for a thermostat controlling the heating of a room with floor heating?

I built my own thermostat that controls the boiler heater for the radiant floor heating in my house and I would like to develop / implement a smarter temperature control algorithm. What I am ...
-2
votes
0answers
27 views

Operations research [closed]

Hello friends? A student asked me on question 1 above.Can the question be solved really? Because i find it confusing therefore,unable to reason it out. someone please help solve it out using any ...
0
votes
1answer
22 views

Is the set of surjective recursive functions in RE/coRE?

Let L be a set of recursive funtions with $L = \{i\in \mathbb{N}|f_i\space is\space surjective\}$ where $i$ is a gödel number of f.Is $L\in RE,\space coRE$? I can't think of a way to show either of ...
0
votes
1answer
35 views

Quick and space-efficient way to find whether two sets intersect

I hope you can help me - Given a lot of sets containing integers, I'd like for any two sets, to quickly (i.e. O(1)) ask whether they intersect. Note that I don'...
0
votes
0answers
37 views

Shortest Uncommon Subsequence

Here is another GeeksforGeeks problem that asks how to find the shortest Uncommon Subsequence of 2 strings? For example, Input : S = “babab” T = “babba” Output : 3The subsequence “aab” of ...
-1
votes
0answers
42 views

Reduction from “restricted-3-partition” to “k-graph-partition”

I need a reduction from “Restricted-3-partition” to “k-graph-partition” that can be done in polynomial time, but I have absolutely no clue how to start this off. Can anyone help me out with an ...
2
votes
3answers
47 views

Solve recurrence T(n)=2T(n-1)+n for n greater than 1 and T(1)=1

Problem statement: Solve $T(n)$ for $T(n)=2T(n-1)+n$, $n > 1$, and $T(1)=1$. My attempt: I tried back substituting but I am unable to find a general pattern: $$\begin{align*} T(n) &=2^2 T(n-2)...
32
votes
6answers
6k views

Do lossless compression algorithms reduce entropy?

According to Wikipedia: Shannon's entropy measures the information contained in a message as opposed to the portion of the message that is determined (or predictable). Examples of the latter ...
0
votes
0answers
3 views

what can cause the best-bound to get tighter in the first MIP node?

I'm using gurobi MIP optimization engine for solving a mixed integer linear minimization problem. I see that the engine didn't start the branch and bound stage ...
-1
votes
1answer
37 views
-1
votes
2answers
30 views

How to construct Context Free Grammar of words with equal number of 0's and 1's [duplicate]

i am trying to find a cfg for this cfl L = $\{ w \mid w \text{ has an equal number of 0's and 1's} \}$ is there a way to count the number of 0's or 1's in the string?
2
votes
2answers
34 views

Cover the maximum of elements

I have a collection of subsets $\{S_1,\ldots,S_m\}$ where each $S_i\subset \{1,\ldots,n\}$. I would like to cover the maximum number of elements from $\{1,\ldots,n\}$ by choosing a single element from ...
1
vote
1answer
23 views

what does this phrase mean: “train a policy network”

I am familiar with the basics (and perhaps a substantial amount of basics) of imitation learning and reinforcement learning. In IL (imitation), we take demonstrations from an assumed expert, which we ...
1
vote
1answer
38 views

Data hazard after in load word after addi

5 stage pipline addi $t1,$zero,0x30 lw $t2,0($t1) sw $t2,0xff18($zero) addi $t2,$zero,100 Question is to find hazards existing in the code and the answer is:...
0
votes
0answers
6 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 ...
1
vote
2answers
15 views

Increased rounding relative error when subtracting

I'm reading the book "Lessons in Scientific Computing" by Schoerghofer and it says: If x and y are real numbers of the same sign, their sum x + y has an absolute error that adds the two ...
1
vote
2answers
87 views

Are the capabilities of programming languages the same?

Is the capability of every programming language the same since it is eventually translated into machine code. Python, Java etc. are all together instructions the CPU is going to process. So, you could ...
6
votes
0answers
76 views
+50

Solving an LP with at most m-1 nonzeros

Consider the linear program: $$ A x = b, ~~~~~~ x\geq 0 $$ where $A$ is an $m$-by-$n$ matrix, $x$ is an $n$-by-1 vector, $b$ is an $m$-by-1 vector, and $m<n$. It is known that, if this ...
0
votes
1answer
16 views

Curiosity on system device nomenclature - Gaussian Mixture Models

Would not know if this is the best SE website to ask, but I could not find anything better, especially because the answer might involve a fair amount of computer science (although this is an ...
0
votes
0answers
21 views

How strong is a FSM with long enough(but not infinite) tape?

Like turing machine, but your tape is finite. To make a program valid it should have a limit result when the length of tape tends to infinity. Whether the tape has two ends or is cyclic doesn't ...
1
vote
0answers
36 views

Is MCTS an appropriate method for this problem size (large action/state space)?

I'm doing a research on a finite horizon decision problem with $t=1,\dots,40$ periods. In every time step $t$, the (only) agent has to chose an action $a(t) \in A(t)$, while the agent is in state $s(t)...
3
votes
1answer
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 ...
5
votes
2answers
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 ...
-2
votes
0answers
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 ...
1
vote
0answers
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 ...
3
votes
1answer
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: ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
-1
votes
0answers
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? ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
1
vote
2answers
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 ...
0
votes
2answers
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?
0
votes
0answers
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
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
2answers
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 ...
1
vote
1answer
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)$ ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 :)
0
votes
0answers
16 views

Number of MUX required for Cache Mapping

I have read that the number of multiplexers required is equal to the number of bits in the TAG field. Is it true? If yes then why? I know that the size of each multiplexer has to be S to 1, where S ...
2
votes
2answers
374 views

Can a Formal Language be of a type (RE, REC, Regular, etc) for one TM, but of a different type for another?

I'm new to the study of formal languages, and I wondered if languages of a certain type are objectively of that type (RE, REC, regular, etc), or if their type varies on their context? I had this ...

15 30 50 per page