# All Questions

45,945 questions
Filter by
Sorted by
Tagged with
1 vote
44 views

### What is the formal definition of a combinational logic?

Question Background A finite-state machine can be defined as a 5-tuple as follows (Sipser, pg. 35): The image below (taken from the Wikipedia article on combinational logic) seems to suggest that ...
• 111
49 views

### given an integer array of length n, find tuples $(a,b,c,d)$ such that $d=\sqrt{a^2+b^2+c^2}$

any reference on what kind of problem it is and what algorithm can solve this in $n^2\log n$? for 5 as d, the numbers 4 and 3 and 0 would work. so i think there should be zero in the array. maybe use ...
516 views

### Is this variant of Exact Path Length Problem easy or NP Complete

I was reading about the longest path problem and it is NP Complete. What about the problem where we need to find a path of some exact length $K$. All edges are directed. We are also allowed to repeat ...
• 45
27 views

### Why $L$ = { $uc^nu$ | $u$ ∈ $P$, $n > 0$ } isn't context-free?

$P$ is the set of all words of even length on {0,1}. Hi, i tried using pumping lemma to see why $L$ isn't a context-free language, but there's a decomposition where none of all three properties is ...
27 views

### Red-Black Tree - Top-down deletion

I learned the red-black tree top-down deletion from RB-tree tree: top-down deletion start from page 56 However, I'm quite confused about below page. Why do the root need to change to red. I thought ...
1 vote
101 views

47 views

### How to define soundness and completeness of a transformation algorithm?

My algorithm takes a Java program as an input, modifies it to eliminate static attributes, and returns a new modified Java program without such attributes. What would be the soundness and completeness ...
• 107
61 views

### Are there any implementations of algorithms on hardware that are (nearly) optimal?

Consider the notion of optimal implementation as follows. Suppose we have some algorithm $A$ whose execution for some problem of size $N$ requires $T(N)$ operations (e.g. arithmetic operations). A ...
• 103
54 views

### How might we hash two trees?

Suppose that you had two trees. Our goal is to convert the two trees into two integers such that two trees are the same if and only if the two integers are the same. Suppose that we have a function ...
43 views

### Largest heap-ordered minor of tree

Question: Let $T$ be a rooted tree whose vertices are labeled with integers. To contract the edge from any node $v$ to its parent $p$, we make $p$ the new parent of all children of $v$ and then ...
• 529
29 views

### relational algebra - sql. Union and intersect question

Question about relational algebra. Is (A⋂B)⋃(C⋂B) ? = (A⋃C)⋂B ? Sorry for the rudimentary question been a while since my relational algebra course
21 views

### How reduce image noise and get only specific object?

I working in road lines detection, this my code : ...
1 vote
22 views

### $|v|$ and $|x|$ factorizations (in Pumping lemma for context-free) have the same length?

When i iterate $v$ and $x$ factorizations to see if a word is still in a language $L$, do i have to assume that $|v| = |x|$ always or could happen theirs lengths are different?. I'm asking because i ...
20 views

### Are all languages determined in exponential time NP languages?

According to the theorem, if $L \in NP$, then $L$ can be determined by a deterministic Turing machine in exponential time. So, are all languages determined in exponential time NP languages?
• 163
1 vote
42 views

### Find MST with bounded edge weight in O(|V|+|E|)

I need to describe (even in words) an algorithm that gets a connected, undirected, weighted graph so that the weight of each edge is either 1,2 or 3; and returns MST of that graph is time complexity O(...
• 25
573 views

### Correctness of FIPS 186-4 square test algorithm

Federal Information Processing Standard 186-4 appendix C.4 gives (without reference) an algorithm intended to test if a positive integer $C$ (which can be thousands bits) is a square: Set $n$, such ...
• 449
78 views

### Has this problem related to bin-packing and knapsack been studied?

There is a problem I recently encountered in my work which is related to the knapsack and bin packing problems. But I couldn't find the exact problem anywhere. Say you have some suitcases. Each of ...
• 295
44 views

• 161
15 views

### Complexity of the tau-leap algorithm

I need help estimating the complexity of the tau-leap algorithm: Equation (7) can be calculated in a constant time. My estimation the complexity of the algorithm would be O(n), where n is a number of ...
15 views

### Is this language PSPACE complete

Prove $PSPACE$-completeness of the language $READALLEXACT$ = $\{$$(M, x, 1^ s , t)$ | $A$ deterministic Turing machine $M$ on input $x$ reads all bits of the input in exactly $t$ steps and using no ...
35 views

• 113