All Questions

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 ...

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 ...

...

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

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. ...

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 ...

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. ...

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 ...

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$...

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 ...

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 ...

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 ...

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 ...

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 ...

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

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 ...

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 ?

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 ...

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 ...

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 ...

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 ...

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, ...

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 ...

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$. ...

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 ...

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.

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 ...

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]) ...

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: $(), ()(), (()...

The question was to convert this recursive code with intermediate variables to a functional program code without any intermediate variables. ...

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 ...

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 ...

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$ ...

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 ...

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....

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 ...

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 ...

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 ...

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 ...

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?

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 ...

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\,|\...

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. ...

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 ...

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 ...

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 ...

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 ...

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 ...

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). ...

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 ...