All Questions

Filter by
Sorted by
Tagged with
0
votes
0answers
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 ...
0
votes
1answer
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 ...
-1
votes
1answer
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 ?
0
votes
0answers
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. ...
1
vote
0answers
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 ...
0
votes
1answer
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. ...
0
votes
0answers
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 ...
1
vote
0answers
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$...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
-1
votes
0answers
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 ...
0
votes
0answers
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 ...
-1
votes
0answers
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 ...
0
votes
1answer
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: ...
2
votes
0answers
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 ...
-2
votes
0answers
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 ?
0
votes
0answers
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 ...
1
vote
0answers
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 ...
3
votes
1answer
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 ...
0
votes
1answer
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 ...
3
votes
1answer
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, ...
0
votes
0answers
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 ...
2
votes
1answer
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$. ...
2
votes
1answer
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 ...
-3
votes
0answers
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.
1
vote
1answer
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 ...
-1
votes
0answers
30 views

Can we find 1's complement of a positive signed number? [closed]

I wanted to ask that can we find 1's complement of a signed/unsigned positive number. (Here 2's complement mean the radix complement and 1's complement [that we study in computer system architecture]) ...
1
vote
1answer
26 views

Disambiguating grammar for Dyck language

Given the following simple grammar for a language that contains all strings with matched parentheses: \begin{align} &s \to ss \\ &s \to (s) \\ &s \to () \end{align} Examples: $(), ()(), (()...
0
votes
0answers
19 views

recursive function without intermediate variables

The question was to convert this recursive code with intermediate variables to a functional program code without any intermediate variables. ...
2
votes
1answer
28 views

Data structure for finding lowest element in range

Consider the following setting: There are tasks $T = \{T_i\}_{i=1}^n$ with priorities $p_i$, and locations $x_i \in \mathbb{R}^2$. Given a location $y \in \mathbb{R}^2$, I would like to find and pop ...
0
votes
2answers
49 views

Can a software program be stored in just one memory cell?

I would define a software program as at least one line of code stored in at least one computer system's memory cell. Can a software program be stored in just one memory cell or rather (due to binary ...
1
vote
0answers
17 views

showing the amortized runtime of insert in a dictionary realization is O(log n) [closed]

Consider the following realization of the dictionary abstract data structure. There is an array $A[0...N]$ for some $N\ge 0$. Entry $A[j]$ is NIL (or NULL) or it stores an array of size exactly $2^j$ ...
2
votes
1answer
30 views

Range queries with O(N log N) build and O(1) query

I read somewhere that you can compute range queries in O(1) with O(N log N) preprocessing for any associative operation (but not necessarily invertible or idempotent). How do you do this? I know this ...
-1
votes
0answers
15 views

Calculating Effective CPI

I'm stuck on this question if I could get some help? Calculate the effective CPI (taking into account both instruction execution and memory access) for the following unified instruction and data cache....
0
votes
0answers
12 views

Is a computational model that can instantly access any storage address and can access any arbitrary number of them at once more powerful then a TM?

This would be a computational model that would have unbounded space. But with a jump command that can access and do operations on any finite number of cells at once. Actual calculations would take ...
0
votes
0answers
11 views

Comparison of Complexity of counting bits in a binary representation

I was asked the following question: Given a number num - write a function (in python) that counts the number of ones in its binary representation. This is the ...
0
votes
2answers
24 views

Are there any complexity classes that can be solved in Polynomial Time that are not in PSPACE?

These would be problems solvable in Polynomial time with and only with pseudo-polynomial or Exponential Space. Do such problems exist? if so which complexity class are they? If not can you prove that ...
1
vote
0answers
32 views

What is the difference between the Church-Turing thesis and the Church-Turing-Deutsch principle?

I am trying to get a better handle on the Church-Turing thesis, and I am confused by the difference between the two ideas in the title. The wikipedia page for the Church-Turing thesis says, the ...
0
votes
0answers
14 views

Calculating memory bandwidth

There's something I'm confused about in calculating the bandwidth. It's defined as number of bytes transferred, and we know that each word is 2 bytes, why are we multiplying 4 words by 4?
-4
votes
1answer
21 views

Polynomial-time Computable $f \circ g$. What does this implies for $f$ and $g$

Suppose that $f$ and $g$ are functions and $f \circ g$ is polynomial computable. a) is it true that $f$ is also polynomial computable b) is it true that $g$ is also polynomial computable c) if we ...
0
votes
1answer
14 views

Computing Earley Parsing Steps

I am trying to understand Earley parsing algorithm using an example. The grammar I use produces all the palindromes over $\Sigma=\{a,b,c\}$: \begin{align*} Z & \to S\\ S & \to a\,|\,b\,|\,c\,|\...
1
vote
0answers
13 views

Bin-packing with a capacity constraint on pairs of bins

In the classic bin-packing problem, we have to pack some positive integers into bins, such that the sum in each bin is at most some constant $B$, and subjet to this, the number of bins is minimum. ...
1
vote
1answer
17 views

Reducing a seating problem to maximum flow

Problem: We have p different families with $1 \leq i \leq p$ members for the $i$-th family. We also have q tables where table $t_j$ has a capacity of $1 \leq j \leq q$. We want no two members of a ...
2
votes
1answer
31 views

Minimum number of edges to remove from a graph, so that MST contains a certain edge

Let's suppose we have a weighted and connected graph. We can easily find the minimum spanning tree for this graph. But let's say we want to "force" a certain edge $e$ to be in the MST. For ...
0
votes
0answers
12 views

Detect the actual edges of circle in directed graph [duplicate]

Okay so , I know how bellman -ford can detect a negative circle. My question is : how to actually find the edges participating in this circle. I searched and found some stuff that seem to work in the ...
1
vote
1answer
24 views

Finding a 'short' binary sequence not contained in a given binary sequence

Let $k>1$ be an integer, let $n = 2^k$. Let $s: \{0, \ldots, n-1\} \to \{0,1\}$ be any binary sequence of length $n = 2^k$. There are $n - k$ coherent subsequences of $s$ having length $k$, and the ...
1
vote
1answer
17 views

How to reduce 3-SAT to Set Splitting

I've been reading through Garey & Johnson's "Computers and intractability", and a problem SP4 caught my attention. It is stated as following: Given a collection $C$ of subsets of a ...
0
votes
1answer
31 views

How can i do this type of swap(4-opt) between 4 edges of a graph?

The double bridge move is a specific type of swap between 4 edges of a graph, also called 4-opt. It consists of removing 2 pairs of edges. Let`s call them (I, I+1), (J, J+1) and (P, P+1), (Q, Q+1). ...
1
vote
0answers
15 views

How to find if there's an MST where vertex $v$ has degree 2 in it? [duplicate]

I've faced this question and I hope that someone can help with it. Question: We're given an undirected graph $G=(V,E,w)$ where $w\colon E\rightarrow \mathbb{Q}$ and vertex $v$. We want to find if ...

15 30 50 per page
1
2 3 4 5
861