All Questions
47,718
questions
0
votes
0
answers
17
views
The second shortest path on a directed graph
The question asks to write an algorithm using Dijkstra's algorithm with time complexity of
$\Theta(|E| \log |V|)$ that find the second shortest path between s∈V and t∈V.
The farthest I managed to get ...
- 1
0
votes
0
answers
14
views
Backpack assigment
Can you help me solve this problem. Names of items NAME, sizes SIZE and values VALUE are given. Using dynamic programming, find the optimal filling of backpacks of size M. NAME = {A, B, C, D, E}, SIZE ...
- 1
0
votes
1
answer
15
views
Determine if all the continuous subsequences of an array contain at least one unique element in O(n lgn)
Given an array of length n, how to determine if all the continuous subsequence of this array contains at least one unique element.
Any subarray array[start, end] ...
- 1
2
votes
1
answer
26
views
Shortest path in polygon from 2 points such that entire polygon is visible
Given an isothetic polygon (sides parallel to the x-axis or y-axis) and 2 points (start and end) on the boundary of the polygon,
find the shortest path traveling only in the direction of the x or y ...
0
votes
0
answers
7
views
Dynamic programming problem for minimum cost tower placement
I have an algorithmic problem in which I have a highway that is a straight line of length n and a set of unique respective costs for construction of a radio tower for each mile on the highway. I am ...
0
votes
0
answers
4
views
data flow analysis reaching definition analysis meaning
I'm trying to understand reaching definitions and I'm having hard problem wrapping it around my head with the following definition
Why part of the expression of ...
- 103
0
votes
0
answers
19
views
Two Counter word count language Nondeterministic Pushdown Automata (NPDA) problem actually Context Sensitive unless counters are multiples
Classic text (Linz, P., & Rodger, S. H. (2022). An introduction to formal languages and automata. Jones & Bartlett Learning.) describes the following language where one is to describe an ...
0
votes
0
answers
3
views
Two Counter word count language npda' problem actually Context Sensitive unless counters are multiples [duplicate]
Classic text (Linz, P., & Rodger, S. H. (2022). An introduction to formal languages and automata. Jones & Bartlett Learning.) describes the following language where one is to describe an ...
0
votes
0
answers
4
views
Two Counter word count language npda' problem actually Context Sensitive unless counters are multiples [duplicate]
Classic text (Linz, P., & Rodger, S. H. (2022). An introduction to formal languages and automata. Jones & Bartlett Learning.) describes the following language where one is to describe an ...
0
votes
1
answer
23
views
Will a FIFO buffer eventually stagnate?
Below depicts a FIFO buffer:
So the buffer is there for when the speed of data written into the FIFO buffer is faster than the data read.
But I don't understand one thing. Wouldn't eventually all the ...
- 101
-3
votes
0
answers
12
views
python django- adding a like function button [closed]
I am trying to add a like function to my blog, but I keep getting this error.
0
votes
0
answers
9
views
What are some good books for vlsi cmos design? Or some good educational software?
I'm a student trying to learn more about CMOS design, I already understand assembly and computer architecture, but VLSI is very interesting and I was wondering if you guys knew some good books/games ...
0
votes
0
answers
15
views
Approximation Algorithm for Bin packing Variant with Packing Overhead
I recently came up with this bin packing variant and was wondering, if someone has studied it before:
Given: Instance $I$ is a set of tuples $\begin{pmatrix}s_{i} \\ o_{i}\end{pmatrix}$ with $s_{i}, ...
1
vote
1
answer
34
views
(Co)-induction, fixpoints and inference systems
I'm learning about induction and co-induction. From what I know, given a set of judgments $U$ and an inference system $\Phi \subseteq \wp(U) \times U$, where $(\left\{ h_1,\dots,h_n \right\}, c) \in \...
- 13
-1
votes
0
answers
18
views
How to construct a turing machine from L= {w (a Ub)* | w = wR} [closed]
How to construct a Turing machine from L= {w (a Ub)* | w = wR} . I have to design a Turing machine in exam. help me.
-2
votes
0
answers
22
views
Maximum flow of multiples [closed]
The problem is that I'm given 3 numbers N which represents the number of nodes in my graph, M which reprensents the amount of vertexes and x which represents an amount of people. The problem is that I ...
- 1
-1
votes
0
answers
6
views
I need help plotting a 3D trajectory field for a 3x3 matrix [closed]
I'm trying to plot the trajectories of a 3x3 matrix. I can do this on the 2D plane but cannot get it to work on the 3D plane as needed for a 3x3 matrix. When I try to use
from sage.plot.streamline ...
0
votes
1
answer
55
views
Visiting all nodes of a directed graph exactly once (not dfs)
Consider a directed unweighted graph (in a adjacency matrix for example), how can I visit each node exactly once? By once I mean for example in a DFS traversal, a node can get finished and we should ...
- 35
0
votes
0
answers
31
views
Greedy Maximum Bipartite Matching
To find the maximum matching on a bipartite graph, I propose the following greedy algorithm:
At each iteration, pick an unmatched vertex with the smallest degree and match it to one of it's neighbours ...
1
vote
0
answers
18
views
Computing the centroid of an "ellipsoid slice"
I want to compute the centroid of a body of the following form:
$$
E\cap H_1\cap \cdots \cap H_T
$$
where:
$E$ is an ellipsoid in $\mathbb{R}^d$: $E = \{x = c + Bu | u^T u \leq 1\}$, where $c$ is the ...
- 5,720
2
votes
0
answers
47
views
Subset sum problem with big items
Consider the variant of the Subset Sum problem, where the input is a list of $2 m + 1$ positive integers of sum $2 S$, and the goal is to find a subset with the largest sum that is at most $S$. The ...
- 5,720
0
votes
1
answer
14
views
Variant of Bounded Subset Product
Consider the following decision problem:
Given $([b_1, \cdots, b_n],t)$, where $[b_1, \cdots b_n]$ is an array of natural numbers and $t \le n^c$, do there exists natural numbers $f_1, \cdots f_n$ ...
- 1
1
vote
0
answers
42
views
Borůvka's step in linear time
I am trying to understand this Expected linear time MST algorithm, and I have a problem in the implementation of the Borůvka's step.
My problem is with the removal of duplicate edges between merged ...
- 12.5k
-5
votes
0
answers
17
views
DFA testing exercice ASAP please [duplicate]
I have a question :
If my word can be only AA or BB or A or B how i will write my regular expression ?
And if 0 is a par number it also may be to include ?
it is something like this : A|B|epsilon) (AA|...
0
votes
1
answer
30
views
Complexity of multiplying 3 matrices
There are algorithms that speed up matrix multiplication over the naive $n^3$ algorithm. But supposing you have 3 matrices $A$, $B$ and $C$, is there a way to compute $ABC$ that is asymptotically ...
- 101
-1
votes
1
answer
21
views
CFGs and Pushdown Automata
Is this the CFG for part (a),
S -> AxxyxxA
A -> Ax|ε
If this is the answer then this grammar would accept &...
- 1
0
votes
1
answer
23
views
What is the largest "allowed" seed for a PRNG to not give any extra power to a deterministic machine?
Suppose a polynomial time machine that has an access to a polynomially long string of bits independent on the input. On average, it's impossible to compress this string to a subpolynomially long ...
- 1,417
0
votes
0
answers
16
views
Greedy algorithm for trading cryptocurrencies with perfect price information
Assume the following hypothetic scenario:
You know the values $v_1^0, \ldots, v_n^0$ of $n$ cryptocurrencies. You know the values this currencies will have for the following $m$ days; this is, $v_0^1,...
- 181
0
votes
0
answers
6
views
Understanding atomic requests/transactions in a snooping coherence protocol
I've been reading the book "A Primer on Memory Consistency and Cache Coherency", and it contains the following paragraph:
The Atomic Requests property states that a coherence request is
...
- 111
0
votes
0
answers
36
views
Complexity of topological sorting with a special restriction
Let $G = (V, E)$ be a connected DAG (representing a circuit) with every vertex may be one of the following three types:
Input variable, with in-degree $0$ and out-degree $\geqslant 1$.
A gate, with ...
- 13
1
vote
0
answers
35
views
How do i make a 2d array as same as i possibly can with another one?
Say i have an 2d array A of nxn size, int values already given for each item.these values can be the same or different.
There's gonna be another nxn array B being input.
I can only interchange one row ...
- 11
-1
votes
2
answers
165
views
Could this novel algorithm be qualified to be published in Nature or Science
I recently designed an algorithm for single-source shortest paths in graph structures, which can limit the number of edges as Bellman-Ford while approaching the performance of SPFA. Of course, it also ...
0
votes
0
answers
50
views
Necklace Alignment Problem
We are given two cyclic $\{0,1\}$ strings $X$ and $Y$ with both length $n$, containing $k$ 0s and $n-k$ 1s. Suppose positions of 1 in $X$ are $x_0,\dots,x_{k-1}$, for $Y$ are $y_0,\dots,y_{k-1}$. We ...
- 1
-1
votes
0
answers
14
views
Clique to SAT example explanation
We are at college trying to implement the reduction of the clique problem to a SAT problem but I dont quite get the examples of the slides if someone can give me a not so technical explanation of what'...
0
votes
1
answer
28
views
What's the Time Complexity and total no of iterations?
for a=1 to m means for(a=1;a<=m;a++)
for i=1 to n
for j=i to n
c= c+1;
The total no of iterations is O(n^2)
...
-2
votes
0
answers
7
views
Construct a pda
Construct the pda that accept following language
L * 1 = {a ^ m * b ^ n / 2 * n <= m <= 3n, n >= 1}
Trace the operation of M on the string aaaaabb
1
vote
0
answers
31
views
Why bisection width of star connected network is 1?
This may seem like a simple question, but I can neither find the answer on the internet nor AI tools can give a proper answer. I was reading a book about static networks and I saw that the bisection ...
- 11
1
vote
0
answers
19
views
How do I prove relations of two CTL formulas?
If I have two CTL equations, how do I prove they're equivalent or that one implies the other?
What's the general approach? Disproving is obvious, but I am unable to figure out how to prove the ...
- 121
0
votes
3
answers
109
views
Testing whether a number (N) is prime or not can be made very fast but it will require storage space
Testing whether a number (N) is prime or not can be made very fast but it will require storage space.
If there is a central repository that stores all prime numbers found till now and if there is a ...
0
votes
1
answer
235
views
What is the simplified form of this big o
$O(\sum_{l=0}^{log_2n} l*2^l)$. I took the integral of the term which I think is $O(n*log(n))$
- 17
0
votes
0
answers
10
views
O(n^3) Algorithm for Maximum Weighted Cycle Cover for Undirected Complete Graph with Triangle Inequality
I have been trying to implement an approximation algorithm for the max traveling salesman problem with triangle inequality, and each paper I've read references the step of finding the max cycle cover ...
0
votes
0
answers
14
views
better ways to integer interpolation?
I made some code about "integer interpolation" for running approximate alpha blending at FPGA which have low quantities of logic gate.
Let's refer to "II" as integer interpolation.
...
- 1
0
votes
0
answers
9
views
Morton-code based Linear BVH: Why do triangle's bounding boxes' centroids give higher-quality trees than triangles' centroids?
I've implemented linear BVH as described in Karras 2012, and I was using triangles' centroids for Morton Code generation. I found recent papers and implementations use triangles' bounding boxes' ...
0
votes
1
answer
28
views
What is the practical use of list.clear() method in Python?
I was wondering if there is a reason behind clearing all the values in a list and reusing it, as opposed to deleting the list and creating a new one. Are there any practical advantages of using ...
- 101
-3
votes
1
answer
102
views
If Q* can break encryption would that prove P=NP?
At 12:11 in this video the creator talks about unverified rumors the Q* algorithm can break AES-192 encryption. If this is true, would this mean P = NP?
- 97
0
votes
1
answer
19
views
Regarding CPU ILP: what actually consistitutes "the current instruction"?
If a CPU is able to execute multiple instructions in parallel, and fetching/decoding/scheduling instructions happen in batches, and there's multiple execution units, etc. What does the IP register ...
- 457
0
votes
0
answers
15
views
maximum step of sorting network
How to calculate the maximum step of sorting network?
Based on image below, it has most comparators at second index which is 9 comparators than another indices. That's mean, overall networks need 9 ...
0
votes
0
answers
13
views
Why is the block size chosen to be q-1 for Reed-Solomon codes?
Consider a Reed-Solomon code over a finite field of $\mathbb{F}_q$. Why is the typical block size chosen to be $q-1$ [1][2][3]? The reasoning I saw around this is ...
- 101
1
vote
0
answers
28
views
What's the intuition behind MIP* being bigger than MIP?
It is well-known that $\mathsf{MIP} = \mathsf{NEXPTIME}$, and recently there was a breakthrough stating that $\mathsf{MIP^*} = \mathsf{RE}$.
This was very confusing because it seemed like the (...
- 335
1
vote
2
answers
57
views
Complexity of satisfiability for relational logic on the booleans
I know that propositional satisfiability is NP-complete and that if I add first-order quantifiers I get the complete problems for the polynomial hierarchy and PSPACE. What happens if my formulas are ...
- 2,184