All Questions
45,945
questions
1
vote
0
answers
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
-2
votes
1
answer
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 ...
3
votes
2
answers
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
0
votes
1
answer
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 ...
0
votes
0
answers
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 ...
- 11
1
vote
2
answers
101
views
Sampling from bins with ratio preservation
I have sequence of integers $a_1, a_2, .., a_n$,
let $S_a = \sum_{i=1}^{N}{a_i}$,
for any $k \in (0; 1)$ I need an algorthim to that maps every $a_i$ into another integer $b_i$ with 2 requirements:
$...
- 287
0
votes
0
answers
12
views
Difference between Distributed File System, Cluster File System and Parallel File System
On the internet, I am unable to find concrete definitions of these three types of file-systems. Can someone clearly explain the difference between these?
0
votes
1
answer
44
views
A variation of the maximum bipartite matching problem
Given a bipartite simple graph $G=(V,E)$, where $V=A\cup B$ and $A\cap B=\emptyset$, any edge in $E$ connects two vertices in $A$ and $B$, respectively. The maximum bipartite matching problem is to ...
- 15
2
votes
1
answer
84
views
Floating-point modular multiplication algorithm
Is there a well-known algorithm for modular multiplication of floating-point numbers?
I would like to multiply some large angle in single precision (6-7 significant digits) and wrap it back to 360 ...
- 21
4
votes
1
answer
58
views
Self referential hash function possible?
Is there a hashing function $f$ that for each input $x$ if $f(x) = y$, then $f(x \, || \, y) = y$? In other words, if we concatenate its output with the input, the result will not change.
Furthermore, ...
- 93
-1
votes
2
answers
31
views
If we find that, e.g., T(n)<=d*n*lg(n) for some d that depends on n, is T(n)=o(nlgn)?
In the substitution method, if we find that, for instance, T(n) < dnlg(n) but only for some d that depends on n, then can we say that T(n) = o(nlg(n)) (little-oh) in some cases? For example, in ...
8
votes
5
answers
2k
views
In algorithms for matrix multiplication (eg Strassen), why do we say n is equal to the number of rows and not the number of elements in both matrices?
In Strassen's algorithm, we calculate the time complexity based on n being the number of rows of the square matrix. Why don't we take n to be the total number of entries in the matrices (so if we were ...
-1
votes
0
answers
48
views
Finding unique (in edges) paths in flow netwrok
A graph $G=(V,E)$ is used to represent a road netwrok with $k$ drivers on the network. Each driver ($i$ where $1\leq i \leq k$) starts at a given starting vertex $s_i$ and needs to get to target ...
- 321
1
vote
0
answers
27
views
Data hazard in MIPS: SW after ADD
Use the five-stage pipeline with forwarding unit.
add $t1, $t2, $t3
sw $t1, 0($t4)
In the above code, is the data hazard of t1 fixed by forwarding the correct t1 ...
- 11
-3
votes
1
answer
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
0
votes
1
answer
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
0
votes
2
answers
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 ...
- 151
0
votes
0
answers
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
-4
votes
0
answers
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
- 1
-1
votes
0
answers
21
views
How reduce image noise and get only specific object?
I working in road lines detection,
this my code :
...
- 1
1
vote
1
answer
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 ...
0
votes
0
answers
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
1
answer
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
7
votes
1
answer
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
0
votes
0
answers
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
0
votes
2
answers
44
views
Finding a 2SAT instance that has a specific solution set
Is there a 2SAT instance of variables $(a,b,c,d,e,f,g)$ that has exactly the solution set $S=\{ (1,0,0,0,0,0,0),(0,1,0,0,0,0,0),(0,0,1,0,0,0,0),(1,1,0,1,0,0,0),(1,0,1,0,1,0,0),(0,1,1,0,0,1,0),(1,1,1,1,...
1
vote
1
answer
21
views
Reduction from $2$-Partitioning to (simple) pairwise $2$-Partitioning
I'm currently stuck showing $NP$-hardness of a problem of mine.
An instance of my problem (I call it (simple) pairwise $2$-Partitioning) is given by the following:
Given a set of tupels $B=\{(b_1,1),\...
- 161
-1
votes
0
answers
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 ...
- 1
0
votes
0
answers
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 ...
- 1
0
votes
1
answer
35
views
Prove that $coNP \neq NTIME(n^2)$
I need to prove that
$coNP \neq NTIME(n^2)$ using time hierarchy theorem.
as we know $DTIME(n^4)\subseteq P\subseteq coNP$
from time hierarchy theorem we can derive that $DTIME(n^4) \not \subseteq ...
- 1
1
vote
1
answer
121
views
Finding existence(or non existence) of spanning tree with a specific degree on a specific vertex
Given an undirected graph $G=(V,E)$, and vertex $v\in V$ and a number $k\in \mathbb{N}$, find an algorithm to find whether there exists a spanning tree of $G$ in which $v$ satisfies $d(v)=k$
I've ...
- 321
1
vote
1
answer
43
views
Why Prim algorithm may fail to return minimum spanning forest on disconnected undirected graph
I am trying to address the following claim- "running prim algorithm on a disconnected undirected graph returns minimum spanning forest".
I thing that the claim may be false (i.e there might ...
- 25
0
votes
1
answer
31
views
Collisions in hash table - Is this table wrong?
I have the following hash table with hashcodes being quadratic numbers.
Why do 0, 16, and 64 have different number of collisions when they map to the same number (line %16). Also how is it possible ...
- 121
0
votes
0
answers
28
views
Is there always a Dynamic Programming Solution underlying a greedy solution to any algorithmic problem?
According to CLRS book, Introduction to Algorithms,
Nevertheless, beneath every greedy algorithm, there is almost always a
more cumbersome dynamic-programming solution
As the word "almost" ...
0
votes
1
answer
32
views
Convert regex for comma separated value to CFG grammar
I have the following regex that I'm trying to convert to a CFG: e|a(,a)* (e representing the empty state). Basically I want to ...
1
vote
1
answer
49
views
What data structure/s can I use for fastest lookup of a permutation between two arrays of pairs (preserving order)?
I'm trying to figure out a more efficient solution to the following problem.
Dataset: A set of arrays of key-value pairs (K, V). The arrays have varying lengths, ...
- 111
2
votes
1
answer
19
views
Duplicate rules in CFG
Suppose I have the following CFG that I would like to bring to CNF
S -> TA | bA | Ab | b
A -> Aa|a
T -> Ab
Then I have two options to get rid of the ...
- 155
0
votes
2
answers
62
views
Do i really need to study monstrously long intel manual?
I want to be an OS developer. I can say I am a bit comfortable after i read few tutorial on x86 assembly.
But I see a lot detailed in intel manual, does an OS developer really need to study whole ...
- 1
1
vote
2
answers
52
views
Why does Michael Sipser state that $0^p0^p$ is a bad choice for proving $L=\{ww|w \in \{0,1\}^*\}$ is non-regular a bad choice?
I feel that choice should work great for proving non - regularity of the mentioned language.
If $L=\{ww|w \in \{0,1\}^*\}$ and we choose $s=0^p0^p$, meaning s is atleast as long as 'p'. Then we can ...
- 305
0
votes
0
answers
70
views
Traveling salesman problem with dynamic edge costs
General description
I have an optimization problem in which I need to schedule events and each of the events needs to be scheduled exactly once. The "cost" of scheduling one event depends on ...
- 101
-1
votes
1
answer
33
views
A sufficient condition for unsatisfiability
Let $\varphi = \bigwedge C_k$, in which $C_k$ is a clause in X3SAT (exactly-one 3SAT or one-in-three 3SAT). That is, $C_k = (l_i \odot l_j \odot l_u)$ such that $l_i \in \{x_i, \overline{x}_i\}$ for ...
0
votes
2
answers
101
views
Can you help me in finding an algorithm that finds the first unique number in an array with lowest position?
I have the following problem to solve:
Given a non-empty array A consisting of N integers, the task is to find the first unique number in the array. A unique number is defined as a number that occurs ...
1
vote
1
answer
25
views
Proof that STCON is in NL
What is the proof that STCON
(returns 1 if there is a path in the directed graph $G = (V,E)$ from $ s \in V$ to $t \in V$ and else, 0.
is indeed in NL? (Non-deterministic turing machines with ...
0
votes
0
answers
32
views
Minimum even goldbach partitioning
The following is an excerpt taken from Oliveria's paper "Empirical verification of the even goldbach conjecture...", it gives an alternative segmentable minimal interval partitioner for the ...
0
votes
0
answers
20
views
How do you devise a cellular automaton?
I learned recently about the von Neumann cellular automaton and how he created it with 29 states. How does one figure this out in advance? How do you come up with a novel mechanism for a cellular ...
- 1,951
2
votes
1
answer
42
views
Determining the minimum number of edges to add to a graph to obtain a clique of size $k$
As part of a hobby project I stubmled into the following question which has me stumped:
Given an undirected graph $G = (V, E)$ and an integer $k$, what is that smallest number of edges that need to be ...
-1
votes
0
answers
17
views
A determines B is used in database for functional dependency. What is the limit of use of this notation & how it is different from notation in maths
We use to show the relation in maths as example y=x, which is a perfact notion to know the behaviour of the relation where as we use in database as x determine y, which does not show how x and y are ...
1
vote
0
answers
44
views
What is the time complexity of removing among $N$ sets of size at most $n$ the sets which are subsets of another set?
A naïve solution would be to first sort all sets, taking time $O(N n \log n)$. Then, for every possible pair of sets, check if one is a subset of the other, and if applicable remove the subset. This ...
- 621
0
votes
0
answers
19
views
The proof of $V^*$ being well-defined in the proof of Hamiltonian cycle problem being NP-complete
In CLRS, at the end of the proof of the Hamiltonian cycle being NP-complete, when it wants to show that $V^*$ is well defined, I don't understand the end of the proof when it says:
To see that not ...
- 113
0
votes
2
answers
47
views
Does the computer change the content of the virtual adress
My book(digital design and computer architecture ARM edition) explains loads and stores like this:
To perform a load or store, the processor must first translate the
virtual adress to a physical ...
- 113