All Questions

I know that the Set-cover problem with $n$ elements and a universe of size $N$ is NP complete. Also, the problem is Fixed-parameter tractable regarding the number of sets $k$ that should cover the ...

You have a 2d field of size X, every point on that field can be treated as a pixel so it has a color, at the start all pixels are white. You then select a point on the field with a different color ...

Is $\frac{n}{\text{log}n}$ $=\text{o}(n)$ ?

When executing this program on c++14 (clang4.0) I get the expected result but other versions I get the wrong result why so? ...

I need to define an algorithm for how fuel efficiently a driver is driving, but I'm a total novice in the area of computational models so I'm not sure if I'm doing this right. I have formulated the ...

I know of 2 Minute Papers and Papers We Love, but is there anything similar in audio format? PS: Is there a better place to ask this question?

I have two lists say A and B, each consisting of n positive integers. I make a list C such that each element of C i.e., Ci=Ai*Bi for each element Ai in A and Bi in B. Now I have to update the value of ...

I have to develop a simple e-commerce application , with Only 3 classes User , Shopping cart and Product. I am not quite sure about the relationship between these classes the requirement says ...

I was reading through a research paper on compressive particle filtering for target tracking, and I came across the following: Let $z \in d_{z}$ denote a vectorized image with $d_{z}$ pixels. Assume ...

Initially we have an array of size N, all set to 0. We have operations of two kinds: $Increment$ the range $[L, R]$ by 1. $Get$ the current value at $idx$. If these queries were interspersed with ...

During my preparation for an exam, I've come across an exercise that was focused on precision calculation with floating point numbers. It goes like this: Consider the expression : $$\frac{1}{1-x}-\...

I asked a question here about discrete event dynamic systems. They are systems whose state evolution depends on asynchronous events. It can be combined with flow to produce a hybrid system. There ...

I am using a network simulator called ns and I got this network and its corresponding graph: and I am supposed to calculate the throughput during the simulated time interval, I was told that sequence ...

I have seen two different Peterson’s Solution to mutual exclusion, one is from Modern Operating Systems: ...

Huffman coding is already doing a great job at compressing ascii bytes for data with a distribution like the following ...

PDA that accepts by final state, the language in the alphabet {a,b} where the number of groups 'aa' equals the number of groups 'bb'. To accept: aababababb aaababbb bbbaaaabbb Rejected aaabbabb ...

I'm writing a design document for a macro expansion language that is specifically intended for arithmetic operations on integers. I've already determined that not wrapping macros with parens can lead ...

Question- Prove: Every decidable set is Turing reducible to the empty set. Can anyone help me with this please? All reductions tutorials I've seen use practical examples of reduction such as sipser'...

Are there any (for example in literature) rules for converting right linear grammar to left? I found the algorithm from right to left, but not the opposite. Thanks for help

I am trying to solve the following Recurrence relation using substitution method and I am stuck almost half way. I know the answer is 2^n but I can't reach it. At first, my question is: Who decicdes ...

Question: Prove the following: Every set is Turing reducible to itself. If anyone can provide a solution that would be great, I've just been introduced to computation theory so be as descriptive as ...

I have an array ($|A|\leq 10^6$) of numbers ($A_i\leq10^6$) and a set of prime numbers. I have to find the count of the elements in the array that are divisible by at least one of the numbers in the ...

How to convert a binary variable and a function to it into matrix in R? x ~ a binary variable, where Prob(x=1) = 0.2 (20% are 1s) w ~ U[0,1] + d*x, where d = 3 (uniformly distributed between 0 and 1 ...

Let $G=(V,E)$ be directed graph, where the weights of the edges are non-negative. The graph might have cycles, but without parallel edges. Consider a $T \subset V$, and $u \notin V$. I'm trying to ...

I have a variable Int a to set variable String b. ...

I've been looking at questions about the regular concatenation of two languages; one question said that the concatenation of $\{0^n1^n|n\geq 0\}$ and $\Sigma^*$ was regular (over the alphabet $\Sigma =...

The grammar is $S \rightarrow AA|a$$A \rightarrow SA|ab$The actual question is to find an NPDA accepting the language generated by this grammar but for that i firstly need to convert it into Greibach ...

Is the complement of every semi-decidable language a semi-decidable language?

I have asked a similar question at stack-overflow, but then I found this question here, and figured it should go here instead.. So, my question is pretty much the same as the one in the question I ...

Given an AVL tree,what are the possible inputs so that the same given tree is formed(please dont mention brute force technique)?

Why is the $A_{ETM}$ for a variant of a Turing machine (an erasing Turing machine), where changing a tape symbol to a nonblank symbol is prohibited, decidable? Why does the following diagonalization ...

So, I was tasked with creating an app that generates the schedule of a doubles tennis tournament (i.e., teams of two) in a way that, by the end of it, everyone would have played against the rest of ...

I want to prove the NP-hardness of my problem P in scheduling. I was trying with Partition, 3-Partition and Subset product, But neither was successful. Now, I can reduce a problem, say PRODUCT-2-...

I am solving this problem from here. The given relation is $$T(n) = 2 T(\frac{n}{2}) + n^2, \, T(1) = 1$$ The solution via recurrence tree method is given as: The zeroth level has a single node ...

Given an array $A$, sum the number of unique elements for each sub-array of $A$. If $A = \{1, 2, 1, 3\}$ the desired sum is $18$. Subarrays: ...

First, we state here a theorem that is well-known in computability theory: $L=\{xx\mid x\in\Sigma^*\}\notin CFL$ for every fixed $|\Sigma|\geq2$ And, the standard proof is using pumping lemma. At ...

Consider this language: $$L = \{w \in \{a,c\}^* \mid 3\nmid\#a(w)\land\#c(w)>0\}$$. Here is an automaton for the first part of language, but I do not know how to devise and attach the second part ...

Along the lines of detect differences between tree structures, I'm wondering if there are any general techniques or tools (e.g. the techniques behind the tools) that can essentially do what Git does ...

Persistent (aka immutable) data structures in functional programming sidestep issues of shared memory mutual exclusion, and thus also issues such as data races that arise and which may be difficult to ...

In lamport's paper1, he define global local timestamp, which is composed of process id and local lamport timestamp. This timestamp is used to order all the events in a distributed system. The rule ...

Given a permutation of $n$ element and for each pair of position $i$ and $j$, a non-negative integer $c_{ij}$ which is cost of swapping $i$-th element and $j$-th element of permutation. Is there any ...

In lamport's paper[1], he define two concept The partial ordering and The totally ordering. What does partial mean in ...

Write a C program which has a function COM that take two strings (character array) A,B and output "A is smaller" or "B is smaller" if string A is smaller than string B. We say A is smaller than B if ...

I mean, in which language/s it was programmed in the beginning, and which program components it contained, and how it changed over the years from a technical point of view and the reason for these ...

How do you solve T(n)=T(n/2)+n*log(n) ?

I have a swarm ofN robots to place on a plane area. Each robot would control a sub part of the area (navigating in it). What algorithm could I use to deploy my ...

so I have a bit longer question. So I have bought a new computer a week ago and it runs super smoothly when it turns on and in general I am happy with it. After 2-3 days i had a required update where ...

Let H be a universal family of hash functions from U = {0, 1, . . . , u − 1} into a table of size m. Let S ⊆ U be a set of m elements we wish to hash. Prove that with probability at least 3/4, no list ...

I have been attempting to solve this problem for hours, but cannot seem to comprehend how to come to the solution. Let $H$ be a universal family of hash functions from $U = \{0,1,\ldots, u − 1\}$ ...

I have the following two functions $f(n) = n\sqrt n + n \log n$ $\log_{100} n$ And I need to classify them into the followings: $O(n)$, and/or $O(n^2)$, and/or $O(n^3)$, and/or $O(n^{1.5})$, and/or ...