All Questions

Filter by
Sorted by
Tagged with
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 ...
Daniel's user avatar
  • 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 ...
mmartiss's user avatar
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] ...
patayala's user avatar
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 ...
swastik sarkar's user avatar
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 ...
Izzy Handkammer's user avatar
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 ...
Jorayen's user avatar
  • 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 ...
John Daniels's user avatar
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 ...
John Daniels's user avatar
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 ...
John Daniels's user avatar
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 ...
cm64's user avatar
  • 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.
african_geek's user avatar
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 ...
1grungler1swag's user avatar
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}, ...
blackdra_gon's user avatar
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 \...
dalz's user avatar
  • 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.
Phone Myint Zaw's user avatar
-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 ...
Faz's user avatar
  • 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 ...
user164686's user avatar
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 ...
shh's user avatar
  • 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 ...
eeeeellllll's user avatar
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 ...
Erel Segal-Halevi's user avatar
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 ...
Erel Segal-Halevi's user avatar
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$ ...
adelta's user avatar
  • 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 ...
Nathaniel's user avatar
  • 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|...
Duarte Grilo's user avatar
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 ...
user34722's user avatar
  • 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 &...
Don senu's user avatar
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 ...
rus9384's user avatar
  • 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,...
lafinur's user avatar
  • 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 ...
eof's user avatar
  • 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 ...
user779130's user avatar
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 ...
HelpmePlease's user avatar
-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 ...
Shawxing Kwok's user avatar
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 ...
Fireond's user avatar
-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'...
user164639's user avatar
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) ...
Vedant Khandelwal's user avatar
-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
Hamad Bilal's user avatar
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 ...
user164631's user avatar
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 ...
JobHunter69's user avatar
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 ...
user164617's user avatar
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))$
Prikshet's user avatar
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 ...
ConfusedGerbil's user avatar
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. ...
박성재's user avatar
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' ...
nitroglycerine's user avatar
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 ...
Akshay Katiha's user avatar
-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?
Asleepace's user avatar
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 ...
ABu's user avatar
  • 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 ...
Muhammad Ikhwan Perwira's user avatar
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 ...
mutantacule's user avatar
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 (...
Dannyu NDos's user avatar
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 ...
user1868607's user avatar
  • 2,184

15 30 50 per page
1
2 3 4 5
955