All Questions

43,043 questions
Filter by
Sorted by
Tagged with
11 views

How to build certificates?

Problem:- I have moving points in a 2d space with a fixed obstacle(A polygon) and a fixed destination. I want to find at what time Source(which is moving) can get a path to destination and what is ...
12 views

Proof no DPDA can accept Palindrome (need explanation for the attached proof)

The given proof for proving that no DPDA can be constructed to accept palindromes is unclear. There exists another similar question but it only explains the proof partially. I understood how it aims ...
8 views

...
10 views

Can a context-free Language have an infinite pumping length?

I have a language that would require an infinite pumping length, I know the language is not context-free, but is this sufficient prove ?
8 views

A DFS update without re-running DFS after adding and removing an edge

Given an undirected graph $G=(V,E)$ I perform a DFS run on it, and among other information I get the visit time $s(\cdot )$ and the exit time $f(\cdot )$ per each node and the parent of each node. ...
18 views

Efficient comparison, using only sum, product, difference, and conditional jump if zero

I was wondering how small we could make the instruction set of a typical machine that supports a single datatype: arbitrary integers. If you need a heap, you declare an integer variable $h$ where you ...
12 views

Beginning Algorithm Design and Proving

I know this is a general question, so you can address this by giving some examples that are specific to your field. I want to start learning algorithm design and consequently prove its convergence. ...
14 views

Conflict Clusters – Another P=NP Proof [closed]

Conflict Clusters – Another P=NP Proof Exactly 1 in 3 SAT ($X3SAT$) is a variation of the Boolean Satisfiability problem. Given an instance of clauses where each clause has three literals, is there a ...
7 views

Contiguous-substring operator

If string concatenation $ab$ is like left- and right-multiplication, is there any infix (latex) operator notation I can use for checking for contiguous substrings, like $bc \subseteq abcd$? $\subseteq$...
11 views

For a given $3$sat, how many possible unique clauses are there which have empty intersection of their unsatisfiable space?

For a given $3$-sat with with $n$ variables the solution space is $2^n$. For $n=3$ a clause like $$(x_1 \vee x_2 \vee x_3)$$ rules out the assignment $$(x_1,x_2,x_3) = (0,0,0)$$ and we can see in this ...
14 views

Incremental Decision Tree Performance

I read about online trees different than Hoeffding based algorithms. Lets say I build a tree by adding one train instance in a loop and add each train data iteratively. I check if current instance is ...
18 views

Can I use the CYK-Algorithm for a Grammar where all results still have a Variable in them?

Let the Grammar be G = ({S}, Σ, P, S), where Σ = {⟨,⟩,[,]} and P: S → ⟨S⟩, [S], SS, ε [⟨ → ⟨[ Can I still use the CYK-Algorithm and if yes then how would I do it ...
31 views

Finding a set of 9 integers that minimize an error function

I have an algorithm that takes a 3d triangle PMN(which is constructed from running a function that converts per-vertex UV coordinates to a PMN triangle) and P' which is a randomly chosen 3D point that ...
16 views

What is the difference between these 4 Finite Automatons?

I am a Uni student and am a little bit confused.. because I was wondering what the differences are between FA1 and FA2 -> as well as the differences between FA3 and FA4. Because to me they all look ...
29 views

Can a program span on 0 memory cells? If so, where is it hosted? (where it "sits down")?

In this question post, one of the answers is: ...
29 views

Bowyer-Watson Delaunay Triangulation neighbour walk in $O(n^{1/d})$

The Bowyer-Watson Algorithm for creating Delaunay Triangulations works iteratively. Let's say that we have a Delaunay triangulation of $n-1$ points. Now we add the $n$-th point. In order to update the ...
23 views

Is this context free grammar ambiguous?

CFG: stmt → IF expr THEN stmt | matchedStmt matchedStmt → IF expr THEN matchedStmt ELSE stmt | other i got those parse trees and i think is unambiguous. Is this true ?
28 views

Difficulty in finding a counter example for a polynomial reduction

I am doing some exercises on proving NP Complete problems and the first problem was directed bipartite graphs with a Hamiltonian cycle and the second one was undirected bipartite graphs with a ...
27 views

Graph in which greedy algorithm for maximum matching is a 2-approximation

Here is a greedy algorithm for maximum bipartite matching: Iteratively select an edge that is not incident to previously selected edges. This algorithm returns a 2-approximation, and runs in linear ...
139 views

Efficient intersection of equivalence classes

Having two equivalence relations, both as a union find data structure with the same number of elements, what is the most efficient way to find the equivalence relation that is the intersection of both ...
12 views

Can't figure out decision variable

Good Evening, I am trying to solve an exercise related to my algorithm designing course. I have understood the question and what it asks. I am required to formulate an ILP and then relax it to ...
153 views

Designing a Queue that efficiently tracks position

Suppose we want to construct a queue with the following properties: The priority of each member of the queue must be known. For example, for the head node, their priority is 1, for the next node, ...
27 views

Find set of vertices of max size under some restrictions [duplicate]

I've faced a problem and I don't know what approach I must follow, dynamic programming or greedy method, so here is the question. Question: Given a directed tree $T=(V,\ E)$. We're required to find a ...
44 views

Maximum independent subset for graphs with lots of edges

Consider an NP-hard graph problem, like the maximum independent set problem. Let us say I restrict my inputs to only be graphs that have $n$ vertices and at least $n^{c}$ edges, for some $c > 1$. ...
29 views

Abstract Interpretation: Connection between soundness relation and a Galois connection

I am currently studying the paper "Abstract Interpretation Frameworks" by Cousot and Cousot from 1992 (https://doi.org/10.1093/logcom/2.4.511) to gain an understanding of the theory behind ...
24 views

CFLs are accepted by two-state PDAs w/o $\epsilon$-transitions

Show that if $L$ is accepted by a PDA, then $L$ is accepted by a PDA having at most two states and no $\epsilon$-transitions.
13 views

Complexity analysis of a recursion

A recursive algorithm has the following computation tree. The label on the node indicates the number of outgoing edges. This algorithm takes an input of length $n$ and at each processing, it results ...