All Questions

Filter by
Sorted by
Tagged with
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 ...
-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 ...
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 ...
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: $...
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 ...
-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 ...
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 ...
-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 ...
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 ...
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 ...
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 ...

15 30 50 per page